{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": true }, "source": [ "

Table of Contents

\n", "
" ] }, { "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 " ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "std::string text = \"The k-medoids algorithm is a clustering algorithm related to the k-means algorithm and the \\\n", " medoidshift algorithm Both the k-means and k-medoids algorithms are partitional breaking the dataset up \\\n", " into groups and both attempt to minimize the distance between points labeled to be in a cluster and a \\\n", " point designated as the center of that cluster\";" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "// Create a string stream from the string \n", "std::stringstream s(text);\n", "std::string word;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- count the number of times each word occurs in the above string" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "// empty map from string to size_t\n", "// This map stores elements in which the keys are strings and the values are size_ts\n", "std::map word_count;" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "// Use a string-stream to fetch and increment the counter for word\n", "for (int i = 0; s >> word; i++){\n", " ++word_count[word];\n", "}" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "When we fetch an element from a map, we get an object of type **pair**. Briefly, a **pair** is a template type that holds two (**public**) data elements named **first** and **second**. The **pairs** used by **map** have a **first** member that is the key and a **second** member that is the corresponding value." ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Both occurs 1 time\n", "The occurs 1 time\n", "a occurs 3 times\n", "algorithm occurs 4 times\n", "algorithms occurs 1 time\n", "and occurs 4 times\n", "are occurs 1 time\n", "as occurs 1 time\n", "attempt occurs 1 time\n", "be occurs 1 time\n", "between occurs 1 time\n", "both occurs 1 time\n", "breaking occurs 1 time\n", "center occurs 1 time\n", "cluster occurs 2 times\n", "clustering occurs 1 time\n", "dataset occurs 1 time\n", "designated occurs 1 time\n", "distance occurs 1 time\n", "groups occurs 1 time\n", "in occurs 1 time\n", "into occurs 1 time\n", "is occurs 1 time\n", "k-means occurs 2 times\n", "k-medoids occurs 2 times\n", "labeled occurs 1 time\n", "medoidshift occurs 1 time\n", "minimize occurs 1 time\n", "of occurs 1 time\n", "partitional occurs 1 time\n", "point occurs 1 time\n", "points occurs 1 time\n", "related occurs 1 time\n", "that occurs 1 time\n", "the occurs 6 times\n", "to occurs 3 times\n", "up occurs 1 time\n" ] } ], "source": [ "// for each element in the map print the results\n", "for (const auto &w : word_count){\n", " std::cout << w.first << \" occurs \" << w.second << ((w.second > 1) ? \" times\" : \" time\") << std::endl;\n", "}" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "xeus C++14", "language": "", "name": "xeus-cling-cpp14" }, "language_info": { "codemirror_mode": "text/x-c++src", "file_extension": ".cpp", "mimetype": "text/x-c++src", "name": "c++", "version": "" }, "toc": { "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": false, "toc_cell": true, "toc_position": {}, "toc_section_display": "block", "toc_window_display": false } }, "nbformat": 4, "nbformat_minor": 2 }