C++_STL常用容器总结：对组pair中关联容器与顺序容器

1. 组pair

在 C++ STL 中，pair 是其中一个最常用的类型，它位于头文件 <utility> 中。实际上，pair 可以看作是一个单元素的 tuple 类型。pair 将两个值组合在一起，这两个值可以是同一类型或不同类型。pair 的第一个元素可以通过 first 访问，第二个元素可以通过 second 访问。

#include <utility>
using namespace std;
pair <int, int> p1 = { 1, 2 };
cout << p1.first << " " << p1.second << endl;
pair <double, string> p2 = make_pair(1.23, "hello world!");
cout << p2.first << " " << p2.second << endl;

2. 关联容器

与普通数组不同，关联容器中的元素是按一定规则自动排序的。STL 中提供的关联容器包括 set、multiset、map 和 multimap。

2.1 set

set 是一种元素唯一、按照一定规则排序的容器。它的底层实现是二叉搜索树。集合中的元素默认按照小到大的排序规则进行排序。可以通过自定义排序规则来改变元素排序方式，也可以在插入数据时使用自定义类的重载操作符。

#include <set>
using namespace std;
// 通过自定义类的重载操作符
class point {
public:
    int x;
    int y;
    point(int _x, int _y) : x(_x), y(_y) {}
    bool operator <(const point &other) const {
        if (x != other.x) {
            return x < other.x; // 按 x 从小到大排序
        } else {
            return y < other.y; // 在 x 相同时，按 y 从小到大排序
        }
    }
};
set <int> s1;
s1.insert(1);
s1.insert(3);
s1.insert(2);
set <point> s2;
s2.insert(point(1, 2));
s2.insert(point(1, 1));
s2.insert(point(2, 1));

2.2 multiset

multiset 也是一种元素唯一、按一定规则排序的容器，它与 set 的区别在于同一个元素在 multiset 中可以有多个副本。也可以用与 set 中相同的方式自定义排序规则。

#include <set>
using namespace std;
multiset <int> s1;
s1.insert(1);
s1.insert(3);
s1.insert(2);
s1.insert(2);
multiset <int>::iterator it = s1.find(2); // 返回一个迭代器，指向包含 2 元素的位置
s1.erase(it); // 将包含 2 元素的位置删除

2.3 map

map 是一种包含有键值对（key-value）的容器，就像一个字典一样。它包含一个 key 值和与其对应的 value 值。key 值可以看作是 map 中元素的索引，所以在 map 中，key 值也是唯一性且有序性的。默认情况下，key 值按照从小到大的顺序进行排序。也可以使用自定义的比较规则来进行排序。

#include <map>
using namespace std;
map <string, int> m1;
m1["aaa"] = 1;
m1["bbb"] = 2;
m1["ccc"] = 3;
map <string, int>::iterator it = m1.find("bbb"); // 返回一个迭代器，指向键值为 "bbb" 的元素所在的位置
m1.erase(it); // 将键值为 "bbb" 的元素删除

2.4 multimap

multimap 与 map 一样，只不过键值可以重复。可以使用与 map 相同的方式查询和操作 multimap 中的数据。

3. 顺序容器

顺序容器中的元素是按插入次序排序的。STL 中提供的顺序容器包括 vector、deque、list。

3.1 vector

vector 是一种动态数组，即封装了大部分 C 数组的相关操作接口，同时支持动态的数组调整。我们可以通过 at、[]、front、back 等方法访问元素。vector 的实现是在连续的存储区域中存储元素。当元素数量超过存储区域的大小后，将会重新分配一块更大的存储区域， 并把原来的元素全部拷贝过去。

#include <vector>
using namespace std;
vector <int> v1;
v1.push_back(10);
v1.push_back(9);
vector <int>::iterator it = v1.begin(); // 返回一个迭代器，指向 vector 的第一个元素
int x = v1.front(); // 返回 vector 的第一个元素
int y = v1[1]; // 返回 vector 的第二个元素
int z = v1.at(1); // 返回 vector 的第二个元素

3.2 deque

deque 也是一种动态数组，与 vector 不同的是，deque 的实现是在多个连续的存储区域中存储元素。deque 支持从两端进行插入和删除操作，可以使用 push_front、push_back、pop_front、pop_back 等方法进行操作。

#include <deque>
using namespace std;
deque <int> d1;
d1.push_back(10);
d1.push_back(9);
d1.push_front(8);
deque <int>::iterator it = d1.begin(); // 返回一个迭代器，指向 deque 的第一个元素
int x = d1.front(); // 返回 deque 的第一个元素
int y = d1.back(); // 返回 deque 的最后一个元素
d1.pop_front(); // 将 deque 的第一个元素弹出

3.3 list

list 是双向链表。它的实现是非连续存储的，每一个元素都包含了前驱和后继指针。在 list 中插入或删除一个元素不会影响链表中其它元素的指针，并且插入或删除操作的时间复杂度为常数级别，而非线性级别。list 不支持随机访问元素，因为没有相关的指针。

#include <list>
using namespace std;
list <int> l1;
l1.push_back(10);
l1.push_back(9);
list <int>::iterator it = l1.begin(); // 返回一个迭代器，指向 list 的第一个元素
int x = l1.front(); // 返回 list 的第一个元素
l1.pop_front(); // 将 list 的第一个元素弹出