# Chapter 20 - Code Examples

## Instantiating&#x20;

To instantiate an `std::map` or `std::multimap` you need to specify the **key type** and the **value type**.

```cpp
std::map<int, std::string> intToStringMap;
std::map<std::string, std::string> stringToStringMap;
```

{% hint style="info" %}
Most functions in `map` and `multimap` work in a similar fashion - they accept similar parameters and return similar value types.&#x20;

Knowing how to use one will give you an intuitive sense of how to use the other, much like `set` and `multiset`.&#x20;
{% endhint %}

## Inserting&#x20;

### Using the `insert` member function&#x20;

```cpp
std::map<int, std::string> intToStringMap;
intToStringMap.insert(std::make_pair(-1, "Minus One"));
```

The `std::make_pair` function creates a key-value pair, the first parameter being the key and the second the value - this returns an `std::pair` type.&#x20;

Alternatively you can also directly supply an `std::pair` object to be inserted:

```cpp
intToStringMap.insert(std::pair<int, std::string>(10, "Ten"));
```

### Using array-like syntax

```cpp
intToStringMap[100] = "Hundred";
```

This is the most user friendly and generally most popular approach.&#x20;

## Finding and Lookups&#x20;

### The `.find()` member method

All associative containers (`std::map`, `std::map`, etc) feature a member function called `.find()` that allows you to search for a given key.

The result for `.find()` is always an iterator:

```cpp
std::map<int, std::string>::const_iterator result = mapIntToString.find(key);
```

If the key was not found in the container, it will return `container.end()`; therefore you should always check for this before using the returned iterator to access the underlying value.

```cpp
if (result != mapIntToString.end()) {
    std::cout << "Key: " << result->first 
              << " has value: " << result->second << std::endl;
} else {
    std::cout << "Key was not found" << std::endl;
}
```

### Finding in a `multimap`

An `std::multimap` opens the possibility of storing **multiple pairs with the same key**.&#x20;

The `.find()` member method returns an **iterator to the first pair** for the given key.

Incrementing this iterator gives access to consequently placed values, possibly with the same key.

Use the `.count()` member function to determine how many times to increment the iterator to enumerate over all keys of a particular value.&#x20;

```cpp
auto pairFound = mmapIntToStr.find(key);

// Check if find() succeeded
if (pairFound != mmapIntToStr.end()) {
    // Find the number of pairs that have the same supplied key
    int numPairsInMap = mmapIntToStr.count(1000);
    
    // Stay within bounds
    for (int counter = 0; counter < numPairsInMap; counter++) 
    {
        cout << "Key: " << pairFound->first; // key
        cout << ", Value [" << counter << "] = ";
        cout << pairFound->second << endl; // value
        
        pairFound++;
    }
}
else {
   cout << "Element not found in the multimap";
}
```

## Erasing&#x20;

### Using the `.erase()` member function

The `.erase()` member function can be invoked with either:

* A key value&#x20;
* An iterator pointing to an element in the `std::map`
* A range of elements described by two iterators&#x20;

## Conclusion&#x20;

### Sequential Containers

* Store elements in the order they were inserted&#x20;
* Not necessarily contiguously in memory (this is only for `std::vector`)
* `std::vector`, `std::deque`, `std::list`
* Dynamic array, chunks of dynamic arrays, linked lists&#x20;

### Associative Containers&#x20;

* They are not stored sequentially in the order they were inserted&#x20;
* `std::set`, `std::map`, `std::unordered_set`, `std::unordered_map`
* Binary search trees, hash sets/hash maps.&#x20;

### Ordered Containers&#x20;

`std::set` and `std::map` are represented by **binary search trees** internally, which implicitly means that the elements are sorted in some order.&#x20;

While much quicker than `std::vector` or `std::list` when it comes to searching, its performance still scales with the number of inputs, although **logarithmically** as opposed to **linearly**.

### Unordered Containers&#x20;

`std::unordered_set` and `std::unordered_map` are represented by **hash sets** (or **hash tables**) internally.&#x20;

Such containers *generally* promise **constant-time** insertions and searches, independent of the size of the container.&#x20;

As a result, these containers are optimised only for search performance, and are suitable in situations where the order of elements does not matter.
