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. 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.
Before writing the index, predict its cat entry. Read the other original with the same basename and the practice note; single quotes keep its space-containing path as one argument:
cat notes/reference/field/notes.txt 'notes/practice/旅行 notes.txt'
Which full IDs should the set contain? Count documents, not occurrences: the archive's repeated CAT and cat still contribute one ID. The expected set is reference/archive/notes.txt, reference/field/notes.txt, and practice/旅行 notes.txt. Keeping only notes.txt would merge two distinct originals. reference/catalog.txt is not a cat result: its whole word is catalog. This prediction gives you a concrete relationship to compare with your implementation.
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
Build that relationship inside the existing function, rather than replacing the file. First decide what must accumulate: one Index outside the loops. Visit each Document, then each original line in doc.lines, then each word returned by the prepared words(line) parser. A range-based for visits each element; const auto& reads it by reference without copying or changing it. index[word] accesses that word's document-ID set, creating an empty set for a new key. .insert(doc.id) adds the full identity once, even when the word repeats. Returning after all three loops retains every document.
Open the existing source in nano, a text editor inside Terminal:
nano engine.cpp
The bottom shortcut labels use ^ for Ctrl: ^O means hold Ctrl and press O, without Shift. Use arrow keys to move. Ctrl+W starts a search; type Index buildIndex, then Enter. This unique signature identifies the function you will edit. Keep both #include lines, the function signature and its opening and final closing braces. The actual unfinished body contains exactly these two lines:
(void)documents;
return {}; // TODO: connect every whole word to every full document identity.
Move down from the signature to (void)documents;. Home (or Ctrl+A) moves to the start of that logical source line. Check the text before cutting: Ctrl+K cuts the current line. Cut that line and then the following return {}; line, including its inline TODO comment. Stop at the function's final }; do not cut it. A long line may wrap on screen without being another source line.
At that position, type the body below. Start by declaring the accumulator, then write the three loops and explain to yourself which object each loop visits. The innermost statement records the predicted relationship; the final return comes after the loops. This is C++ text to type in nano, not a shell command. Its three inner closing braces close the three loops; the function's existing final brace stays below it.
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;
Finish the body with Enter so the retained function brace is on its own line. Check both includes, the signature, loop braces, return index;, and that retained outer brace. Do not extract a basename, stop at the first match, or store an occurrence count instead of a document set.
Save with Ctrl+O. At the filename prompt, keep engine.cpp and press Enter; read the write confirmation. Ctrl+X exits to the shell. Ctrl+C cancels a search or filename prompt and returns to the buffer. If you exit a modified buffer, nano asks whether to save: Y saves (then confirm the filename with Enter), N discards only unsaved edits, and Ctrl+C cancels exiting so you can keep editing.
For an immediate accidental cut, Ctrl+U reinserts the cut text at the cursor; consecutive cuts can be restored together, so inspect what came back. For an ordinary mistaken edit, Alt+U (or Esc, then U) undoes the edit. If you have damaged the surrounding structure and have not saved, exit with Ctrl+X, N, reopen the file and edit only the body again. Discarding does not reverse edits already saved: reopen and repair the includes, signature or outer brace using the starter context above. Do not rerun setup or change protected files to recover an edit.
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, start with the first filename and line number in the diagnostic. For example, if it identifies engine.cpp:12, nano +12 engine.cpp opens that file at line 12; use the actual reported number. The + number is a starting line, not a change to the file. Correct the local mistake, save and exit as above, then compile again. Do not edit a protected include to silence a source error. 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.
