c++ 11标准模板（STL） std::map(一）旧
std::map 是有序键值对容器，它的元素的键是唯一的。用比较函数 Compare 排序键。搜索、移除和插入操作拥有对数复杂度。 map 通常实现为红黑树。在每个标准库使用比较 (Compare) 概念的位置，以等价关系检验唯一性。不精确而言，若二个对象 a 与 b 互相比较不小于对方 ： !comp(a, b) && !comp(b, a) ，则认为它们等价（非唯一）。
·
定义于头文件<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>>>
}
std::map 是有序键值对容器，它的元素的键是唯一的。用比较函数 Compare 排序键。搜索、移除和插入操作拥有对数复杂度。 map 通常实现为红黑树。
在每个标准库使用比较 (Compare) 概念的位置，以等价关系检验唯一性。不精确而言，若二个对象 a 与 b 互相比较不小于对方 ： !comp(a, b) && !comp(b, a) ，则认为它们等价（非唯一）。
std::map 满足容器 (Container) 、具分配器容器 (AllocatorAwareContainer) 、关联容器 (AssociativeContainer) 和可逆容器 (ReversibleContainer) 的要求。
构造函数
map();
explicit map( const Compare& comp,const Allocator& alloc = Allocator() ); (1)
explicit map( const Allocator& alloc ); (1) (C++11 起)
template< class InputIt >
map( InputIt first, InputIt last, const Compare& comp = Compare(),
const Allocator& alloc = Allocator() ); （2）
template< class InputIt >
map( InputIt first, InputIt last,
const Allocator& alloc ); (C++14 起)
map( const map& other );
map( const map& other, const Allocator& alloc ); (3) (C++11 起)
map( map&& other );(4) (C++11 起)
map( map&& other, const Allocator& alloc ); (4) (C++11 起)
map( std::initializer_list<value_type> init,
const Compare& comp = Compare(),
const Allocator& alloc = Allocator() ); （2）(C++11 起)
map( std::initializer_list<value_type> init,const Allocator& ); （2）(C++14 起)
从各种数据源构造新容器，可选地使用用户提供的分配器 alloc 或比较函数对象 comp 。
1) 构造空容器。
2) 构造容器，使之拥有范围 [first, last) 的内容。若范围中的多个元素拥有比较等价的关键，则插入哪个元素是未指定的（待决的 LWG2844 ）。
3) 复制构造函数。构造容器，使之拥有 other 的内容副本。若不提供 alloc ，则通过调用 std::allocator_traits<allocator_type>::select_on_container_copy_construction(other.get_allocator()) 获得分配器。
4) 移动构造函数。用移动语义构造容器，使之拥有 other 的内容。若不提供 alloc ，则从属于 other 的分配器移动构造分配器
5) 构造容器，使之拥有 initializer_list init 的内容。若范围中的多个元素拥有比较等价的关键，则插入哪个元素是未指定的（待决的 LWG2844 ）。
参数
| alloc | - | 用于此容器所有内存分配的分配器 |
| comp | - | 用于所有关键比较的比较函数对象 |
| first, last | - | 复制元素来源的范围 |
| other | - | 要用作源以初始化容器元素的另一容器 |
| init | - | 用以初始化容器元素的 initializer_list |
| 类型要求 | ||
- InputIt 必须满足遗留输入迭代器 (LegacyInputIterator) 的要求。 | ||
- Compare 必须满足比较 (Compare) 的要求。 | ||
- Allocator 必须满足分配器 (Allocator) 的要求。 | ||
复杂度
1) 常数。
2) N log(N) ，其中通常有 N = std::distance(first, last) ，若范围已为 value_comp() 所排序则与 N 成线性。
3) 与 other 的大小成线性。
4) 常数。若给定 alloc 且 alloc != other.get_allocator() 则为线性。
5) N log(N) ，其中通常有 N = init.size()) ，若 init 已按照 value_comp() 排序则与 N 成线性 。
异常
对 Allocator::allocate 的调用可能抛出。
示例
// 构造空容器
map<uint16_t, string> map1;
cout << "map1.size() : " << map1.size() << endl;
// 列表初始化，构造, 排序递增
map<uint16_t, string, std::less<uint16_t>> map2{{1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}, {5, "E"}};
print_Map("initializer_list, ASC", map2);
// 列表初始化，构造, 排序递减
map<uint16_t, string, std::greater<uint16_t>> map6{{1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}, {5, "E"}};
print_Map("initializer_list, DESC", map6);
// 列表初始化，构造, 排序自定义
map<uint16_t, string, myCompare> map7{{1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}, {5, "E"}};
print_Map("initializer_list, DESC", map7);
// 范围构造,排序递增
map<uint16_t, string, std::less<uint16_t>> map3(map2.begin(), map2.end());
print_Map("range, ASC", map3);
// 范围构造,排序递减
map<uint16_t, string, std::greater<uint16_t>> map8(map2.begin(), map2.end());
print_Map("range, DESC", map8);
// 拷贝构造，类型必须一致，包括排序，排序递增
map<uint16_t, string, std::less<uint16_t>> map4(map3);
print_Map("copy, ASC", map4);
// 拷贝构造,排序递增
map<uint16_t, string, std::greater<uint16_t>> map9(map8);
print_Map("copy, DESC", map9);
// 赋值构造,类型必须一致，包括排序，排序递增
map<uint16_t, string, std::less<uint16_t>> map10 = map4;
print_Map("assignment , ASC", map10);
// 赋值构造,类型必须一致，包括排序，排序递减
map<uint16_t, string, std::greater<uint16_t>> map11 = map9;
print_Map("assignment , DESC", map11);
元素访问
访问指定的元素，同时进行越界检查
std::map<Key,T,Compare,Allocator>::at
T& at( const Key& key ); (1) (C++11 起)
const T& at( const Key& key ) const; (2) (C++11 起)
返回到拥有等于 key 的关键的元素被映射值的引用。若无这种元素，则抛出 std::out_of_range 类型异常。
参数
| key | - | 要找到的元素的关键 |
返回值
到请求元素的被映射值的引用
异常
若容器无拥有指定 key 的元素则为 std::out_of_range
复杂度
与容器大小成对数。
访问或插入指定的元素
std::map<Key,T,Compare,Allocator>::operator[]T& operator[]( const Key& key ); (1)
T& operator[]( Key&& key ); (2) (C++11 起)
返回到映射到等于 key 的关键的值的引用，若这种关键不存在则进行插入。
1) 若关键不存在则插入 value_type(key, T()) 。此函数等价于 return insert(std::make_pair(key, T())).first->second;
| (C++11 前) | ||||||
1) 若关键不存在，则插入从 std::piecewise_construct, std::forward_as_tuple(key), std::tuple<>() 原位构造的 value_type 对象。此函数等价于 return this->try_emplace(key).first->second; 。 (C++17 起)使用默认分配器时，这导致从 key 复制构造关键，并值初始化被映射值。
value_type 对象。此函数等价于 return this->try_emplace(std::move(key)).first->second; 。 (C++17 起)使用默认分配器时，这导致从 key 移动构造关键，并值初始化被映射值。
| (C++11 起) | ||||||
没有迭代器或引用被非法化。
参数
| key | - | 要寻找的元素关键 |
返回值
若不存在拥有关键 key 的元素，则为到新元素被映射值的引用。否则为到既存的关键等价于 key 的元素的被映射值的引用。
异常
若任何操作抛出异常，则插入无效果。
复杂度
与容器大小成对数。
示例
cout << "elementAccessTest() begin" << endl;
map<uint16_t, string, std::less<uint16_t>> map1{{1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}, {5, "E"}};
cout << "at(key) : " << map1.at(1) << endl;
cout << "[key] : " << map1[2] << endl;
// map容器产生<6,"">节点
cout << "[key] : " << map1[6] << endl;
print_Map("[key] , ASC", map1);
// map容器产生<7,"H">节点
map1[7] = "H";
print_Map("[key] , ASC", map1);
// map容器key为1的节点value被替换为"K"
map1[1] = "K";
print_Map("[key] , ASC", map1);
cout << "elementAccessTest() end" << endl;
容量
检查容器是否为空
std::map<Key,T,Compare,Allocator>::emptybool empty() const; (C++11 前)
bool empty() const noexcept; (C++11 起)(C++20 前)
[[nodiscard]] bool empty() const noexcept;(C++20 起)
检查容器是否无元素，即是否 begin() == end() 。
参数
（无）
返回值
若容器为空则为 true ，否则为 false
复杂度
常数。
返回容纳的元素数
std::map<Key,T,Compare,Allocator>::sizesize_type size() const; (C++11 前)
size_type size() const noexcept; (C++11 起)
返回容器中的元素数，即 std::distance(begin(), end()) 。
参数
（无）
返回值
容器中的元素数量。
复杂度
常数。
返回可容纳的最大元素数
std::map<Key,T,Compare,Allocator>::max_sizesize_type max_size() const; (C++11 前)
size_type max_size() const noexcept; (C++11 起)
返回根据系统或库实现限制的容器可保有的元素最大数量，即对于最大容器的 std::distance(begin(), end()) 。
参数
（无）
返回值
元素数量的最大值。
复杂度
常数。
注意
此值通常反映容器大小上的理论极限，至多为 std::numeric_limits<difference_type>::max() 。运行时，可用 RAM 总量可能会限制容器大小到小于 max_size() 的值。
示例
map<uint16_t, string> map1;
cout << "map1: " << (map1.empty() ? "empty" : "not empty");
cout << "map1 size() " << map1.size() << endl;;
map1[1] = "A";
map1[2] = "B";
cout << "map1: " << (map1.empty() ? "empty" : "not empty");
cout << "map1 size() " << map1.size() << endl;;
cout << "map<uint16_t, string> max_size: " << map1.max_size() << std::endl;
map<uint16_t, uint16_t> map2;
cout << "map<uint16_t, uint16_t> max_size: " << map2.max_size() << std::endl;
map<string, uint16_t> map3;
cout << "map<string, uint16_t> max_size: " << map3.max_size() << std::endl;
map<string, string> map4;
cout << "map<string, string> max_size: " << map4.max_size() << std::endl;
代码汇总
#include <iostream>
#include <map>
#include <string>
using namespace std;
struct myCompare
{
bool operator()(const uint16_t a, const uint16_t b) const
{
return (a > b);
}
myCompare() {}
};
template <typename _Key, typename _Tp, typename _Compare = std::less<_Key>,
typename _Alloc = std::allocator<std::pair<const _Key, _Tp> > >
void print_Map(const string &name, const map<_Key, _Tp, _Compare, _Alloc> &tmap)
{
cout << name << ": \n";
for (const std::pair<const _Key, _Tp> it : tmap)
{
cout << "key: " << it.first << ", value: " << it.second << endl;
}
}
void constructorTest()
{
cout << "constructorTest() begin" << endl;
// 构造空容器
map<uint16_t, string> map1;
cout << "map1.size() : " << map1.size() << endl;
// 列表初始化，构造, 排序递增
map<uint16_t, string, std::less<uint16_t>> map2{{1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}, {5, "E"}};
print_Map("initializer_list, ASC", map2);
// 列表初始化，构造, 排序递减
map<uint16_t, string, std::greater<uint16_t>> map6{{1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}, {5, "E"}};
print_Map("initializer_list, DESC", map6);
// 列表初始化，构造, 排序自定义
map<uint16_t, string, myCompare> map7{{1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}, {5, "E"}};
print_Map("initializer_list, DESC", map7);
// 范围构造,排序递增
map<uint16_t, string, std::less<uint16_t>> map3(map2.begin(), map2.end());
print_Map("range, ASC", map3);
// 范围构造,排序递减
map<uint16_t, string, std::greater<uint16_t>> map8(map2.begin(), map2.end());
print_Map("range, DESC", map8);
// 拷贝构造，类型必须一致，包括排序，排序递增
map<uint16_t, string, std::less<uint16_t>> map4(map3);
print_Map("copy, ASC", map4);
// 拷贝构造,排序递增
map<uint16_t, string, std::greater<uint16_t>> map9(map8);
print_Map("copy, DESC", map9);
// 赋值构造,类型必须一致，包括排序，排序递增
map<uint16_t, string, std::less<uint16_t>> map10 = map4;
print_Map("assignment , ASC", map10);
// 赋值构造,类型必须一致，包括排序，排序递减
map<uint16_t, string, std::greater<uint16_t>> map11 = map9;
print_Map("assignment , DESC", map11);
cout << "constructorTest() end" << endl;
}
void elementAccessTest()
{
cout << "elementAccessTest() begin" << endl;
map<uint16_t, string, std::less<uint16_t>> map1{{1, "A"}, {2, "B"}, {3, "C"}, {4, "D"}, {5, "E"}};
cout << "at(key) : " << map1.at(1) << endl;
cout << "[key] : " << map1[2] << endl;
// map容器产生<6,"">节点
cout << "[key] : " << map1[6] << endl;
print_Map("[key] , ASC", map1);
// map容器产生<7,"H">节点
map1[7] = "H";
print_Map("[key] , ASC", map1);
// map容器key为1的节点value被替换为"K"
map1[1] = "K";
print_Map("[key] , ASC", map1);
cout << "elementAccessTest() end" << endl;
}
void capacityTest()
{
cout << "capacityTest begin" << endl;
map<uint16_t, string> map1;
cout << "map1: " << (map1.empty() ? "empty" : "not empty");
cout << "map1 size() " << map1.size() << endl;;
map1[1] = "A";
map1[2] = "B";
cout << "map1: " << (map1.empty() ? "empty" : "not empty");
cout << "map1 size() " << map1.size() << endl;;
cout << "map<uint16_t, string> max_size: " << map1.max_size() << std::endl;
map<uint16_t, uint16_t> map2;
cout << "map<uint16_t, uint16_t> max_size: " << map2.max_size() << std::endl;
map<string, uint16_t> map3;
cout << "map<string, uint16_t> max_size: " << map3.max_size() << std::endl;
map<string, string> map4;
cout << "map<string, string> max_size: " << map4.max_size() << std::endl;
cout << "capacityTest endl" << endl;
}
int main()
{
// constructorTest();
// elementAccessTest();
capacityTest();
return 0;
}
权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区
更多推荐
2
0- 0
已为社区贡献3条内容
所有评论(0)