接着介绍两个重要的容器map和hashtable。

1. map

map映射也叫键值对即<key,value>分为键值和实值，有序且默认按键值排序，底层数据结构是红黑树，是一个重要的容器。
基本方法：

insert();	//插入一个键值对
find();		//查找键是否在map里面
erase();	//去除指定的键值对

map的插入方式有两种，一种是插入pair键值对一种是类似数组的方式进行初始化。
可执行代码：

//
// Created by wsk on 25-10-27.
//
#include <iostream>
#include <string>
#include <map>
using namespace std;
struct myCompare
{
    bool operator()(const string& lsh, const string& rsh) const
    {
        return lsh > rsh;// 自定义排序方法，按键值降序排序
    }
};

int main()
{
    map<string,int> mymap;
    map<string,int,myCompare> mymap2;
    multimap<string,int,myCompare> mymap3;// 多键map
    // mymap3.insert(pair<string,int>("a",1));
    // mymap3.insert(pair<string,int>(string("a"),1));
    // cout << mymap3.size() << endl;
    // string str = "hello";
    mymap["Tom"] = 1;
    mymap["Jack"] = 2;
    mymap["Bob"] = 3;
    mymap["Rose"] = 4;
    mymap2["Tom"] = 1;
    mymap2["Jack"] = 2;
    mymap2["Bob"] = 3;
    mymap2["Rose"] = 4;
    pair<string,int> value("David",5);
    mymap.insert(value);// 插入
    mymap2.insert(value);
    int number = mymap["Bob"];
    cout << number << endl;
    // mymap.erase("Tom");// 删除
    cout << mymap.size() << endl;
    auto it2 = mymap.find("Tom");// 查找
    if (it2 != mymap.end())
    {
        mymap2.erase(it2);
        cout << "Tom is found!" << endl;
    }else
    {
        cout << "Tom is not found!" << endl;
    }
    // it2->second = 6;// 修改实值
    auto it = mymap.begin();
    while(it != mymap.end())
    {
        cout<< it->first <<" "<< it->second <<endl;// 默认按照键值排序
        ++it;
    }
    cout<<endl;
    cout << "降序排序后：" << endl;
    auto it3 = mymap2.begin();
    while(it3 != mymap2.end())
    {
        cout<< it3->first <<" "<< it3->second <<endl;// 默认按照键值排序
        ++it3;
    }
    cout<<endl;
    return 0;
}

2. hashtable

哈希表又叫散列表，采用空间换时间的思路，是查找时间复杂度接近O(1)的数据结构。其中有两个重要的概念哈希函数和碰撞检测。使用哈希函数不可避免的会带来哈希碰撞，常见处理方式有线性探测法和拉链法。接下来主要介绍一下拉链法，因为STL模板里面的hashtable冲突处理方式就是拉链法的一个变体。
简单例子：在长度为53的哈希表里面依次插入元素59、63、108、2、53、55。哈希函数采用简单的除余运算。插入后哈希表如图所示：

当出现哈希值相同时通过链表连接相同哈希值的元素。比如要查找值108是否在哈希表里面首先计算key为2然后顺序查询链表直到链表为空。hashtable在STL容器是以底层算法的形式存在，利用到hashtable的容器有hash_set、hash_map、hash_multiset和hash_multimap。和普通的set、map的区别是hash_set和hash_map的键值是无序的，而set和map是有序的。简单测试：

//
// Created by wsk on 25-10-27.
//
#include <algorithm>
#include <iostream>
#include <unordered_set>
using namespace std;

int main()
{
    unordered_set<int> myset(10);
    myset.insert(3);
    myset.insert(13);
    myset.insert(23);
    myset.insert(389);
    myset.insert(194);
    myset.insert(387);
    auto iter = myset.begin();
    while (iter!=myset.end())
    {
        cout << *iter << endl;
        ++iter;
    }
    return 0;
}

3. 结语

STL标准模板库里面提供了大量常见的数据结构，可以帮助我们理解和使用它们。利用这些数据结构可以快速实现我们的逻辑和提高编程效率。