Difference between revisions of "cpp/container/map"
Omarsaber98 (Talk | contribs) m (added semicolon) |
(Added LWG issue #230 DR (part 6).) |
||
Line 8: | Line 8: | ||
class T, | class T, | ||
class Compare = std::less<Key>, | class Compare = std::less<Key>, | ||
− | 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< class Key, class T, class Compare = std::less<Key> > |
− | using map = std::map<Key, T, Compare, | + | using map = std::map< |
− | + | Key, T, Compare, | |
+ | std::pmr::polymorphic_allocator<std::pair<const Key, T>> | ||
+ | >; | ||
} | } | ||
}} | }} | ||
Line 22: | Line 24: | ||
{{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. | + | 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)}}. |
{{tt|std::map}} meets the requirements of {{named req|Container}}, {{named req|AllocatorAwareContainer}}, {{named req|AssociativeContainer}} and {{named req|ReversibleContainer}}. | {{tt|std::map}} meets the requirements of {{named req|Container}}, {{named req|AllocatorAwareContainer}}, {{named req|AssociativeContainer}} and {{named req|ReversibleContainer}}. | ||
Line 120: | Line 122: | ||
std::cout << comment; | std::cout << comment; | ||
// iterate using C++17 facilities | // 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 << "; "; | ||
− | + | ||
// C++11 alternative: | // C++11 alternative: | ||
− | // for (const auto& n : m) | + | // for (const auto& n : m) |
// 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(); it++) | + | // 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 << "; "; | ||
− | + | ||
std::cout << '\n'; | std::cout << '\n'; | ||
} | } | ||
Line 136: | Line 138: | ||
int main() | int main() | ||
{ | { | ||
− | // Create a map of three ( | + | // Create a map of three (string, int) pairs |
− | std::map<std::string, int> m { {"CPU", 10}, {"GPU", 15}, {"RAM", 20} | + | std::map<std::string, int> m{<!---->{"CPU", 10}, {"GPU", 15}, {"RAM", 20}<!---->}; |
print_map("1) Initial map: ", m); | print_map("1) Initial map: ", m); | ||
− | m["CPU"] = 25; | + | m["CPU"] = 25; // update an existing value |
− | m["SSD"] = 30; | + | m["SSD"] = 30; // insert a new value |
print_map("2) Updated map: ", m); | print_map("2) Updated map: ", m); | ||
Line 159: | Line 161: | ||
std::cout << std::boolalpha << "8) Map is empty: " << m.empty() << '\n'; | std::cout << std::boolalpha << "8) Map is empty: " << m.empty() << '\n'; | ||
} | } | ||
− | + | |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; | ||
Line 172: | Line 174: | ||
===Defect reports=== | ===Defect reports=== | ||
{{dr list begin}} | {{dr list begin}} | ||
+ | {{dr list item|wg=lwg|dr=230|std=C++98|before={{tt|Key}} was not required to be {{named req|CopyConstructible}}<br>(a key of type {{tt|Key}} might not be able to be constructed)|after={{tt|Key}} is also required to<br>be {{named req|CopyConstructible}}}} | ||
{{dr list item|wg=lwg|dr=464|std=C++98|before=accessing a const {{tt|map}} by key was inconvenient|after={{tt|at}} function provided}} | {{dr list item|wg=lwg|dr=464|std=C++98|before=accessing a const {{tt|map}} by key was inconvenient|after={{tt|at}} function provided}} | ||
{{dr list end}} | {{dr list end}} | ||
Line 177: | Line 180: | ||
===See also=== | ===See also=== | ||
{{dsc begin}} | {{dsc begin}} | ||
− | {{dsc inc | cpp/container/dsc unordered_map}} | + | {{dsc inc|cpp/container/dsc unordered_map}} |
− | <!-- {{dsc see cpp | cpp/language/ | + | <!-- {{dsc see cpp|cpp/language/structured binding|Structured Binding (since C++17)|nomono=true}} --> |
{{dsc end}} | {{dsc end}} | ||
{{langlinks|de|es|fr|it|ja|pl|pt|ru|zh}} | {{langlinks|de|es|fr|it|ja|pl|pt|ru|zh}} |
Revision as of 00:25, 12 October 2022
Defined in header <map>
|
||
template< class Key, |
(1) | |
namespace pmr { template< class Key, class T, class Compare = std::less<Key> > |
(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 |
Member types
Member 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> |
Member classes
compares objects of type value_type (class) |
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++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) |
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)
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 tobe CopyConstructible |
LWG 464 | C++98 | accessing a const map by key was inconvenient
|
at function provided
|
See also
(C++11) |
collection of key-value pairs, hashed by keys, keys are unique (class template) |