map

存储结构

map容器的底层存储是一个红黑树，遍历方式都是按照中序遍历的方式进行的。

int main() {std::map<int, std::string> ismap;ismap[12] = "yhping";ismap[34] = "xjq";ismap[23] = "hx";ismap[67] = "dxw";ismap[45] = "yx";ismap[56] = "dy";
}

上面代码，我们定义了一map容器，其中放置了数据，其存储结构是红黑树，按照关键码进行排序。如下图：
在这里插入图片描述
我们知道了其存储结构，才可以了解其成员方法。

基本操作

equal_range

函数声明：std::pair<const_iterator,const_iterator> equal_range(const k&x)const
该函数返回容器中所拥有给定关键的元素范围，其中键值对中存在两个迭代器，一个指向首个不小于key的元素，首个迭代器可以通过lower_bound()获得，而第二个迭代器指向首个大于key的元素，可换用upper_bound（）获得。
试想 auto it= ismap.equal_range(40);该函数返回值的两个指针指向。
根据上面代码我们也可得到第一个迭代器指向45，第二个也指向45。

cout << it.first->first << " " << it.second->first << endl;

执行该语句得到的结果便是45，45。

	auto et= ismap.equal_range(45);cout << et.first->first<<":"<<et.first->second << endl;cout << et.second->first <<":"<<et.second->second<< endl;auto it = ismap.lower_bound(45);cout << it->first <<":"<< it->second << endl;auto pt = ismap.upper_bound(45);cout << pt->first << ":"<< pt->second << endl;

执行结果：在这里插入图片描述
通过结果结果发现equal_range函数返回的是两个迭代器，而lower_bound和upper_bound返回的是一个迭代器，分别是首个不小于待查找的元素和首个大于带查找值得元素。

遍历方式

执行下面语句，判断其结果：

int main() {std::map<int, std::string> ismap;ismap[12] = "yhping";ismap[34] = "xjq";ismap[23] = "hx";ismap[67] = "dxw";ismap[45] = "yx";ismap[56] = "dy";auto p = ismap.begin();for (; p != ismap.end(); ++p) {cout << p->first <<" : " <<p->second<< endl;}
}

这段代码便是要我们遍历map容器，结果如下：
在这里插入图片描述
也可以通过map定义时加入geater< int >参数来改变存储顺序。通过上面执行结果我们可以看出，迭代器的首个元素指向关键码最小的位置，而末尾便是最大的位置。遍历的时候是按照中序遍历的顺序进行遍历，但是我们明明对迭代器进行了++操作，所以总觉得是对其进行了+1，而本质上是通过调用函数来移动到其直接后继。

插入

map容器插入时如果其中存在相同关键码，便只会插入一个。

int main() {std::map<int, std::string> ismap;ismap.insert(std::map<int, std::string>::value_type(18, "dxw"));ismap.insert(std::map<int, std::string>::value_type(18, "sxl"));ismap.insert(std::map<int, std::string>::value_type(12, "yhping"));ismap.insert(std::map<int, std::string>::value_type(12, "wt"));ismap.insert(std::map<int, std::string>::value_type(34, "newdata"));ismap.insert(std::map<int, std::string>::value_type(23, "yx"));ismap.insert(std::map<int, std::string>::value_type(24, "fjx"));ismap.insert(std::map<int, std::string>::value_type(22, "data"));for (auto& x : ismap) {cout << x.first << ":" << x.second << endl;}
}

结果：在这里插入图片描述

所以此时就要用多重map，

multimap

多重map可以存放关键码相同得数据，如下

int main() {std::multimap<int, std::string> ismap;ismap.insert(std::multimap<int, std::string>::value_type(18, "dxw"));ismap.insert(std::multimap<int, std::string>::value_type(18, "sxl"));ismap.insert(std::multimap<int, std::string>::value_type(12, "yhping"));ismap.insert(std::multimap<int, std::string>::value_type(12, "wt"));ismap.insert(std::multimap<int, std::string>::value_type(34, "newdata"));ismap.insert(std::multimap<int, std::string>::value_type(23, "yx"));ismap.insert(std::multimap<int, std::string>::value_type(24, "fjx"));ismap.insert(std::multimap<int, std::string>::value_type(22, "data"));for (auto& x :ismap) {cout << x.first << ":" << x.second << endl;}
}

使用了多重map之后就会发现可以存放多个关键码相同得元素，
在这里插入图片描述
如果在此时用equal_range函数，会出现什么情况呢？
我们可以在上面代码得前提下执行下面代码

auto it = ismap.equal_range(18);for (auto p = it.first; p != it.second; ++p) {cout << p->first << " : " << p->second << endl;}

得到结果便是关键码为18得两个迭代器。如果在容器中没有关键码为18得值，返回得两个迭代器和有序map一样，返回的是指向首个不小于和首个大于关键码的迭代器。

set

set容器智能存放一种类型，其底层也是红黑树，遍历是有序的，其插入的参数有两个，一个是要插入的关键码类型，另一个是bool类型，可以通过bool类型的返回值判断是否插入成功。

int main() {std::set<int> iset;for (int i = 0; i < 100; ++i) {auto it=iset.insert(rand()%100);if (it.second) {cout << "insert seccod" << endl;}else {cout << "已经有重复值" << endl;cout << *it.first << endl;}}std::set<int>::iterator it = iset.begin();for (; it != iset.end(); ++it) {cout << *it << endl;}
}

unordered_map

通过代码比较map和unordered_map的区别

int main() {std::map<int, std::string> ismap;std::unordered_map<int, std::string> isunmap;ismap[12] = "yhping";ismap[34] = "xjq";ismap[23] = "hx";ismap[67] = "dxw";ismap[45] = "yx";ismap[56] = "dy";isunmap[12] = "yhping";isunmap[34] = "xjq";isunmap[23] = "hx";isunmap[67] = "dxw";isunmap[45] = "yx";isunmap[56] = "dy";cout << "map" << endl;for (auto& x : ismap) {cout << x.first << ":" << x.second << endl;}cout << "------------------------" << endl;cout << "undered_map" << endl;for (auto& x : isunmap) {cout << x.first << ":" << x.second << endl;}return 0;
}

我们通过代码可以发现其区别和名字一样，一个是有序的一个是无序的，这是为什么呢？
无需map的底层实际上不是红黑树，而是哈希桶，我们可以通过画图来理解其底层结构。
在这里插入图片描述
这里桶中结点个数是10个，所以存放结点是这样存放的，关键码对10取余，得到的结果是多少就存放在那个结点后面，存放的方式便是链表。而如果数据量太大的情况下，而桶中结点个数很少，这样导致一个结点后的元素个数很多，遍历时元素效率就很低，所以桶的也会进行扩容（更改10），然后重构哈希表（桶）。而每当结点个数等于桶中元素个数时就会扩容。