简述C++map容器

pair键值对

std::pair在很多关联容器（如std::map、std::multimap、std::set、std：multiset等）中被广泛应用。以std::map为例，std::map是一个键值对的容器，其中每个元素都是一个std::pair，键用于唯一标识元素，值则是与键相关联的数据。

pair是类模板，一般用于表示key/value数据，其实现是结构体。

pair结构模板的定义如下：

template <class T1, class T2>

struct pair

{

    T1 first;     // 第一个成员，一般表示key。

    T2 second;  // 第二个成员，一般表示value。

      pair();       // 默认构造函数。

      pair(const T1 &val1,const T2 &val2);   // 有两个参数的构造函数。

      pair(const pair<T1,T2> &p);           // 拷贝构造函数。

      void swap(pair<T1,T2> &p);           // 交换两个pair。

};

make_pair函数模板的定义如下：

template <class T1, class T2>

make_pair(const T1 &first,const T2 &second)

{

      return pair<T1,T2>(first, second);

}

示例代码：

#include <iostream>
#include<utility>using  namespace std;template <class T1, class T2>
struct Pair
{T1 first;        // 第一个成员，一般表示key。T2 second;  // 第二个成员，一般表示value。Pair() {cout << "调用了有默认的构造函数。\n";}Pair(const T1& val1, const T2& val2) :first(val1), second(val2) {cout << "调用了有两个参数的构造函数。\n";}Pair(const Pair<T1, T2>& p) : first(p.first), second(p.second) {cout << "调用了拷贝构造函数。\n";}
};template <class T1, class T2>
Pair<T1, T2> make_Pair(const T1& first, const T2& second)
{// Pair<T1, T2> p(first, second);// return p;        // 返回局部对象。return Pair<T1, T2>(first, second);  // 返回临时对象。
}int main()
{pair<int, string> p0;cout << "p0 first=" << p0.first << ",second=" << p0.second << endl;pair<int, string> p1(1, "吴彦祖");    // 两个参数的构造函数。cout << "p1 first=" << p1.first << ",second=" << p1.second << endl;pair<int, string> p2 = p1;             // 拷贝构造。cout << "p2 first=" << p2.first << ",second=" << p2.second << endl;p2.swap(p0);cout << "p0 first=" << p0.first << ",second=" << p0.second << endl;cout << "p2 first=" << p2.first << ",second=" << p2.second << endl;auto p3 = make_pair(2, "陈冠希");cout << "键：" << p3.first << ", 值：" << p3.second << endl;
}

运行结果： 

map容器

map 容器封装了红黑树（平衡二叉排序树），用于查找。

包含头文件： #include<map>

map容器的元素是pair键值对。

迭代器是双向迭代器。

map类模板的声明：

template <class K, class V, class P = less<K>, class _Alloc = allocator<pair<const K, V >>>

class map : public _Tree<_Tmap_traits< K, V, P, _Alloc, false>>

{

   …

}

第一个模板参数K：key的数据类型（pair.first）。

第二个模板参数V：value的数据类型（pair.second）。

第三个模板参数P：排序方法，缺省按key升序。

第四个模板参数_Alloc：分配器，缺省用new和delete。

map提供了双向迭代器。

二叉链表：                               

struct BTNode                       

{                                 

   pair<K,V> p;       // 键值对。      

      BTNode *parent;   // 父节点。   

      BTNode *lchirld;    // 左子树。

      BTNode *rchild;    // 右子树。

};                                     

一、构造函数

1）map();  // 创建一个空的map容器。

2）map(initializer_list<pair<K,V>> il); // 使用统一初始化列表。

3）map(const map<K,V>& m);  // 拷贝构造函数。

4）map(Iterator first, Iterator last);  // 用迭代器创建map容器。

5）map(map<K,V>&& m);  // 移动构造函数（C++11标准）。

二、特性操作

size_t size() const;        // 返回容器的实际大小（已使用的空间）。

bool empty() const;      // 判断容器是否为空。

void clear();             // 清空容器。

三、元素操作

V &operator[](K key);             // 用给定的key访问元素。

const V &operator[](K key) const;  // 用给定的key访问元素，只读。

V &at(K key);                     // 用给定的key访问元素。

const V &at(K key) const;         // 用给定的key访问元素，只读。

注意：

1）[ ]运算符：如果指定键不存在，会向容器中添加新的键值对；如果指定键不存在，则读取或修改容器中指定键的值。

2）at()成员函数：如果指定键不存在，不会向容器中添加新的键值对，而是直接抛出out_of_range 异常。

示例代码：

