Namespaces
Variants
Views
Actions

Difference between revisions of "cpp/container/map"

From cppreference.com
< cpp‎ | container
(Added the todo block regarding missing template parameter descriptions.)
m (fmt)
Line 3: Line 3:
 
{{dcl begin}}
 
{{dcl begin}}
 
{{dcl header|map}}
 
{{dcl header|map}}
{{dcl | num=1|1=
+
{{dcl|num=1|1=
 
template<
 
template<
 
     class Key,
 
     class Key,
Line 10: Line 10:
 
     class Allocator = std::allocator<std::pair<const Key, T>>
 
     class Allocator = std::allocator<std::pair<const Key, T>>
 
> class map;
 
> class map;
}}  
+
}}
 
{{dcl|num=2|since=c++17|1=
 
{{dcl|num=2|since=c++17|1=
 
namespace pmr {
 
namespace pmr {
    template< class Key, class T, class Compare = std::less<Key> >
+
template<
    using map = std::map<
+
    class Key,
        Key, T, Compare,
+
    class T,
        std::pmr::polymorphic_allocator<std::pair<const Key, T>>
+
    class Compare = std::less<Key>
    >;
+
> using map = std::map<Key, T, Compare,
 +
                      std::pmr::polymorphic_allocator<std::pair<const Key, T>>>;
 
}
 
}
 
}}
 
}}
 
{{dcl end}}
 
{{dcl end}}
  
{{tt|std::map}} is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function {{tt|Compare}}.  Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as [[enwiki:Red–black_tree|red-black trees]].
+
{{tt|std::map}} is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function {{tt|Compare}}.  Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as {{enwiki|Red–black_tree|red-black trees}}.
  
 
Everywhere the standard library uses the {{named req|Compare}} requirements, uniqueness is determined by using the equivalence relation. In imprecise terms, two objects {{c|a}} and {{c|b}} are considered equivalent (not unique) if neither compares less than the other: {{c|!comp(a, b) && !comp(b, a)}}.
 
Everywhere the standard library uses the {{named req|Compare}} requirements, uniqueness is determined by using the equivalence relation. In imprecise terms, two objects {{c|a}} and {{c|b}} are considered equivalent (not unique) if neither compares less than the other: {{c|!comp(a, b) && !comp(b, a)}}.
Line 33: Line 34:
 
===Member types===
 
===Member types===
 
{{dsc begin}}
 
{{dsc begin}}
{{dsc hitem | Member type | Definition}}
+
{{dsc hitem|Member type|Definition}}
{{dsc inc | cpp/container/dsc key_type | map}}
+
{{dsc inc|cpp/container/dsc key_type|map}}
{{dsc inc | cpp/container/dsc mapped_type | map}}
+
{{dsc inc|cpp/container/dsc mapped_type|map}}
{{dsc inc | cpp/container/dsc value_type | map}}
+
{{dsc inc|cpp/container/dsc value_type|map}}
{{dsc inc | cpp/container/dsc size_type | map}}
+
{{dsc inc|cpp/container/dsc size_type|map}}
{{dsc inc | cpp/container/dsc difference_type | map}}
+
{{dsc inc|cpp/container/dsc difference_type|map}}
{{dsc inc | cpp/container/dsc key_compare | map}}
+
{{dsc inc|cpp/container/dsc key_compare|map}}
{{dsc inc | cpp/container/dsc allocator_type | map}}
+
{{dsc inc|cpp/container/dsc allocator_type|map}}
{{dsc inc | cpp/container/dsc reference | map}}
+
{{dsc inc|cpp/container/dsc reference|map}}
{{dsc inc | cpp/container/dsc const_reference | map}}
+
{{dsc inc|cpp/container/dsc const_reference|map}}
{{dsc inc | cpp/container/dsc pointer | map}}
+
{{dsc inc|cpp/container/dsc pointer|map}}
{{dsc inc | cpp/container/dsc const_pointer | map}}
+
{{dsc inc|cpp/container/dsc const_pointer|map}}
{{dsc inc | cpp/container/dsc iterator | map}}
+
{{dsc inc|cpp/container/dsc iterator|map}}
{{dsc inc | cpp/container/dsc const_iterator | map}}
+
{{dsc inc|cpp/container/dsc const_iterator|map}}
{{dsc inc | cpp/container/dsc reverse_iterator | map}}
+
{{dsc inc|cpp/container/dsc reverse_iterator|map}}
{{dsc inc | cpp/container/dsc const_reverse_iterator | map}}
+
{{dsc inc|cpp/container/dsc const_reverse_iterator|map}}
{{dsc inc | cpp/container/dsc node_type | map}}
+
{{dsc inc|cpp/container/dsc node_type|map}}
{{dsc inc | cpp/container/dsc insert_return_type | map}}
+
{{dsc inc|cpp/container/dsc insert_return_type|map}}
 
