|
Associative containers (C++)
In C++, associative containers are a group of class templates in the standard library of the C++ programming language that implement ordered associative arrays.[1] Being templates, they can be used to store arbitrary elements, such as integers or custom classes. The following containers are defined in the current revision of the C++ standard: The associative containers are similar to the unordered associative containers in C++ standard library, the only difference is that the unordered associative containers, as their name implies, do not order their elements. DesignCharacteristics
Associative containers are designed to be especially efficient in accessing its elements by their key, as opposed to sequence containers which are more efficient in accessing elements by their position.[1] Associative containers are guaranteed to perform operations of insertion, deletion, and testing whether an element is in it, in logarithmic time – O(log n). As such, they are typically implemented using self-balancing binary search trees and support bidirectional iteration. Iterators and references are not invalidated by insert and erase operations, except for iterators and references to erased elements.The defining characteristic of associative containers is that elements are inserted in a pre-defined order, such as sorted ascending. The associative containers can be grouped into two subsets: maps and sets. A map, sometimes referred to as a dictionary, consists of a key/value pair. The key is used to order the sequence, and the value is somehow associated with that key. For example, a map might contain keys representing every unique word in a text and values representing the number of times that word appears in the text. A set is simply an ascending container of unique elements. As stated earlier, Both maps and sets support bidirectional iterators. For more information on iterators, see Iterators. While not officially part of the STL standard,
PerformanceThe asymptotic complexity of the operations that can be applied to associative containers are as follows:
Overview of functionsThe containers are defined in headers named after the names of the containers, e.g.
UsageThe following code demonstrates how to use the #include <iostream>
#include <map>
int main()
{
std::map<std::string, int> wordcounts;
std::string s;
while (std::cin >> s && s != "end")
{
++wordcounts[s];
}
while (std::cin >> s && s != "end")
{
std::cout << s << ' ' << wordcounts[s] << '\n';
}
return 0;
}
When executed, program lets user type a series of words separated by spaces, and a word "end" to signify the end of input. Then user can input a word to query how many times it has occurred in the previously entered series. The above example also demonstrates that the operator The following example illustrates inserting elements into a map using the insert function and searching for a key using a map iterator and the find function: #include <iostream>
#include <map>
#include <utility> // To use make_pair function
int main()
{
typedef std::map<char, int> MapType;
MapType my_map;
// Insert elements using insert function
my_map.insert(std::pair<char, int>('a', 1));
my_map.insert(std::pair<char, int>('b', 2));
my_map.insert(std::pair<char, int>('c', 3));
// You can also insert elements in a different way like shown below
// Using function value_type that is provided by all standart containers
my_map.insert(MapType::value_type('d', 4));
// Using the utility function make_pair
my_map.insert(std::make_pair('e', 5));
// Using C++11 initializer list
my_map.insert({'f', 6});
//map keys are sorted automatically from lower to higher.
//So, my_map.begin() points to the lowest key value not the key which was inserted first.
MapType::iterator iter = my_map.begin();
// Erase the first element using the erase function
my_map.erase(iter);
// Output the size of the map using size function
std::cout << "Size of my_map: " << my_map.size() << '\n';
std::cout << "Enter a key to search for: ";
char c;
std::cin >> c;
// find will return an iterator to the matching element if it is found
// or to the end of the map if the key is not found
iter = my_map.find(c);
if (iter != my_map.end())
{
std::cout << "Value is: " << iter->second << '\n';
}
else
{
std::cout << "Key is not in my_map" << '\n';
}
// You can clear the entries in the map using clear function
my_map.clear();
return 0;
}
Example shown above demonstrates the usage of some of the functions provided by When program is executed, six elements are inserted using the IteratorsMaps may use iterators to point to specific elements in the container. An iterator can access both the key and the mapped value of an element:[1] // Declares a map iterator
std::map<Key, Value>::iterator it;
// Accesses the Key value
it->first;
// Accesses the mapped value
it->second;
// The "value" of the iterator, which is of type std::pair<const Key, Value>
(*it);
Below is an example of looping through a map to display all keys and values using iterators: #include <iostream>
#include <map>
int main()
{
std::map<std::string, int> data
{
{ "Bobs score", 10 },
{ "Martys score", 15 },
{ "Mehmets score", 34 },
{ "Rockys score", 22 },
// The next values are ignored because elements with the same keys are already in the map
{ "Rockys score", 23 },
{ "Mehmets score", 33 }
};
// Iterate over the map and print out all key/value pairs.
for (const auto& element : data)
{
std::cout << "Who(key = first): " << element.first;
std::cout << " Score(value = second): " << element.second << '\n';
}
// If needed you can iterate over the map with the use of iterator,
// Note that the long typename of the iterator in this case can be replaced with auto keyword
for (std::map<std::string, int>::iterator iter = data.begin(); iter != data.end(); ++iter)
{
std::cout << "Who(key = first): " << iter->first;
std::cout << " Score(value = second): " << iter->second << '\n';
}
return 0;
}
For compiling above sample on GCC compiler, must use specific standard select flag. g++ -std=c++11 source.cpp -o src
This will output the keys and values of the entire map, sorted by keys. See also
References
|
![[icon]](File:Wiki_letter_w_cropped.svg){kind=small}
Portal di Ensiklopedia Dunia