#include <iostream>
#include <map>
using  namespace std;int main()
{map<string, string> m({ { "08","冠希" }, { "03","于晏" }, { "01","彦祖" }, { "07","德华" }, { "05","学友" } });cout << "m[08]=" << m["08"] << endl;     // 显示key为08的元素的value。cout << "m[09]=" << m["09"] << endl;    // 显示key为09的元素的value。key为09的元素不存在，将添加新的键值对。cout << "m.at(03)=" << m.at("03") << endl;//m.at("099");错误！！m["07"] = "黎明";                                          // 把key为07的元素的value修改为黎明。m["12"] = "富城";                                          // 将添加新的键值对。for (auto& val : m)cout << val.first << "," << val.second << "  ";cout << endl;
}

运行结果：

四、赋值操作

给已存在的容器赋值，将覆盖容器中原有的内容。

1）map<K,V> &operator=(const map<K,V>& m);         // 把容器m赋值给当前容器。

2）map<K,V> &operator=(initializer_list<pair<K,V>> il);  // 用统一初始化列表给当前容器赋值。

五、交换操作

void swap(map<K,V>& m);    // 把当前容器与m交换。

交换的是树的根结点。

六、比较操作

bool operator == (const map<K,V>& m) const;

bool operator != (const map<K,V>& m) const;

七、查找操作

1）查找键值为key的键值对

在map容器中查找键值为key的键值对，如果成功找到，则返回指向该键值对的迭代器；失败返回end()。

iterator find(const K &key);

const_iterator find(const K &key) const;  // 只读。

2）查找键值>=key的键值对

在map容器中查找第一个键值>=key的键值对，成功返回迭代器；失败返回end()。

iterator lower_bound(const K &key);

const_iterator lower_bound(const K &key) const;  // 只读。

3）查找键>key的键值对

在map容器中查找第一个键值>key的键值对，成功返回迭代器；失败返回end()。

iterator upper_bound(const K &key);

const_iterator upper_bound(const K &key) const;  // 只读。

4）统计键值对的个数

统计map容器中键值为key的键值对的个数。

size_t count(const K &key) const;

八、插入和删除

1）void insert(initializer_list<pair<K,V>> il);  // 用统一初始化列表在容器中插入多个元素。

2）pair<iterator,bool> insert(const pair<K,V> &value);  // 在容器中插入一个元素，返回值pair：first是已插入元素的迭代器，second是插入结果。

3）void insert(iterator first,iterator last);  // 用迭代器插入一个区间的元素。

4）pair<iterator,bool> emplace (...);  // 将创建新键值对所需的数据作为参数直接传入，map容器将直接构造元素。返回值pair：first是已插入元素的迭代器，second是插入结果。

例：mm.emplace(piecewise_construct, forward_as_tuple(8), forward_as_tuple("冰冰", 18));

5）iterator emplace_hint (const_iterator pos,...); // 功能与第4）个函数相同，第一个参数提示插入位置，该参数只有参考意义，如果提示的位置是正确的，对性能有提升，如果提示的位置不正确，性能反而略有下降，但是，插入是否成功与该参数元关。该参数常用end()和begin()。成功返回新插入元素的迭代器；如果元素已经存在，则插入失败，返回现有元素的迭代器。

6）size_t erase(const K & key);  // 从容器中删除指定key的元素，返回已删除元素的个数。

7）iterator erase(iterator pos);  // 用迭代器删除元素，返回下一个有效的迭代器。

8）iterator erase(iterator first,iterator last);  // 用迭代器删除一个区间的元素，返回下一个有效的迭代器。

示例代码：

#include <iostream>
#include <map>
using  namespace std;int main()
{map<string, string> m({ { "08","冠希" }, { "03","于晏" }, { "01","彦祖" }, { "07","德华" }, { "05","学友" } });// 执行插入操作并检查返回值auto result = m.insert(make_pair("08", "富城"));// result的类型是std::pair<std::map<std::string, std::string>::iterator, bool>// result.first是指向插入位置的迭代器（如果插入成功）或已存在相同键的迭代器（如果插入失败）// result.second是一个布尔值，表示插入是否成功if (result.second) {std::cout << "插入成功" << std::endl;}else {std::cout << "插入失败，键已存在" << std::endl;}for (auto& val : m)cout << val.first << "," << val.second << "  ";cout << endl;// 在map容器中查找键值为key的键值对，如果成功找到，则返回指向该键值对的迭代器；失败返回end()。auto it1 = m.find("05");if (it1 != m.end())cout << "查找成功：" << it1->first << "," << it1->second << endl;elsecout << "查找失败。\n";// 在map容器中查找第一个键值 >= key的键值对，成功返回迭代器；失败返回end()。auto it2 = m.lower_bound("05");if (it2 != m.end())cout << "查找成功：" << it2->first << "," << it2->second << endl;elsecout << "查找失败。\n";//	在map容器中查找第一个键值 > key的键值对，成功返回迭代器；失败返回end()。auto it3 = m.upper_bound("05");if (it3 != m.end())cout << "查找成功：" << it3->first << "," << it3->second << endl;elsecout << "查找失败。\n";//	统计map容器中键值为key的键值对的个数。cout << "count(05)=" << m.count("05") << endl;   // 返回1。cout << "count(06)=" << m.count("06") << endl;   // 返回0。
}

