C++ STL 关联式容器

pair数据类型

关联式容器存储的是“键值对”形式的数据，其中第一个元素作为键（key），第二个元素作为值（value）。键值对”并不是普通类型数据，C++ STL 标准库提供了 pair 类模板，其专门用来将 2 个普通元素 first 和 second（可以是 C++ 基本数据类型、结构体、类自定的类型）创建成一个新元素<first, second>。

pair 类模板定义在<utility>头文件中。

#include <utility>
pair<string, double> pair1;//空pair
pair<string, double> pair2("h", 0.3);//初始化
pair<string, double> pair3(pair2);//复制构造

关联式容器 map

http://c.biancheng.net/view/7173.html

map 容器存储的都是 pair 对象，也就是用 pair 类模板创建的键值对。其中，各个键值对的键和值可以是任意数据类型，包括 C++ 基本数据类型（int、double 等）、使用结构体或类自定义的类型。

通常情况下，map 容器中存储的各个键值对都选用 string 字符串作为键的类型。

与此同时，在使用 map 容器存储多个键值对时，该容器会自动根据各键值对的键的大小，按照既定的规则进行排序。默认情况下，map 容器选用std::less<T>排序规则（其中 T 表示键的数据类型），其会根据键的大小对所有键值对做升序排序。当然，根据实际情况的需要，我们可以手动指定 map 容器的排序规则，既可以选用 STL 标准库中提供的其它排序规则（比如std::greater<T>），也可以自定义排序规则。

另外需要注意的是，使用 map 容器存储的各个键值对，键的值既不能重复也不能被修改。换句话说，map 容器中存储的各个键值对不仅键的值独一无二，键的类型也会用 const 修饰，这意味着只要键值对被存储到 map 容器中，其键的值将不能再做任何修改。

前面提到，map 容器存储的都是 pair 类型的键值对元素，更确切的说，该容器存储的都是 pair<const K, T> 类型（其中 K 和 T 分别表示键和值的数据类型）的键值对元素。

引入：

#include <map>
using namespace std;

map容器的模板定义如下：

template < class Key,                                     // 指定键（key）的类型
           class T,                                       // 指定值（value）的类型
           class Compare = less<Key>,                     // 指定排序规则
           class Alloc = allocator<pair<const Key,T> >    // 指定分配器对象的类型
           > class map;

可以看到，map 容器模板有 4 个参数，其中后 2 个参数都设有默认值。大多数场景中，我们只需要设定前 2 个参数的值，有些场景可能会用到第 3 个参数，但最后一个参数几乎不会用到。

#include <map>
using namespace std;

map<string, int> m;//构建空的map容器
map<string, int> m{{"a",1},{"b",2}};//构建map容器并初始化
//复制构造
map<string, int> m{make_pair("a", 1), make_pair("b", 2)};//同上

//插入
m.insert({"a", 1});
m.insert(make_pair("a", 1));
m.insert(pair<string, int>("a", 1));
m["a"] = 1;
m.emplace("a", 1);

//查找
iter = m.find("a");
if(iter != m.end())
    cout << "have found";
num = m.count("a");//num=0或1，存在为1，不存在为0

//删除
iter = m.find("a");
m.erase(iter);//迭代器删除
m.erase(m.begin(), m.end());//迭代器范围删除，等同于m.clear()
m.erase("a");//关键字删除
m.clear();//清空

//迭代器
m.begin();

//容量
m.size();
m.max_size();
m.empty();

关联式容器 set

使用 set 容器存储的各个元素的值必须各不相同。更重要的是，从语法上讲 set 容器并没有强制对存储元素的类型做 const 修饰，即 set 容器中存储的元素的值是可以修改的。但是，C++ 标准为了防止用户修改容器中元素的值，对所有可能会实现此操作的行为做了限制，使得在正常情况下，用户是无法做到修改 set 容器中元素的值的。

对于初学者来说，切勿尝试直接修改 set 容器中已存储元素的值，这很有可能破坏 set 容器中元素的有序性，最正确的修改 set 容器中元素值的做法是：先删除该元素，然后再添加一个修改后的元素。

