"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# STL Associative Containers and Iterators"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"In the previous post, we explored two of the STL's sequence containers:\n",
"\n",
"- **vector**\n",
"- **deque**\n",
"\n",
"These containers are ideally suited for situations where we need to keep track of an ordered list of elements. However, representing data in ordered lists is not optimal in many applications. \n",
"\n",
"In this installment of **Play interactively with C++**, we will explore **STL Associative Containers**.\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Associative and Sequential containers differ from one another in a fundamental way:\n",
"- Elements in an associative container are stored and retrieved by key.\n",
"- Elements in a sequential container are stored and accessed sequentially by their position in the container\n",
"\n",
"The **Associative container** types are:\n",
"\n",
"| Elements Ordered by Key | |\n",
"|-------------------------|------------------------------------------------|\n",
"| `map` | Associative array--holds key-value pairs |\n",
"| `set` | Container in which the key is the value |\n",
"| `multimap` | `map` in which a key can appear multiple times |\n",
"| `multiset` | `set` in which a key can appear multiple times |\n",
"\n",
"\n",
"| Unordered Collections | |\n",
"|-----------------------|-----------------------------------------------|\n",
"| `unordered_map` | `map` organized by a hash function |\n",
"| `unordered_set` | `set` organized by a hash function |\n",
"| `unordered_multimap` | Hashed `map`--keys can appear multiple times |\n",
"| `unordered_multiset` | Hashed `set` --keys can appear multiple times |"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## Using An Associative Container\n",
"\n",
"A **`map`** is a collection of key-value pairs. For example, each pair might contain a book's author as a key and a book's name as its value. We speak of such a data structure as *mapping authors to books*. \n",
"\n",
"The `map` type is often referred to as an **associative array**. An associative array is like a normal *array* except that its subscripts don't have integers. Values in a `map` are found by a key rather than by their position. \n",
"\n",
"In contrast, a **`set`** is simply a collection of keys. A `set` is most useful when we simply want to know whether a value is present."
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"### Using a `map`"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"To illustrate how to use a map, we are going to write a **word-counting** program."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"#include \n",
"#include \n",
"#include \n",
"#include