15.9. Unique values with std::setΒΆ

std::set is declared in <set>. It stores unique keys in sorted order. For strings, the default order is lexicographical. This is not insertion order, and elements are not numbered: a set does not have an indexing operator.

Example c192_15_7
 1#include <iostream>
 2#include <set>
 3#include <string>
 4
 5int main() {
 6    std::set<std::string> cities{"San Diego", "Boston", "San Diego"};
 7    auto result = cities.insert("Chicago");
 8    std::cout << std::boolalpha << result.second << '\n';
 9    std::cout << cities.contains("Boston") << '\n';
10    for (const auto& city_name : cities) {
11        std::cout << city_name << '\n';
12    }
13}

insert returns a pair. Its first member is an iterator referring to the stored key; second is true only if a new key was inserted. Trying to insert an existing key leaves the set unchanged. contains is a C++20 member that answers a membership question without changing the container.

find(key) returns an iterator, not a numeric index. Compare it with end() before dereferencing it. Set keys cannot be changed through their iterators: changing a key could break the ordering. Erase the old key and insert a new one instead. erase(key) returns the number of keys removed, which is either zero or one here.

Example c192_set_find
 1#include <iostream>
 2#include <set>
 3#include <string>
 4
 5int main() {
 6    std::set<std::string> cities{"Boston", "Chicago"};
 7    auto position = cities.find("Chicago");
 8    if (position != cities.end()) {
 9        std::cout << *position << '\n';
10    }
11    cities.erase("Boston");
12    std::cout << cities.size() << '\n';
13}

Use a vector when positions or repeated values matter. Use a set when the important operations are membership, insertion, and removal of unique keys. Lookup, insertion, and removal by key take logarithmic time in a std::set. An std::unordered_set is another option when sorted iteration is not needed; it uses hashing and has different ordering and performance guarantees.

We want to open a file and parse its data into our program. What library do we need to include?