C++ / CAPSTONE PROJECTS
Project: a text indexer built on maps and sets
Build a C++ inverted index with std::map<std::string, std::set<int>> that keeps words sorted and line numbers unique, and query it with set_intersection.
What you will learn
- Invert text into word -> line-number postings using std::map<std::string, std::set<int>>
- Use index[word].insert(line) to create a missing bucket and dedupe in one lookup
- Print an alphabetical index straight from map iteration, with no sorting step
- Combine query terms with std::set_intersection over the stored line-number sets
Understanding Project: a text indexer built on maps and sets
A text indexer transposes a relation. The input runs line -> words: line 1 holds "the", "cat", "sat"; line 2 holds something else. A search needs the opposite direction, word -> lines, so building the index is a single pass over the text that records, for every word encountered, the number of the line it came from. Nothing about the text is stored twice; the index is just the same pairs read along the other axis.
The reason std::map<std::string, std::set<int>> makes this project short is that all three properties you want from the finished index are invariants of the containers rather than steps in your code. index[word] default-constructs an empty std::set the first time a word appears, so the insertion loop needs no "have I seen this word" branch. std::set<int>::insert silently ignores the second occurrence of a word on the same line, so postings stay unique and ascending. And iterating a std::map visits keys in comparison order, so printing the index alphabetically requires no sort call. The whole build reduces to one statement in the inner loop.
Two details decide whether the index is actually usable. The keys are compared as byte sequences, so "The" and "the," are different words from "the" unless you fold case and strip punctuation before forming the key; put that in one normalize function and call it on the way in and on the way out, otherwise queries silently miss. Cost-wise each word pays O(log W) string comparisons for the map plus O(log L) for the set, which is cheap for text-sized inputs; swapping in std::unordered_map buys faster average lookup but gives up the free ordering, so you would then have to collect and sort the keys before printing.
<iostream>
<sstream>
<string>
<map>
<set>
<cctype>
// Fold case and drop punctuation so "The" and "the," become the same key.
std::string normalize(const std::string& raw) {
std::string out;
for (unsigned char c : raw) {
if (std::isalnum(c)) out += static_cast<char>(std::tolower(c));
}
return out;
}
int main() {
const std::string text =
"the cat sat on the mat\n"
"The dog sat on the log.\n"
"A cat and a dog!\n";
std::map<std::string, std::set<int>> index;
std::istringstream lines(text);
std::string line;
int lineNo = 0;
while (std::getline(lines, line)) {
++lineNo;
std::istringstream words(line);
std::string word;
while (words >> word) {
std::string key = normalize(word);
if (!key.empty()) index[key].insert(lineNo);
}
}
for (const auto& entry : index) {
std::cout << entry.first << ":";
for (int n : entry.second) std::cout << ' ' << n;
std::cout << '\n';
}
std::cout << "distinct words: " << index.size() << '\n';
}
An inverted index is the input relation read backwards, and choosing map-of-set makes sortedness and deduplication properties of the container instead of code you have to write.
Worked examples
Answering a multi-word query
Finds the lines that contain every query term by intersecting the stored posting sets.
<iostream>
<string>
<map>
<set>
<vector>
<algorithm>
<iterator>
int main() {
std::map<std::string, std::set<int>> index{
{"cat", {1, 3, 4}},
{"dog", {2, 3, 4}},
{"sat", {1, 2, 4}}
};
std::vector<std::string> query{"cat", "dog", "sat"};
std::set<int> hits;
bool first = true;
for (const std::string& term : query) {
auto it = index.find(term);
if (it == index.end()) { hits.clear(); break; }
if (first) { hits = it->second; first = false; continue; }
std::set<int> merged;
std::set_intersection(hits.begin(), hits.end(),
it->second.begin(), it->second.end(),
std::inserter(merged, merged.end()));
hits = merged;
}
std::cout << "lines with all terms:";
for (int n : hits) std::cout << ' ' << n;
std::cout << '\n';
std::cout << "index still holds " << index.size() << " words\n";
}
Example explained
Line 1index.find(term) is used instead of index[term] so a term absent from the text cannot add an entry, which is why the index still reports 3 words.
Line 2std::set_intersection requires both inputs to be sorted by the same ordering, and std::set<int> always is, so no preparation is needed before the merge.
Line 3std::inserter lets the algorithm write into a set; the set ignores the position hint and keeps the results ordered itself.
Line 4The candidate set narrows with each term: {1,3,4}, then {3,4}, then {4}, and one missing term collapses it to empty immediately.
How a search can grow the index
Shows that operator[] on a map inserts, while find leaves the container untouched.
<iostream>
<string>
<map>
<set>
int main() {
std::map<std::string, std::set<int>> index{{"cat", {1, 3}}};
std::cout << "size before: " << index.size() << '\n';
std::cout << "hits for zebra: " << index["zebra"].size() << '\n';
std::cout << "size after: " << index.size() << '\n';
auto it = index.find("moose");
std::cout << "moose found: " << (it != index.end()) << '\n';
std::cout << "size still: " << index.size() << '\n';
for (const auto& entry : index) std::cout << '[' << entry.first << ']';
std::cout << '\n';
}
Example explained
Line 1index["zebra"] has to return a reference to a set, so when the key is absent it default-constructs one and stores it; size goes from 1 to 2.
Line 2That new set is empty, so size() == 0 makes the failed search look correct while the index has quietly gained a word.
Line 3index.find("moose") returns end() and changes nothing, which is the behaviour a read-only lookup needs.
Line 4The final key dump proves zebra is now indexed even though it appears on no line.
Important notes
std::isalnum and std::tolower take an int and have undefined behaviour on negative values, so convert each character to unsigned char first; plain char is often signed and UTF-8 bytes above 127 will trip it.
References and iterators into a std::map or std::set stay valid when you insert more elements, so caching auto& postings = index[key] across further insertions is safe here in a way it would not be with a vector.
Common mistakes
Using index[term] to answer a search: every miss inserts a word with an empty posting list, so the index keeps growing, size() lies, and the printed report lists words that appear nowhere in the text.
Normalizing only while building the index: a query for "the" then fails to match the stored key that came from "The", and a query typed as "cat," matches nothing at all.
Storing postings in a std::vector<int> instead of a std::set<int>: a word appearing twice on one line records that line twice, and you have to add a sort plus unique pass before the output is usable.
Try it yourself
Change, predict, then run
Copy the main program and add a std::map<std::string,int> that counts every occurrence of a word rather than every line, then print the words whose occurrence count exceeds the size of their posting set, which are exactly the words repeated inside a single line.
Open the C++ workspaceCheck your understanding
You build the index with index[normalize(w)].insert(lineNo), then answer searches with if (!index[term].empty()). The text never changes, yet index.size() keeps growing as users search. Why?
- operator[] must return a reference, so it default-constructed and stored an empty set for every term searched for but not present
- std::set::insert reallocates and duplicates nodes as the posting lists grow
- The map rehashed once it passed its load factor, which changed the value reported by size()
- normalize returned an empty string for the queries, and the empty key was appended once per search
Show answer
operator[] on std::map is an inserting operation: it hands back a reference to the mapped value, so a missing key has to be created first, and each failed search leaves behind a word with an empty posting list. Use find, count or contains for read-only lookups. Rehashing is not a candidate: std::map is a balanced tree with no load factor, and its size changes only through insertion or erasure. The empty-key idea also fails, because a single empty key would be inserted once and then reused.