map Class

Used for the storage and retrieval of data from a collection in which each element is a pair that has both a data value and a sort key. The value of the key is unique and is used to automatically sort the data.

The value of an element in a map can be changed directly. The key value is a constant and cannot be changed. Instead, key values associated with old elements must be deleted, and new key values must be inserted for new elements.

template <
   class Key, 
   class Type, 
   class Traits = less<Key>, 
   class Allocator=allocator<pair <const Key, Type> > 
> class map;

Parameters

• Key
  The key data type to be stored in the map.

• Type
  The element data type to be stored in the map.

• Traits
  The type that provides a function object that can compare two element values as sort keys to determine their relative order in the map. This argument is optional and the binary predicate less<Key> is the default value.

• Allocator
  The type that represents the stored allocator object that encapsulates details about the map's allocation and deallocation of memory. This argument is optional and the default value is allocator<pair<constKey*,* Type> >.

Remarks

The Standard Template Library (STL) map class is:

• A container of variable size that efficiently retrieves element values based on associated key values.

• Reversible, because it provides bidirectional iterators to access its elements.

• Sorted, because its elements are ordered by key values according to a specified comparison function.

• Unique. because each of its elements must have a unique key.

• A pair-associative container, because its element data values are distinct from its key values.

• A template class, because the functionality it provides is generic and independent of element or key type. The data types used for elements and keys are specified as parameters in the class template together with the comparison function and allocator.

The iterator provided by the map class is a bidirectional iterator, but the insert and map class member functions have versions that take as template parameters a weaker input iterator, whose functionality requirements are fewer than those guaranteed by the class of bidirectional iterators. The different iterator concepts are related by refinements in their functionality. Each iterator concept has its own set of requirements, and the algorithms that work with it must be limited by those requirements. An input iterator may be dereferenced to refer to some object and may be incremented to the next iterator in the sequence.

We recommend that you base the choice of container type on the kind of searching and inserting that is required by the application. Associative containers are optimized for the operations of lookup, insertion, and removal. The member functions that explicitly support these operations perform them in a worst-case time that is proportional to the logarithm of the number of elements in the container. Inserting elements invalidates no iterators, and removing elements invalidates only those iterators that specifically pointed to the removed elements.

We recommend that you make the map the associative container of choice when conditions that associate values with keys are satisfied by the application. A model for this kind of structure is an ordered list of uniquely occurring key words that have associated string values that provide definitions. If a word has more than one correct definition, so that key is not unique, then a multimap would be the container of choice. If just the list of words is being stored, then a set would be the appropriate container. If multiple occurrences of the words are allowed, then a multiset would be appropriate.

The map orders the elements it controls by calling a stored function object of type key_compare. This stored object is a comparison function that is accessed by calling the key_comp method. In general, any two given elements are compared to determine whether one is less than the other or whether they are equivalent. As all elements are compared, an ordered sequence of non-equivalent elements is created.

Note

The comparison function is a binary predicate that induces a strict weak ordering in the standard mathematical sense. A binary predicate f(x,y) is a function object that has two argument objects x and y, and a return value of true or false. An ordering imposed on a set is a strict weak ordering if the binary predicate is irreflexive, antisymmetric, and transitive, and if equivalence is transitive, where two objects x and y are defined to be equivalent when both f(x,y)and f(y,x) are false. If the stronger condition of equality between keys replaces that of equivalence, the ordering becomes total (in the sense that all the elements are ordered with regard to one other), and the keys matched will be indiscernible from one other.

Members

Constructors

map	Constructs a list of a specific size or with elements of a specific value or with a specific allocator or as a copy of some other map.

Typedefs

allocator_type	A typedef for the allocator class for the map object.
const_iterator	A typedef for a bidirectional iterator that can read a const element in the map.
const_pointer	A typedef for a pointer to a const element in a map.
const_reference	A typedef for a reference to a const element stored in a map for reading and performing const operations.
const_reverse_iterator	A type that provides a bidirectional iterator that can read any const element in the map.
difference_type	A signed integer typedef for the number of elements of a map in a range between elements pointed to by iterators.
iterator	A typedef for a bidirectional iterator that can read or modify any element in a map.
key_compare	A typedef for a function object that can compare two sort keys to determine the relative order of two elements in the map.
key_type	A typedef for the sort key stored in each element of the map.
mapped_type	A typedef for the data stored in each element of a map.
pointer	A typedef for a pointer to a const element in a map.
reference	A typedef for a reference to an element stored in a map.
reverse_iterator	A typedef for a bidirectional iterator that can read or modify an element in a reversed map.
size_type	An unsigned integer typedef for the number of elements in a map
value_type	A typedef for the type of object stored as an element in a map.

Member Functions

at	Finds an element with a specified key value.
begin	Returns an iterator that points to the first element in the map.
cbegin	Returns a const iterator that points to the first element in the map.
cend	Returns a const past-the-end iterator.
clear	Erases all the elements of a map.
count	Returns the number of elements in a map whose key matches the key specified in a parameter.
crbegin	Returns a const iterator that points to the first element in a reversed map.
crend	Returns a const iterator that points to the location after the last element in a reversed map.
emplace	Inserts an element constructed in place into the map.
emplace_hint	Inserts an element constructed in place into the map, with a placement hint.
empty	Returns true if a map is empty.
end	Returns the past-the-end iterator.
equal_range	Returns a pair of iterators. The first iterator in the pair points to the first element in a map with a key that is greater than a specified key. The second iterator in the pair points to the first element in the map with a key that is equal to or greater than the key.
erase	Removes an element or a range of elements in a map from the specified positions.
find	Returns an iterator that points to the location of an element in a map that has a key equal to a specified key.
get_allocator	Returns a copy of the allocator object that is used to construct the map.
insert	Inserts an element or a range of elements into the map at a specified position.
key_comp	Returns a copy of the comparison object that used to order keys in a map.
lower_bound	Returns an iterator to the first element in a map that has a key value that is equal to or greater than that of a specified key.
max_size	Returns the maximum length of the map.
rbegin	Returns an iterator that points to the first element in a reversed map.
rend	Returns an iterator that points to the location after the last element in a reversed map.
size	Returns the number of elements in the map.
swap	Exchanges the elements of two maps.
upper_bound	Returns an iterator to the first element in a map that has a key value that is greater than that of a specified key.
value_comp	Retrieves a copy of the comparison object that is used to order element values in a map.

Operators

operator[]	Inserts an element into a map with a specified key value.
operator=	Replaces the elements of a map with a copy of another map.

Requirements

Header: <map>

Namespace: std

See Also

Reference

Thread Safety in the C++ Standard Library

Standard Template Library

Concepts

Containers

Other Resources

<map> Members