运行结果： 

std::map 的 insert 函数在遇到重复键的情况时，会根据其内部实现做出相应处理。通常情况下，它不会覆盖已有的键值对（与 std::unordered_map 不同，std::unordered_map 若插入重复键，会覆盖原来的值），而是会返回一个表示插入结果的对象，这个对象包含了一些信息来表明插入操作是否真正成功插入了新元素。 我们可以接受返回值来确认是否插入成功。

在容器中插入一个元素，返回值pair：first是已插入元素的迭代器，second是插入结果。

按照字符串的字典序比较规则（这也是 std::map 默认用于比较键的规则，因为键是 std::string 类型）：

"01" < "03" < "05" < "07" < "08"

所以查找lower和upper时候会找到学友和德华；

unordered_map容器

unordered（无序）

unordered_map容器封装了哈希表，查找、插入和删除元素时，只需要比较几次key的值。

包含头文件： #include<unordered_map>

unordered_map容器的元素是pair键值对。

unordered_map类模板的声明：

template <class K, class V, class _Hasher = hash<K>, class _Keyeq = equal_to<K>,

    class _Alloc = allocator<pair<const K, V>>>

class unordered_map : public _Hash<_Umap_traits<K, V, _Uhash_compare<K, _Hasher, _Keyeq>, _Alloc, false>>

{

      …

}

第一个模板参数K：key的数据类型（pair.first）。

第二个模板参数V：value的数据类型（pair.second）。

第三个模板参数_Hasher：哈希函数，默认值为std::hash<K>

第四个模板参数_Keyeq：比较函数，用于判断两个key是否相等，默认值是std::equal_to<K>。

第五个模板参数_Alloc：分配器，缺省用new和delete。

创建std::unordered_map类模板的别名：

template<class K,class V>

using umap = std::unordered_map<K, V>;

std::map 和 std::unordered_map 区别：

1. 底层数据结构

• std::map：

  • std::map 的底层数据结构是基于红黑树（Red-Black Tree）实现的。红黑树是一种自平衡二叉搜索树，它在插入和删除节点时会通过一系列的旋转和颜色调整操作来保持树的平衡，使得树的高度始终保持在一个相对较低的水平（最坏情况下为 O(logn)，其中n  是树中节点的数量）。
  • 这种数据结构的优点是能够保证元素按照键的大小顺序进行有序存储，并且在查找、插入和删除操作时，平均时间复杂度都为O(logn) 。例如，当你插入一个新的键值对到 std::map 中时，它会根据键的大小在红黑树中找到合适的位置进行插入，并自动调整树的结构以保持平衡和有序。

• std::unordered_map：

  • std::unordered_map 的底层数据结构是基于哈希表（Hash Table）实现的。哈希表通过一个哈希函数将键映射到一个特定的桶（Bucket）中，每个桶可以存储一个或多个键值对。理想情况下，当哈希函数设计得比较好时，查找操作可以在常数时间O(1)  内完成，因为可以通过计算键的哈希值直接定位到对应的桶，然后在桶内进行查找。
  • 然而，哈希表存在哈希冲突（Hash Collision）的问题，即不同的键可能通过哈希函数计算得到相同的哈希值，从而被映射到同一个桶中。为了解决哈希冲突，通常会采用一些冲突解决策略，如链地址法（将冲突的键值对链接成一个链表存放在同一个桶中）或开放地址法（通过一定的规则在哈希表中重新寻找空闲的位置来存放冲突的键值对）。

2、元素顺序

由于其基于红黑树的实现，std::map 中的元素会按照键的大小顺序自动进行排序。unordered_map 中的元素是无序的，因为哈希表本身并不保证元素的顺序。键值对在哈希表中的存储位置主要取决于键的哈希值以及冲突解决策略。所以，当你遍历 unordered_map 时，元素的出现顺序是不确定的，可能与插入顺序不同，也不一定按照键的任何特定顺序排列。

例如：

