# Chapter 15 - Associative Container Notes

## Set / Unordered Set&#x20;

{% embed url="<https://en.cppreference.com/w/cpp/container/set>" %}

### Characteristics&#x20;

* 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.&#x20;
* Checking if an element already exists in a set, this is O(1) time for unordered sets, and O(log N) for ordered sets.&#x20;
* In other words, lookups are very fast.&#x20;

### Not good for...&#x20;

* If you want to store multiple of the same element in the container&#x20;

### Usage&#x20;

#### Creating and Adding Elements

```cpp
#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&#x20;

```cpp
#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&#x20;

```cpp
#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&#x20;

{% embed url="<https://en.cppreference.com/w/cpp/container/map>" %}

### Characteristics&#x20;

* Internally represented as either a hash map, or a red-black tree&#x20;
* 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.&#x20;

### Good for...

* Mapping certain values to another, e.g. storing customers' ages, keyed by their name.&#x20;

### Not good for...&#x20;

* When the data you want to store has a many-to-many, or many-to-one relationship, since keys have to be unique.&#x20;

### Usage&#x20;

```cpp
#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;
     }
}
```
