知识储备

C++关联容器 C++11之前只提供了 - 有序的关联容器 - 底层数据结构：红黑树 增删查时间复杂度:O(logn) set（集合） map（映射表）

C++11又提供了 - 无序的关联容器 - 底层数据结构：哈希表 增删查时间复杂度：O(1) unordered_set（无序集合） key unordered_map（无序映射表） key-value

#include <iostream>
#include <vector>    // std::vector<int>
#include <list>
#include <string>
#include <algorithm>
#include <stack>   // stack
#include <queue>   // queue   优先级队列priority_queue
#include <stdlib.h>
#include <time.h>
#include <functional>  // 函数对象
#include <unordered_map>
#include <set>
#include <typeinfo>    // 查看C++变量的类型
using namespace std; // using 指示符   using std::vector;


class Student
{
public:
    Student(int id=0, string name="")
    {
        id_ = id;
        name_ = name;
    }
private:
    int id_;
    string name_;

    friend ostream& operator<<(ostream& out, const Student& s);
};

ostream& operator<<(ostream& out, const Student& s)
{
    out << s.id_ << " " << s.name_ << endl;
    return out;
}

int main()
{
    // 映射表  value id Student
    unordered_map<int, Student> m;

    // 增加元素[key, value]
    m.insert(make_pair(1000, Student(1000, "zhang san")));
    m.insert({ 2000, Student(2000, "li yang") }); // pair对象打包key - value键值对
    m.emplace(3000, Student(3000, "wang wu"));

    // 用迭代器遍历map表   搜索效率：O(n)
    for (auto it = m.begin(); it != m.end(); ++it)
    {
        // it => 每一个pair对象 first second
        cout << "key:" << it->first << " second:" << it->second << endl;
    }

    // 删除元素
    m.erase(2000); // 用key进行删除

    // 修改元素 m.operator[](key)
    // map[key] => value
    cout << typeid(m[3000]).name() << endl;
    cout << m[3000] << endl;

    // key:4000 不存在 map会插入一个新的键值对 [4000, Student()]，，所以： []慎用
    cout << m[4000] << endl;

    // 搜索   find方法：传入一个key，返回包含key的pair对象的迭代器， 如果不存在，返回end()
    // 这个find，才是哈希表的搜索，效率:O(1)
    auto it2 = m.find(3000);
    if (it2 != m.end())
    {
        cout << it2->first << " " << it2->second << endl;
    }

    m.clear();
}