Difference between revisions of "cpp/container/map"
(Added the todo block regarding missing template parameter descriptions.) |
m (→Member types: ~Type) |
||
(40 intermediate revisions by 20 users not shown) | |||
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, |
− | + | class 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}}. | + | {{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}}s. |
+ | |||
+ | Iterators of {{tt|std::map}} iterate in ascending order of keys, where ascending is defined by the comparison that was used for construction. That is, given | ||
+ | * {{c|m}}, a {{tt|std::map}} | ||
+ | * {{c|it_l}} and {{c|it_r}}, dereferenceable iterators to {{c|m}}, with {{c|it_l < it_r}}. | ||
+ | {{c|1=m.value_comp()(*it_l, *it_r) == true}} (least to greatest if using the default comparison). | ||
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 39: | ||
===Member types=== | ===Member types=== | ||
{{dsc begin}} | {{dsc begin}} | ||
− | {{dsc hitem | | + | {{dsc hitem|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_range|map}} |
− | {{dsc inc | cpp/container/dsc emplace | map}} | + | {{dsc inc|cpp/container/dsc insert_or_assign|map}} |
− | {{dsc inc | cpp/container/dsc emplace_hint | map}} | + | {{dsc inc|cpp/container/dsc emplace|map}} |
− | {{dsc inc | cpp/container/dsc try_emplace | map}} | + | {{dsc inc|cpp/container/dsc emplace_hint|map}} |
− | {{dsc inc | cpp/container/dsc erase | map}} | + | {{dsc inc|cpp/container/dsc try_emplace|map}} |
− | {{dsc inc | cpp/container/dsc swap | map}} | + | {{dsc inc|cpp/container/dsc erase|map}} |
− | {{dsc inc | cpp/container/dsc extract | map}} | + | {{dsc inc|cpp/container/dsc swap|map}} |
− | {{dsc inc | cpp/container/dsc merge | map}} | + | {{dsc inc|cpp/container/dsc extract|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}} | ||
− | ==={{rl| | + | {{rrev|since=c++17| |
+ | ==={{rl|deduction guides|Deduction guides}}=== | ||
+ | }} | ||
+ | |||
+ | ===Notes=== | ||
+ | {{ftm begin|std=1|comment=1}} | ||
+ | {{ftm|__cpp_lib_containers_ranges|value=202202L|std=C++23|Ranges construction and insertion for containers}} | ||
+ | {{ftm end}} | ||
===Example=== | ===Example=== | ||
− | {{example|code= | + | {{example |
+ | |code= | ||
#include <iostream> | #include <iostream> | ||
#include <map> | #include <map> | ||
Line 124: | Line 139: | ||
{ | { | ||
std::cout << comment; | std::cout << comment; | ||
− | // | + | // Iterate using C++17 facilities |
for (const auto& [key, value] : m) | for (const auto& [key, value] : m) | ||
std::cout << '[' << key << "] = " << value << "; "; | std::cout << '[' << key << "] = " << value << "; "; | ||
Line 132: | Line 147: | ||
// std::cout << n.first << " = " << n.second << "; "; | // std::cout << n.first << " = " << n.second << "; "; | ||
// | // | ||
− | // C++98 alternative | + | // C++98 alternative: |
− | // for (std::map<std::string, int>::const_iterator it = m.begin(); it != m.end(); | + | // for (std::map<std::string, int>::const_iterator it = m.begin(); it != m.end(); ++it) |
// std::cout << it->first << " = " << it->second << "; "; | // std::cout << it->first << " = " << it->second << "; "; | ||
Line 150: | Line 165: | ||
print_map("2) Updated map: ", m); | print_map("2) Updated map: ", m); | ||
− | // | + | // Using operator[] with non-existent key always performs an insert |
std::cout << "3) m[UPS] = " << m["UPS"] << '\n'; | std::cout << "3) m[UPS] = " << m["UPS"] << '\n'; | ||
print_map("4) Updated map: ", m); | print_map("4) Updated map: ", m); | ||
Line 165: | Line 180: | ||
} | } | ||
|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 | ||
Line 183: | Line 198: | ||
===See also=== | ===See also=== | ||
{{dsc begin}} | {{dsc begin}} | ||
+ | {{dsc inc|cpp/container/dsc multimap}} | ||
{{dsc inc|cpp/container/dsc unordered_map}} | {{dsc inc|cpp/container/dsc unordered_map}} | ||
− | + | {{dsc inc|cpp/container/dsc flat_map}} | |
{{dsc end}} | {{dsc end}} | ||
{{langlinks|de|es|fr|it|ja|pl|pt|ru|zh}} | {{langlinks|de|es|fr|it|ja|pl|pt|ru|zh}} |
Latest revision as of 15:48, 1 November 2024
Defined in header <map>
|
||
template< class Key, |
(1) | |
namespace pmr { template< |
(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.
Iterators of std::map
iterate in ascending order of keys, where ascending is defined by the comparison that was used for construction. That is, given
- m, a
std::map
- it_l and it_r, dereferenceable iterators to m, with it_l < it_r.
m.value_comp()(*it_l, *it_r) == true (least to greatest if using the default comparison).
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 |
[edit] Template parameters
This section is incomplete Reason: Add descriptions of the template parameters. |
[edit] Member types
Type | Definition | ||||
key_type
|
Key
| ||||
mapped_type
|
T
| ||||
value_type
|
std::pair<const Key, T> | ||||
size_type
|
Unsigned integer type (usually std::size_t) | ||||
difference_type
|
Signed integer type (usually std::ptrdiff_t) | ||||
key_compare
|
Compare
| ||||
allocator_type
|
Allocator
| ||||
reference
|
value_type& | ||||
const_reference
|
const value_type& | ||||
pointer
|
| ||||
const_pointer
|
| ||||
iterator
|
LegacyBidirectionalIterator to value_type
| ||||
const_iterator
|
LegacyBidirectionalIterator to const value_type | ||||
reverse_iterator
|
std::reverse_iterator<iterator> | ||||
const_reverse_iterator
|
std::reverse_iterator<const_iterator> | ||||
node_type (since C++17)
|
a specialization of node handle representing a container node | ||||
insert_return_type (since C++17)
|
type describing the result of inserting a node_type , a specialization oftemplate<class Iter, class NodeType> |
[edit] Member classes
compares objects of type value_type (class) |
[edit] Member functions
constructs the map (public member function) | |
destructs the map (public member function) | |
assigns values to the container (public member function) | |
returns the associated allocator (public member function) | |
Element access | |
access specified element with bounds checking (public member function) | |
access or insert specified element (public member function) | |
Iterators | |
(C++11) |
returns an iterator to the beginning (public member function) |
(C++11) |
returns an iterator to the end (public member function) |
(C++11) |
returns a reverse iterator to the beginning (public member function) |
(C++11) |
returns a reverse iterator to the end (public member function) |
Capacity | |
checks whether the container is empty (public member function) | |
returns the number of elements (public member function) | |
returns the maximum possible number of elements (public member function) | |
Modifiers | |
clears the contents (public member function) | |
inserts elements or nodes(since C++17) (public member function) | |
(C++23) |
inserts a range of elements (public member function) |
(C++17) |
inserts an element or assigns to the current element if the key already exists (public member function) |
(C++11) |
constructs element in-place (public member function) |
(C++11) |
constructs elements in-place using a hint (public member function) |
(C++17) |
inserts in-place if the key does not exist, does nothing if the key exists (public member function) |
erases elements (public member function) | |
swaps the contents (public member function) | |
(C++17) |
extracts nodes from the container (public member function) |
(C++17) |
splices nodes from another container (public member function) |
Lookup | |
returns the number of elements matching specific key (public member function) | |
finds element with specific key (public member function) | |
(C++20) |
checks if the container contains element with specific key (public member function) |
returns range of elements matching a specific key (public member function) | |
returns an iterator to the first element not less than the given key (public member function) | |
returns an iterator to the first element greater than the given key (public member function) | |
Observers | |
returns the function that compares keys (public member function) | |
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 map s (function template) |
specializes the std::swap algorithm (function template) | |
(C++20) |
erases all elements satisfying specific criteria (function template) |
Deduction guides |
(since C++17) |
[edit] Notes
Feature-test macro | Value | Std | Feature |
---|---|---|---|
__cpp_lib_containers_ranges |
202202L | (C++23) | Ranges construction and insertion for containers |
[edit] 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
[edit] 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 tobe CopyConstructible |
LWG 464 | C++98 | accessing a const map by key was inconvenient
|
at function provided
|
[edit] See also
collection of key-value pairs, sorted by keys (class template) | |
(C++11) |
collection of key-value pairs, hashed by keys, keys are unique (class template) |
(C++23) |
adapts two containers to provide a collection of key-value pairs, sorted by unique keys (class template) |