#include <iostream>
#include <unordered_map>int main() {std::unordered_map<int, std::string> myUnorderedMap;myUnorderedMap.insert({ 1, "one" });myUnorderedMap.insert({ 3, "three" });myUnorderedMap.insert({ 2, "two" });// 遍历unordered_map输出所有键值对，顺序不确定for (auto it = myUnorderedMap.begin(); it != myUnorderedMap.end(); ++it) {std::cout << "键：" << it->first << ", 值：" << it->second << std::endl;}return 0;
}

 

这个结果每次输出结果都一样，这其实是有一定概率会出现的情况。虽然理论上 std::unordered_map 的遍历顺序是不确定的，因为它是基于哈希表实现的，元素存储位置取决于键的哈希值以及哈希冲突解决策略等因素。但在实际情况中，如果数据量比较小，而且哈希函数（std::unordered_map 默认的哈希函数或者你自定义的哈希函数，如果有的话）对于你所插入的这些键计算出来的哈希值分布相对比较均匀，没有产生过多的哈希冲突，那么就有可能每次遍历输出的顺序看起来是一样的。

不过，当你插入的数据量逐渐增大，或者插入一些特殊的键值使得哈希冲突情况发生变化时，就很可能会出现不同的遍历顺序了。

例如：

#include <iostream>
#include <unordered_map>
#include<random>
#include<utility>
int main() {std::unordered_map<int, int> myUnorderedMap;for (int i = 1; i < 1000000; i++){std::random_device rd;std::mt19937 gen(rd());// 定义分布范围为1到1000000std::uniform_int_distribution<> dis(1, 1000000);// 生成随机数int randomNumber = dis(gen);myUnorderedMap.insert(std::make_pair(i, randomNumber));}// 遍历unordered_map输出所有键值对，顺序不确定for (auto it = myUnorderedMap.begin(); it != myUnorderedMap.end(); ++it) {std::cout << "键：" << it->first << ", 值：" << it->second << std::endl;}return 0;
}

如果生成的数足够多，顺序是不确定的。

3、查找、插入和删除操作的性能特点

• std::map：

  • 查找、插入和删除操作的平均时间复杂度都是 O(logn)。这意味着在数据量较大时，这些操作的执行时间会随着数据量的增加而以对数级别的速度增长。虽然这种增长速度相对较慢，但相比一些常数时间复杂度的操作（如理想情况下的哈希表查找）还是要慢一些。不过，由于 std::map 能够保持元素的有序性，在一些需要基于顺序进行查找（如查找某个键值对之后的所有键值对）或者进行范围查找（如查找键在某个区间内的所有键值对）的场景下，它具有独特的优势。

• std::unordered_map：

  • 在理想情况下，查找操作的时间复杂度可以达到 O(1)，即可以在常数时间内完成查找。这是因为通过哈希函数可以直接定位到键值对可能所在的桶，然后在桶内进行查找。然而，实际情况中，由于哈希冲突的存在，当哈希冲突比较严重时，查找操作可能会退化为链表查找（如果采用链地址法解决冲突），此时查找时间复杂度可能会变为O(n) ，其中  是桶内键值对的数量。插入和删除操作的时间复杂度也类似，在理想情况下为 O(1)，但在哈希冲突严重时可能会变差。总体来说，当哈希函数设计得比较好，并且哈希冲突不太严重时，std::unordered_map 在查找、插入和删除操作上的性能要优于 std::map。

4. 内存占用

• std::map：

  • 由于红黑树需要存储节点之间的指针以及用于保持树平衡的额外信息（如节点的颜色等），相对来说内存占用可能会比 std::unordered_map 要多一些。具体的内存占用情况还会受到键值对类型、树的大小等因素的影响。

• std::unordered_map：

  • std::unordered_map 的内存占用主要取决于哈希表的大小（即桶的数量）以及键值对的数量。一般来说，为了减少哈希冲突，哈希表可能需要设置较大的桶数，这可能会导致一定的内存浪费。但总体而言，在数据量较大且哈希冲突不严重的情况下，std::unordered_map 的内存占用可能相对 std::map 会有一定的优势。

5、总结

std::map 和 std::unordered_map 各有优缺点，在实际应用中，需要根据具体的应用场景和需求来选择合适的容器。如果需要元素按照键的顺序存储并且对查找、插入和删除操作的平均性能要求不是特别高（能够接受O(logn)  的时间复杂度），那么 std::map 是一个不错的选择；如果更看重查找、插入和删除操作的快速执行（希望在理想情况下达到 O(1) 的时间复杂度），并且不需要元素按照特定顺序排列，那么 std::unordered_map 则更为合适。