{{dsc end}}
 
{{dsc end}}
  
 
===Member classes===
 
===Member classes===
 
{{dsc begin}}
 
{{dsc begin}}
{{dsc inc | cpp/container/dsc value_compare | map}}
+
{{dsc inc|cpp/container/dsc value_compare|map}}
 
{{dsc end}}
 
{{dsc end}}
  
 
===Member functions===
 
===Member functions===
 
{{dsc begin}}
 
{{dsc begin}}
{{dsc inc | cpp/container/dsc constructor | map}}
+
{{dsc inc|cpp/container/dsc constructor|map}}
{{dsc inc | cpp/container/dsc destructor | map}}
+
{{dsc inc|cpp/container/dsc destructor|map}}
{{dsc inc | cpp/container/dsc operator{{=}} | map}}
+
{{dsc inc|cpp/container/dsc operator{{=}}|map}}
{{dsc inc | cpp/container/dsc get_allocator | map}}
+
{{dsc inc|cpp/container/dsc get_allocator|map}}
  
{{dsc h2 | Element access}}
+
{{dsc h2|Element access}}
{{dsc inc | cpp/container/dsc at | map}}
+
{{dsc inc|cpp/container/dsc at|map}}
{{dsc inc | cpp/container/dsc operator_at | map}}
+
{{dsc inc|cpp/container/dsc operator_at|map}}
  
{{dsc h2 | Iterators}}
+
{{dsc h2|Iterators}}
{{dsc inc | cpp/container/dsc begin | map}}
+
{{dsc inc|cpp/container/dsc begin|map}}
{{dsc inc | cpp/container/dsc end | map}}
+
{{dsc inc|cpp/container/dsc end|map}}
{{dsc inc | cpp/container/dsc rbegin | map}}
+
{{dsc inc|cpp/container/dsc rbegin|map}}
{{dsc inc | cpp/container/dsc rend | map}}
+
{{dsc inc|cpp/container/dsc rend|map}}
  
{{dsc h2 | Capacity}}
+
{{dsc h2|Capacity}}
{{dsc inc | cpp/container/dsc empty | map}}
+
{{dsc inc|cpp/container/dsc empty|map}}
{{dsc inc | cpp/container/dsc size | map}}
+
{{dsc inc|cpp/container/dsc size|map}}
{{dsc inc | cpp/container/dsc max_size | map}}
+
{{dsc inc|cpp/container/dsc max_size|map}}
  
{{dsc h2 | Modifiers}}
+
{{dsc h2|Modifiers}}
{{dsc inc | cpp/container/dsc clear | map}}
+
{{dsc inc|cpp/container/dsc clear|map}}
{{dsc inc | cpp/container/dsc insert | map}}
+
{{dsc inc|cpp/container/dsc insert|map}}
{{dsc inc | cpp/container/dsc insert_or_assign | map}}
+
{{dsc inc|cpp/container/dsc insert_or_assign|map}}
{{dsc inc | cpp/container/dsc emplace | map}}
+
{{dsc inc|cpp/container/dsc emplace|map}}
{{dsc inc | cpp/container/dsc emplace_hint | map}}
+
{{dsc inc|cpp/container/dsc emplace_hint|map}}
{{dsc inc | cpp/container/dsc try_emplace | map}}
+
{{dsc inc|cpp/container/dsc try_emplace|map}}
{{dsc inc | cpp/container/dsc erase | map}}
+
{{dsc inc|cpp/container/dsc erase|map}}
{{dsc inc | cpp/container/dsc swap | map}}
+
{{dsc inc|cpp/container/dsc swap|map}}
{{dsc inc | cpp/container/dsc extract | map}}
+
{{dsc inc|cpp/container/dsc extract|map}}
{{dsc inc | cpp/container/dsc merge | map}}
+
{{dsc inc|cpp/container/dsc merge|map}}
  
{{dsc h2 | Lookup}}
+
{{dsc h2|Lookup}}
{{dsc inc | cpp/container/dsc count | map}}
+
{{dsc inc|cpp/container/dsc count|map}}
{{dsc inc | cpp/container/dsc find | map}}
+
{{dsc inc|cpp/container/dsc find|map}}
{{dsc inc | cpp/container/dsc contains | map}}
+
{{dsc inc|cpp/container/dsc contains|map}}
{{dsc inc | cpp/container/dsc equal_range | map}}
+
{{dsc inc|cpp/container/dsc equal_range|map}}
{{dsc inc | cpp/container/dsc lower_bound | map}}
+
{{dsc inc|cpp/container/dsc lower_bound|map}}
{{dsc inc | cpp/container/dsc upper_bound | map}}
+
{{dsc inc|cpp/container/dsc upper_bound|map}}
  
