Introduction
You remember a word from a note but cannot remember its directory. A useful search tool should find every matching note, distinguish equal filenames, and show real lines you can open in the source.
Build that relationship with C++ maps and sets. Loading, word parsing, query handling, and line display are prepared; you implement the index and try it against changing practice notes. You need basic terminal navigation, C++ strings, vectors, functions, file streams, and exceptions. Maps and sets are taught here. The 50-minute duration is an author estimate.
Connect a Word to Every Note
In this step, use a working sample, then build the word-to-document index for your own executable. Use the Terminal tab throughout this course. It opens a UTF-8 shell; use this named tab rather than a terminal inside WebIDE. The shell's directory lasts within that open connection. If you open another connection, repeat the visible cd.
cd changes the working directory. Start in the prepared project:
cd /home/labex/project/note-search
notes/reference contains protected originals; notes/practice contains a writable copy. find lists paths recursively; -type f limits the listing to regular files. Listing order does not matter.
find notes -type f
Both notes/reference/archive/notes.txt and notes/reference/field/notes.txt exist. The last filename component, or basename, is identical, but the complete paths identify different documents. ./ runs an executable in the current directory. The complete sample takes a notes directory and a query:
./sample notes cat
It returns three document groups, including these two:
File: reference/archive/notes.txt
1: CAT, cat!
3: cat blue together
File: reference/field/notes.txt
1: cat; red
The third group is practice/旅行 notes.txt. Each identity is relative to the supplied notes root, so it omits notes/. Each document appears once, even when the word occurs several times. Numbers are real, 1-based source line numbers. Only relevant lines appear; a missing number does not mean the source line was deleted. cat prints a text file so you can compare:
cat notes/reference/archive/notes.txt
Line 2, Blue ledger — 東京, is present but does not contain cat. The original UTF-8 paths and line text are preserved.
Our small word rule is precise: a token is a maximal run of ASCII letters A-Z or a-z, with uppercase ASCII folded to lowercase. Digits, underscores, punctuation, spaces, and every non-ASCII byte separate tokens. CAT-blue_42 becomes cat and blue; cat differs from catalog; 猫cat狗 contains cat; café produces caf, not cafe. Preserving Unicode text is different from understanding words in every language. We do not implement multilingual segmentation.
Read the prepared interface and your starter:
cat search.hpp
cat engine.cpp
Document holds id, the complete relative path, and lines, a vector of original line strings. Prepared loading recursively reads regular .txt files and sorts their identities. Notes are UTF-8 text with LF line endings. Spaces and Unicode are allowed in paths; path tabs/newlines, symlinks, NUL data, and arbitrary binary files are outside this format. Unreadable input produces an error rather than partial results.
Index aliases std::map<std::string, std::set<std::string>>. A map associates each distinct word key with a value: here a set of document IDs. A set retains each ID once. Three occurrences of cat in one document therefore produce one relationship. This reversed lookup from words to documents is an inverted index.
Your starter returns an empty index. provided.inc contains this unit's already working query function. #include inserts a file at compilation time. Preserve search.hpp, provided.inc, support.cpp, main.cpp, sample, and every notes/reference/ path and content. Edit engine.cpp; you may add helpers or use equivalent algorithms. Only notes/practice/ may be edited, added to, or deleted from. Its original membership is not a grading requirement.
bash runs the prepared self-check script. index selects the behavior taught here. This first run intentionally fails with FAIL exact whole-word postings retain complete document identities and a nonzero exit status. That means your index is incomplete, not that the environment is broken:
bash /opt/labex-note-search/check.sh index
Visit every document, line, and parsed word. A range-based for visits each element; const auto& gives a read-only reference instead of copying it. index[word] accesses the word's set, creating an empty one if the key is new. .insert(doc.id) adds the complete identity and ignores duplicate relationships. Keep the map outside all loops to accumulate every document.
The next command replaces only engine.cpp. A here-document sends several lines to cat; > writes them to the named file, replacing its contents. The quoted delimiter 'CPP' prevents shell expansion of the C++ text. Finish with CPP alone on a line. Keep both includes so declarations and the prepared query implementation remain available.
cat > engine.cpp <<'CPP'
#include "search.hpp"
#include "provided.inc"
Index buildIndex(const std::vector<Document>& documents) {
Index index;
for (const auto& doc : documents) {
for (const auto& line : doc.lines) {
for (const auto& word : words(line)) {
index[word].insert(doc.id);
}
}
}
return index;
}
CPP
words(line) is the prepared ASCII parser. Do not extract a basename, stop at the first match, or store an occurrence count instead of the document set.
Compile your deliverable. g++ is the compiler; -std=c++17 selects the language version, -Wall -Wextra enables useful warnings, and -o findnotes names the output executable. The three .cpp inputs are your engine, the prepared loader/parser, and the command interface. Included files are read automatically.
g++ -std=c++17 -Wall -Wextra engine.cpp support.cpp main.cpp -o findnotes
A successful build usually prints nothing. On error, read the first filename and line number, correct engine.cpp or repeat its complete replacement, and compile again. A failed build may leave an old executable in place. Editing source alone does not update it. The self-check tests both your original functions in an isolated fixture and your existing findnotes; it does not rebuild that executable for you.
./findnotes notes cat
Expect all three document identities and the same original lines as the sample. Another repeatable document order is allowed; lines within each document must increase and appear once. This step grades the index and single-word behavior. Combining different query words is prepared here and becomes your task in the next lab.
Rebuild from Current Practice Notes
In this step, edit, add, and remove practice data while retaining the original notes. Stay in Terminal, in /home/labex/project/note-search. Each invocation loads current files and builds a fresh in-memory index. There is no saved index file, refresh daemon, or extra rebuild command.
First compare whole-word boundaries:
./findnotes notes catalog
Expect reference/catalog.txt and practice/旅行 notes.txt, with lines containing catalog. They are not extra cat matches. An unknown word is a normal search:
./findnotes notes absent
It prints No matching documents. and exits successfully. This differs from malformed input, which the prepared interface rejects. The next lab examines that distinction.
The practice copy is already writable; reference originals are read-only. Single quotes keep a path with spaces as one argument and preserve Unicode characters. printf writes text; \n creates a line break. > replaces the entire named practice file. Remove cat from this copy by replacing its content:
printf 'owl green\n東京 — preserved\n' > 'notes/practice/旅行 notes.txt'
./findnotes notes cat
Only the two reference notes match now. The practice file still exists; its current contents no longer match. Add a new allowed practice note:
printf 'CAT beside the window\nA new observation\n' > 'notes/practice/new notes.txt'
./findnotes notes cat
Three documents match again, including practice/new notes.txt at line 1. You did not recompile: changing data only requires rerunning the program. Changing C++ source requires compilation.
rm removes a file. Its single quoted operand here is the new practice note, not an original or an entire directory:
rm 'notes/practice/new notes.txt'
./findnotes notes cat
That identity disappears; the two reference results remain. Never delete originals or alter the parser to force a result. If you misspell a path, read No such file or directory, list paths with find notes -type f, and use the exact path. If you target a read-only original, leave it unchanged and use a practice file. Normal path errors do not require resetting the environment.
Run the self-check again. It reads your live files, then creates disposable fixtures for further inputs. Fixture edits/additions/deletions never modify your practice data. Expected error messages from isolated invalid-input probes can appear beside PASS lines; a successful run ends with CLI CHECKS PASSED.
bash /opt/labex-note-search/check.sh index
The check button should pass too. Repeating a check does not rewrite your code, replace the executable, or reset practice notes. If it fails after a source edit, rebuild the actual findnotes and retry. Temporary function tests alone cannot prove your executable is current.
Summary
You built an inverted index whose values are sets of full document identities. Repeated words do not duplicate documents, equal basenames stay separate, and real line numbers lead back to original text. Rerunning transparently rebuilds from allowed practice edits, additions, and deletions. Next, implement the query intersection that requires several words in the same document.