值得一提的是，set 容器定义于<set>头文件，并位于 std 命名空间中。

set 容器的类模板定义如下：

template < class T,                        // 键 key 和值 value 的类型
           class Compare = less<T>,        // 指定 set 容器内部的排序规则
           class Alloc = allocator<T>      // 指定分配器对象的类型
           > class set;

注意，由于 set 容器存储的各个键值对，其键和值完全相同，也就意味着它们的类型相同，因此 set 容器类模板的定义中，仅有第 1 个参数用于设定存储数据的类型。

对于 set 类模板中的 3 个参数，后 2 个参数自带默认值，且几乎所有场景中只需使用前 2 个参数，第 3 个参数不会用到。

#include <set>
using namespace std;

set<string> myset;//创建空的set容器，采用默认的std::less<T>规则，会对存储的 string 类型元素做升序排序
set<string> myset{"a", "b", "c"};//创建set容器并初始化

//同map
//插入
myset.insert("d");
myset.emplace("d");

//查找
iter = myset.find("a");
if(iter != myset.end())
    cout << "have found";
num = myset.count("a");//num=0或1，存在为1，不存在为0

//删除
iter = myset.find("a");
myset.erase(iter);//迭代器删除
myset.erase(m.begin(), m.end());//迭代器范围删除，等同于m.clear()
myset.erase("a");//关键字删除
myset.clear();//清空

//迭代器
myset.begin();

//容量
myset.size();
myset.max_size();
myset.empty();

//自定义数据类型
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
    friend bool operator< (const shared_ptr<ListNode> &p1, const shared_ptr<ListNode> &p2) {
        return p1->val < p2->val;
    }
    friend bool operator> (const shared_ptr<ListNode> &p1, const shared_ptr<ListNode> &p2) {
        return p1->val > p2->val;
    }
};
//仿函数
struct cmp {
    //set/map要求key是不可更改的，所以重载比较运算符或者重写仿函数时，需要确保函数参数为const，对于指针，则需要确保其值不变即其指向不变
    bool operator() (ListNode* const&p1, ListNode* const&p2) {
        return p1->val < p2->val;
    }
};

void test_set2() {
    int a[] = {5, 3, 8, 1 ,9};
    auto phead = new ListNode(-1);
    auto p = phead;
    for (auto &v: a) {
        p->next = new ListNode(v);
        p = p->next;
    }
    /*
     * set存储指针数据，第一种写法是符合预期的，第二种写法只会按照指针地址进行排序
     * 可以使用智能指针
     */
    set<ListNode*, cmp> ms;//第一种写法
    //set<ListNode*> ms;//第二种写法
    p = phead->next;
    while (p) {
        ms.insert(p);
        p = p->next;
    }
    for (auto & v: ms) {
        cout << v->val << "  ";
    }
}

void test_set3() {
    //使用智能指针
    int a[] = {5, 3, 8, 1 ,9};
    auto phead = make_shared<ListNode>(-1);
    auto p = phead;
    set<shared_ptr<ListNode>> ms;
    for (auto &v: a) {
        auto temp = make_shared<ListNode>(v);
        auto mp = p.get();
        mp->next = temp.get();
        p = temp;
        ms.insert(temp);
        cout << temp.get()->val << "  " << temp.get() << endl;
    }
    cout << endl;
    for (auto & v: ms) {
        cout << v->val << "  " << v->next << "\n";
    }
}
void test_set4() {
    //使用智能指针
    int a[] = {5, 3, 8, 1 ,9};
    auto phead = new ListNode(-1);
    auto p = phead;
    for (auto &v: a) {
        auto temp = new ListNode(v);
        p->next = temp;
        p = p->next;
        cout << temp->val << "  " << temp << endl;
    }
    cout << endl;
    set<shared_ptr<ListNode>> ms;
    p = phead->next;
    while (p) {
        auto temp = shared_ptr<ListNode>(p);
        ms.insert(temp);
        p = p->next;
    }
    for (auto & v: ms) {
        cout << v->val << "  " << v->next << "\n";
    }
}