{{dsc h2 | Observers}}
+
{{dsc h2|Observers}}
{{dsc inc | cpp/container/dsc key_comp | map}}
+
{{dsc inc|cpp/container/dsc key_comp|map}}
{{dsc inc | cpp/container/dsc value_comp | map}}
+
{{dsc inc|cpp/container/dsc value_comp|map}}
 
{{dsc end}}
 
{{dsc end}}
  
 
===Non-member functions===
 
===Non-member functions===
 
{{dsc begin}}
 
{{dsc begin}}
{{dsc inc | cpp/container/dsc operator_cmp | map}}
+
{{dsc inc|cpp/container/dsc operator_cmp|map}}
{{dsc inc | cpp/container/dsc swap2 | map}}
+
{{dsc inc|cpp/container/dsc swap2|map}}
{{dsc inc | cpp/container/dsc erase_if | map}}
+
{{dsc inc|cpp/container/dsc erase_if|map}}
 
{{dsc end}}
 
{{dsc end}}
  
Line 165: Line 166:
 
}
 
}
 
|output=
 
|output=
1) Initial map: [CPU] = 10; [GPU] = 15; [RAM] = 20;  
+
1) Initial map: [CPU] = 10; [GPU] = 15; [RAM] = 20;
2) Updated map: [CPU] = 25; [GPU] = 15; [RAM] = 20; [SSD] = 30;  
+
2) Updated map: [CPU] = 25; [GPU] = 15; [RAM] = 20; [SSD] = 30;
 
3) m[UPS] = 0
 
3) m[UPS] = 0
4) Updated map: [CPU] = 25; [GPU] = 15; [RAM] = 20; [SSD] = 30; [UPS] = 0;  
+
4) Updated map: [CPU] = 25; [GPU] = 15; [RAM] = 20; [SSD] = 30; [UPS] = 0;
5) After erase: [CPU] = 25; [RAM] = 20; [SSD] = 30; [UPS] = 0;  
+
5) After erase: [CPU] = 25; [RAM] = 20; [SSD] = 30; [UPS] = 0;
6) After erase: [CPU] = 25; [RAM] = 20; [UPS] = 0;  
+
6) After erase: [CPU] = 25; [RAM] = 20; [UPS] = 0;
 
7) m.size() = 3
 
7) m.size() = 3
 
8) Map is empty: true
 
8) Map is empty: true

Revision as of 13:15, 2 February 2023

 
 
 
 
Defined in header <map>
template<

    class Key,
    class T,
    class Compare = std::less<Key>,
    class Allocator = std::allocator<std::pair<const Key, T>>

> class map;
(1)
namespace pmr {

template<
    class Key,
    class T,
    class Compare = std::less<Key>
> using map = std::map<Key, T, Compare,
                       std::pmr::polymorphic_allocator<std::pair<const Key, T>>>;

}
(2) (since C++17)

std::map is a sorted associative container that contains key-value pairs with unique keys. Keys are sorted by using the comparison function Compare. Search, removal, and insertion operations have logarithmic complexity. Maps are usually implemented as red-black trees.

Everywhere the standard library uses the Compare requirements, uniqueness is determined by using the equivalence relation. In imprecise terms, two objects a and b are considered equivalent (not unique) if neither compares less than the other: !comp(a, b) && !comp(b, a).

std::map meets the requirements of Container, AllocatorAwareContainer, AssociativeContainer and ReversibleContainer.

Contents

Template parameters

Member types

Member type Definition
key_type Key[edit]
mapped_type T[edit]
value_type std::pair<const Key, T>[edit]
size_type Unsigned integer type (usually std::size_t)[edit]
difference_type Signed integer type (usually std::ptrdiff_t)[edit]
key_compare Compare[edit]
allocator_type Allocator[edit]
reference value_type&[edit]
const_reference const value_type&[edit]
pointer

Allocator::pointer

(until C++11)

std::allocator_traits<Allocator>::pointer

(since C++11)
[edit]
const_pointer

Allocator::const_pointer

(until C++11)

std::allocator_traits<Allocator>::const_pointer

(since C++11)
[edit]
iterator LegacyBidirectionalIterator to value_type[edit]
const_iterator LegacyBidirectionalIterator to const value_type[edit]
reverse_iterator std::reverse_iterator<iterator>[edit]
const_reverse_iterator std::reverse_iterator<const_iterator>[edit]
node_type (since C++17) a specialization of node handle representing a container node[edit]
insert_return_type (since C++17) type describing the result of inserting a node_type, a specialization of

template<class Iter, class NodeType>
struct /*unspecified*/
{
    Iter     position;
    bool     inserted;
    NodeType node;
};

instantiated with template arguments iterator and node_type.[edit]

Member classes

compares objects of type value_type
(class) [edit]

Member functions

