C++之关联容器

介绍

关联容器支持高效的关键字查找和访问。C++提供了两个主要的关联容器类型：map和set。从这两个类型延伸出八个关联容器，分为两类：关键字带不带multi，带不带unordered。具体详情会在后面讲解。
map存储的是键值对，键又称为关键字起到索引的作用。值表示与索引相关联的数据。set则只是一些数据的集合，可以查询某个关键字是否存在于set中。
map和multimap在头文件map中，set和multiset在头文件set中。unordered_map和unordered_set等无序容器在头文件unordered_map或unordered_set中。

定义关联容器

定义一个map，必须既指明关键字类型又指明值类型。定义一个set只需要指明关键字类型。每个关联容器都有默认构造函数，用来创建空容器。也可以用大括号来对关联容器进行值初始化。值初始化set可以向vector一样进行初始化。值初始化map则需要传入关键字和值并使用大括号包起来。

set<string> example_set({"apple", "banana", "orange"});
map<string, int> example_map({
    {"Alice" , 3},
    {"Bob", 5},
    {"John", 2}
});

set和map都只允许关键字出现一次，如果想要定义多个关键字，需要使用multimap和multiset。

set<string> example_set({"apple", "banana", "orange", "orange"});
multiset<string> example_multiset({"apple", "banana", "orange", "orange"});
map<string, int> example_map({
    {"Alice" , 3},
    {"Bob", 5},
    {"John", 2},
    {"John", 4}
});
multimap<string, int> example_multimap({
    {"Alice" , 3},
    {"Bob", 5},
    {"John", 2},
    {"John", 4}
});

cout << example_map.size() << endl; // 3
cout << example_multimap.size() << endl;    // 4
cout << example_set.size() << endl; // 3
cout << example_multiset.size() << endl;    // 4

需要注意的是，我们所指定的关键字类型必须定义一个严格弱序。因此要想在关联容器中指定我们的类，需要在指定关键字类型后面提供一个指向比较函数的指针。构造函数传入比较函数。例如：

class MyClass
{
public:
    MyClass(int val): val(val) {}
    int val;

    static bool compare(const MyClass& c1, const MyClass& c2);
};

bool MyClass::compare(const MyClass &c1, const MyClass &c2)
{
    return c1.val < c2.val; // 严格弱序
}

int main()
{
    multiset<MyClass, decltype(MyClass::compare)*> correct_set(MyClass::compare); // 编译通过
    correct_set.insert(MyClass(2));
    correct_set.insert(MyClass(1));
    multimap<MyClass, size_t, decltype(MyClass::compare)*> correct_map(MyClass::compare);
    correct_map.insert(make_pair(MyClass(2), 5));
    correct_map.insert(make_pair(MyClass(9), 5));
}

pair类型

在讲述关联容器的操作前，需要了解pair标准库类型，在头文件utility中。pair数据类型十分简单，定义时需要指定两个数据类型，用于存储两个类型的数据，例如下面这样。

pair<string, size_t> word_count;

一般情况下，我们定义pair类型可以不用手动指定类型，可以使用make_pair来自动推导。

auto word_count2 = make_pair("Hello", 2); // 自动推导为 pair<const char *, int>)

可以使用数据成员first和second来访问其对应的数据。

    auto word_count2 = make_pair("Hello", 2); // 自动推导为 pair<const char *, int>)
    cout << word_count2.first << " " << word_count2.second << endl; // Hello 2

关联容器操作

类型别名

关联容器新增了三个类型别名：

1. key_type：表示关联容器中键的类型。
2. mapped_type：仅适用于std::map，表示映射到每个键的值的类型。
3. value_type：对于std::map，它等同于std::pair<const Key, T>，其中Key是键的类型，T是值的类型；对于std::set，它等同于键的类型。

迭代器

解引用一个关联容器类型的迭代器，会得到一个容器为value_type的值的引用。set类型的迭代器是const的。

算法

关联容器使用泛型算法是一个坏主意。通常我们只需要搜索关联容器。例如find，使用泛型算法的find会顺序搜索关键字，这样做map和set的优势荡然无存。普通的map和set的数据结构是一棵红黑树，支持O(logN)的查找。

调用其成员函数find就能最大性能保证搜索。具体的操作会在后面详细讲解。

添加元素

使用insert成员为关联容器添加元素，如果是普通不包含重复关键字的map和set，插入一个以存在的元素没有任何影响。insert有两个版本：

• c.insert(b, e)：接受两个迭代器，插入迭代器中的内容；
• c.insert({elem1, elem2})：接受初始化器列表，添加到容器中。

map插入的元素必须是一个pair类型。

vector<int> nums{2,5,3,1,7,5,0};
set<int> example_set;
example_set.insert(6);  // {6}
example_set.insert({4,8,9});    // {4, 6, 8, 9}
example_set.insert(nums.begin(), nums.end());   // {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

map<string, size_t> word_count;
word_count.insert({ "apple", 5 });
word_count.insert( make_pair("banana", 3));
word_count.insert(pair<string, size_t>("pineapple", 10));
word_count.insert(decltype(word_count)::value_type("orange", 8));

insert或emplace的值依赖于容器类型和返回参数。只插入单个关键字，其返回值是一个pair类型。第一个元素是一个指向给定关键字元素的迭代器，第二个元素是一个bool值。若返回的bool为false，则代表插入失败，第一个元素也为空。

删除元素

和insert一样，关联容器提供erase来删除元素。其参数可以是一个迭代器，或是一对迭代器，此外还提供接受一个key_type参数的元素，用于删除单个元素，其返回值为删除元素的数量。

对于不保存重复关键字的容器，其erase的返回值始终为0或1，0代表没有找到元素。

map的下标操作

map和unordered_map提供了下标运算符和一个对应的at函数。set不支持下标。不能对一个multi类型的容器进行下标操作。

map下标支持一个关键字，如果这个关键字不存在，map会自动创建一个该关键字类型的元素，并对值进行初始化。

map<string, size_t> c;
c["hello"] = 1; // 不会报错

访问元素

• find(k)会寻找关键字为参数的元素的迭代器，如果找不到，则会返回容器的尾迭代器。
• count(k)会做的更多一些，它会返回一个指定元素在容器中的个数。如果不需要计数，则最好使用find。
• lower_bound(k)返回一个迭代器，指向第一个关键字不小于k的元素。
• upper_bound(k)返回一个迭代器，指向第一个关键字大于k的元素。

lower_bound和upper_bound不适用于无序容器。

• c.equal_range(k)会返回一个迭代器pair，表示关键字等于k的元素范围。

multimap<string, size_t> word_count;
word_count.insert(make_pair("hello", 2));
word_count.insert(make_pair("hello", 5));
word_count.insert(make_pair("world", 9));

// multimap遍历全部关键字的方法
// 第一种：统计法
auto left = word_count.find("hello");
auto count = word_count.count("hello");
if (left != word_count.end())
{
    while (count--)
    {
        cout << left->first << ": " << left->second << endl;
        ++left;
    }
}

// 第二种：用lower_bound和upper_bound
string key = "hello";
for (auto i = word_count.lower_bound(key); i != word_count.upper_bound(key); ++i)
{
    cout << i->first << ": " << i->second << endl;
}

// 第三种：直球
auto range_pair = word_count.equal_range("hello");
for (auto i = range_pair.first; i != range_pair.second; ++i)
{
    cout << i->first << ": " << i->second << endl;
}

附件

源代码