Chapter 15 - Associative Container Notes

Set / Unordered Set

std::set - cppreference.comen.cppreference.com

Characteristics

• Internally represented as either a hash set, or a red-black tree

• Contains a set of unique objects

• Elements are referred to as keys

Good for...

• Insertion is very fast, this is O(1) time for unordered sets, and O(log N) for ordered sets.

• Checking if an element already exists in a set, this is O(1) time for unordered sets, and O(log N) for ordered sets.

• In other words, lookups are very fast.

Not good for...

• If you want to store multiple of the same element in the container

Usage

Creating and Adding Elements

#include<iostream>
#include<set>
#include<string>

int main()
{
    std::set<std::string> setOfStrings;
    
    // Lets insert four elements
    setOfStrings.insert("first");
    setOfStrings.insert("second");
    setOfStrings.insert("third");
    setOfStrings.insert("first");
    
    // Only 3 elements will be inserted
    std::cout<< "Set size = "<< setOfStrings.size()<<std::endl;
    
    // Iterate through all the elements in a set and display the value.
    for (auto it = setOfStrings.begin(); it != setOfStrings.end(); ++it)
        std::cout << ' ' << *it;
    std::cout << std::endl;
}

Search for an Element in a Set

#include<iostream>
#include<set>
#include<string>

int main()
{
    std::set<std::string> setOfStrings;
    
    // Lets insert four elements
    setOfStrings.insert("first");
    setOfStrings.insert("second");
    setOfStrings.insert("third");
    setOfStrings.insert("first");
    
    // Search for element in set using find member function
    auto it = setOfStrings.find("second");
    if (it != setOfStrings.end())
        std::cout<<"'first' found"<<std::endl;
    else
        std::cout<<"'first' not found"<<std::endl;
    
    // Search for element in set using find member function
    it = setOfStrings.find("fourth");
    if (it != setOfStrings.end())
        std::cout<<"'fourth'  found"<<std::endl;
    else
        std::cout<<"'fourth' not found"<<std::endl;
}

Remove Elements from a Set

#include<iostream>
#include<set>
#include<string>
int main()
{
    std::set<std::string> setOfStrings;
    
    // Lets insert four elements
    setOfStrings.insert("first");
    setOfStrings.insert("second");
    setOfStrings.insert("third");
    setOfStrings.insert("first");
    
    // Iterate through all the elements in a set and display the value.
    for (auto it = setOfStrings.begin(); it != setOfStrings.end(); ++it)
        std::cout << ' ' << *it;
    std::cout<<std::endl;
    
    setOfNumbers.erase("third");
    
    // Iterate through all the elements in a set and display the value.
    for (auto it = setOfStrings.begin(); it != setOfStrings.end(); ++it)
        std::cout << ' ' << *it;
    std::cout<<std::endl;
}

Map / Unordered Map

std::map - cppreference.comen.cppreference.com

Characteristics

• Internally represented as either a hash map, or a red-black tree

• Similar in principle to a set, except instead of a single element, it stores a key-value pair.

• As with sets, each key in the container is unique.

Good for...

• Mapping certain values to another, e.g. storing customers' ages, keyed by their name.

Not good for...

• When the data you want to store has a many-to-many, or many-to-one relationship, since keys have to be unique.

Usage

#include <iostream>
#include <unordered_map>
 
int main()
{
    // Declaring umap to be of <string, double> type
    // key will be of string type and mapped value will
    // be of double type
    std::unordered_map<string, double> umap;
 
    // inserting values by using [] operator
    umap["PI"] = 3.14;
    umap["root2"] = 1.414;
    umap["root3"] = 1.732;
    umap["log10"] = 2.302;
    umap["loge"] = 1.0;
 
    // inserting value by insert function
    umap.insert(make_pair("e", 2.718));
 
    std::string key = "PI";
 
    // If key not found in map iterator to end is returned
    if (umap.find(key) == umap.end())
        cout << key << " not found\n\n";
 
    // If key found then iterator to that key is returned
    else
        cout << "Found " << key << "\n\n";
 
    key = "lambda";
    if (umap.find(key) == umap.end())
        std::cout << key << " not found\n";
    else
        std::cout << "Found " << key << std::endl;
 
    // iterating over all value of umap
    std::unordered_map<string, double>::iterator itr;
    std::cout << "\nAll Elements : \n";
    for (itr = umap.begin(); itr != umap.end(); itr++)
    {
        // itr works as a pointer to pair<string, double>
        // type itr->first stores the key part  and
        // itr->second stroes the value part
        cout << itr->first << "  " << itr->second << endl;
     }
}