constructs the map
(public member function) [edit]
destructs the map
(public member function) [edit]
assigns values to the container
(public member function) [edit]
returns the associated allocator
(public member function) [edit]
Element access
access specified element with bounds checking
(public member function) [edit]
access or insert specified element
(public member function) [edit]
Iterators
returns an iterator to the beginning
(public member function) [edit]
(C++11)
returns an iterator to the end
(public member function) [edit]
returns a reverse iterator to the beginning
(public member function) [edit]
(C++11)
returns a reverse iterator to the end
(public member function) [edit]
Capacity
checks whether the container is empty
(public member function) [edit]
returns the number of elements
(public member function) [edit]
returns the maximum possible number of elements
(public member function) [edit]
Modifiers
clears the contents
(public member function) [edit]
inserts elements or nodes(since C++17)
(public member function) [edit]
inserts an element or assigns to the current element if the key already exists
(public member function) [edit]
(C++11)
constructs element in-place
(public member function) [edit]
constructs elements in-place using a hint
(public member function) [edit]
inserts in-place if the key does not exist, does nothing if the key exists
(public member function) [edit]
erases elements
(public member function) [edit]
swaps the contents
(public member function) [edit]
(C++17)
extracts nodes from the container
(public member function) [edit]
(C++17)
splices nodes from another container
(public member function) [edit]
Lookup
returns the number of elements matching specific key
(public member function) [edit]
finds element with specific key
(public member function) [edit]
(C++20)
checks if the container contains element with specific key
(public member function) [edit]
returns range of elements matching a specific key
(public member function) [edit]
returns an iterator to the first element not less than the given key
(public member function) [edit]
returns an iterator to the first element greater than the given key
(public member function) [edit]
Observers
returns the function that compares keys
(public member function) [edit]
returns the function that compares keys in objects of type value_type
(public member function) [edit]

Non-member functions

(removed in C++20)(removed in C++20)(removed in C++20)(removed in C++20)(removed in C++20)(C++20)
lexicographically compares the values of two maps
(function template) [edit]
specializes the std::swap algorithm
(function template) [edit]
erases all elements satisfying specific criteria
(function template) [edit]

Deduction guides (since C++17)

Example

#include <iostream>
#include <map>
#include <string>
#include <string_view>
 
void print_map(std::string_view comment, const std::map<std::string, int>& m)
{
    std::cout << comment;
    // iterate using C++17 facilities
    for (const auto& [key, value] : m)
        std::cout << '[' << key << "] = " << value << "; ";
 
// C++11 alternative:
//  for (const auto& n : m)
//      std::cout << n.first << " = " << n.second << "; ";
//
// C++98 alternative
//  for (std::map<std::string, int>::const_iterator it = m.begin(); it != m.end(); it++)
//      std::cout << it->first << " = " << it->second << "; ";
 
    std::cout << '\n';
}
 
int main()
{
    // Create a map of three (string, int) pairs
    std::map<std::string, int> m{{"CPU", 10}, {"GPU", 15}, {"RAM", 20}};
 
    print_map("1) Initial map: ", m);
 
    m["CPU"] = 25; // update an existing value
    m["SSD"] = 30; // insert a new value
    print_map("2) Updated map: ", m);
 
    // using operator[] with non-existent key always performs an insert
    std::cout << "3) m[UPS] = " << m["UPS"] << '\n';
    print_map("4) Updated map: ", m);
 
    m.erase("GPU");
    print_map("5) After erase: ", m);
 
    std::erase_if(m, [](const auto& pair){ return pair.second > 25; });
    print_map("6) After erase: ", m);
    std::cout << "7) m.size() = " << m.size() << '\n';
 
    m.clear();
    std::cout << std::boolalpha << "8) Map is empty: " << m.empty() << '\n';
}

Output:

1) Initial map: [CPU] = 10; [GPU] = 15; [RAM] = 20;
2) Updated map: [CPU] = 25; [GPU] = 15; [RAM] = 20; [SSD] = 30;
3) m[UPS] = 0
4) Updated map: [CPU] = 25; [GPU] = 15; [RAM] = 20; [SSD] = 30; [UPS] = 0;
5) After erase: [CPU] = 25; [RAM] = 20; [SSD] = 30; [UPS] = 0;
6) After erase: [CPU] = 25; [RAM] = 20; [UPS] = 0;
7) m.size() = 3
8) Map is empty: true

Defect reports

The following behavior-changing defect reports were applied retroactively to previously published C++ standards.

DR Applied to Behavior as published Correct behavior
LWG 230 C++98 Key was not required to be CopyConstructible
(a key of type Key might not be able to be constructed)
Key is also required to
be CopyConstructible
LWG 464 C++98 accessing a const map by key was inconvenient at function provided

See also

collection of key-value pairs, hashed by keys, keys are unique
(class template) [edit]