An associative container organizes elements around keys instead of positional indexes. An std::map stores key-value pairs in key order, providing dictionary-style lookup. Related containers include std::multimap, which permits duplicate keys, and std::set, which stores ordered keys without mapped values. section 7.0 section 7.4
Use associative containers to:
- Query or insert map elements with operator[], while using at when a failed query must not create an element. section 7.4
- Represent multiple values with std::pair, std::tuple, or structured bindings. section 7.4
- Search ordered containers efficiently with lower_bound, upper_bound, and equal_range. section 7.2.2
Answer Smash
A dictionary maps clue words to definitions for a word-overlap game. Searching with equal_range helps find a word whose beginning matches a later stem; a multimap can retain several entries for one key. section 7.0 section 7.2.2
Listing 7.8 Finding an overlapping word more efficiently
std::pair<std::string, int> find_overlapping_word(std::string word,
const std::map<std::string, std::string>& dictionary)
{
size_t offset = 1;
while (offset < word.size())
{
auto stem = word.substr(offset);
auto [lb, ub] = dictionary.equal_range(stem); #1
if (lb != dictionary.end() &&
stem == lb->first.substr(0, stem.size())) #2
{
return {lb->first, offset}; #3
}
++offset;
}
return {"", -1};
}
Inspect a complete function that combines equal_range with prefix checking to locate an overlapping dictionary word. section 7.2.2
