- Map (C++ container)
std::mapis a standard
C++container. It is a sorted associative array, which is a data structure which acts like a dynamic one-dimensional array that associates values of one type with values of another type (the two types of values may be the same). [ [http://uw713doc.sco.com/en/SDK_c++/_Intro_map.html Introduction ] ] Specifically, this type of associative array maps objects of type Key to objects of type Data. Typically, the key value is used to identify the element and the data is some sort of value associated with this key. The types of key and data may differ, and the elements of the map are internally sorted from lowest to highest key value. Each key value is unique; if an object is inserted with an already existing key, the object already present in the map is not changed in any way. [http://www.cplusplus.com/reference/stl/map/ map - C++ Reference ] ] A variation on the map, called the multimap, allows keys to be duplicated.
Iterators are not invalidated by insert and erase operations which don't remove the object to which the iterator points. The usual implementation is a
self-balancing binary search tree(but any other data structure that respects the complexity constraints can be used, like a skip list).
* Searching for an element takes "O(log n)" time
* Inserting a new element takes "O(log n)" time plus the time to call malloc once
* Incrementing/decrementing an iterator takes "O(log n)" time
* Iterating through every element of a map takes "O(n)" time
* Removing a single map element takes "O(log n)" time
* Copying an entire map takes "O(n log n)" time. [ [http://uw713doc.sco.com/en/SDK_c++/_Perform_map.html Performance ] ]
Maps 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 (although maps are able to directly access elements with the
The map is declared in this format:
map <"key_type", "value_type" [, "comparing_option" [, "memory_allocator"] ] > "map_name"
The following code demonstrates how to use the
mapto count occurrences of words. It uses the word as the key and the count as the value.
When executed, the user first types a series of words separated by spaces, and a word "end" to signify the end of input; then the user can input words to query how many times each word occurred in the previous series.
The above example also demonstrates that the operator "  " inserts new objects (using the default constructor) in the map if there isn't one associated with the key. So integral types are zero-initialized, strings are initialized to empty strings, etc.
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:
In the above example, five elements are entered using the insertion function, and then the first element is deleted. Then, the size of the map is output. Next, the user is prompted for a key to search for. Using the iterator, the find function searches for an element with the given key. If it finds the key, the program prints the element's value. If it does not find it, an iterator to the end of the map is returned and it outputs that the key could not be found. Finally all the elements in the tree are erased.
Below is an example of looping through a map to display all keys and values using iterators:
This will output the keys and values of the entire map.
*Standard Template Library containers
Wikimedia Foundation. 2010.
Look at other dictionaries:
Container Corporation of India — logo Container Corporation of India Ltd. (Concor) is a Navratna Public Sector undertaking under the Indian Ministry of Railways. Incorporated in March 1988 under the Companies Act, Concor commenced operations in November 1989 taking over an… … Wikipedia
map (C++) — Not to be confused with Map (higher order function). C++ Standard Library fstream iomanip ios iostream sstre … Wikipedia
Container ship — Two container ships pass in San Francisco Bay Class overview Name: Container ship Subclasses: (1) Geared or gearless … Wikipedia
Container deposit legislation in the United States — Deposit notice on a bottle sold in Continental U.S., indicating the container s deposit value in various states. The United States container deposit legislation is popularly called bottle bills after the Oregon Bottle Bill, the first such… … Wikipedia
Container (data structure) — For the abstract notion of containers in Type theory, see Container (Type theory). In computer science, a container is a class, a data structure, or an abstract data type (ADT) whose instances are collections of other objects. In other… … Wikipedia
Container (type theory) — In type theory, containers are abstractions which permit various different collection types , such as lists and trees, to be represented in a uniform way. A (unary) container is defined by a type of shapes S and a type family of positions P,… … Wikipedia
GSA weapons container — n. a GSA vault or map and plan container used to store weapons and requiring a minimum protection of a Group 1 lock … Locksmith dictionary
List of Sly Cooper characters — This is a list of characters in the Sly Cooper video game series. Contents 1 Allies 1.1 Cooper Gang 1.1.1 Sly Cooper 1.1.2 Bentley … Wikipedia
Chesapeake and Delaware Canal — Map of the C D Canal from The Chesapeake to Delaware Bays … Wikipedia
Häfen von Auckland — Container und Containerkräne auf Fergusson Wharf … Deutsch Wikipedia