C++每日一记：关联容器

关联容器

概述

关联容器用于关键字的查找和访问，主要包括两种类型：map 和 set. map 中的元素是一些键值对，关键字起到了索引的作用，值则表示索引相关的数据。set 的每个元素只包含一个关键字，set 支持高效的关键字查询操作。

定义关联容器

定义 map 时需要指定关键字和值的类型，而定义 set 只需要指定关键字类型。set 可以使用 {} 进行初始化，map 初始化时必须将将键值对放到花括号中 { key, value }.

    void TestMapInit()
    {
        using namespace std;

        map<string, size_t> word_count;
        set<string> exclude = {"a", "b", "c", "a"};
        map<string, string> authors = { { "Yuan", "Rui" }, { "Github", "Banana" }, {"Yuan", "2"} };

        for (auto item : authors)
        {
            cout << item.first << " " << item.second << endl;
        }        
    }

需要注意的是，map 和 set 在初始化时，支持重复的键值。出现重复时，根据关键字的顺序保留第一个。上述代码最终输出如下：

Github Banana
Yuan Rui

pair 类型

map中的元素是 pair. pair 类型定义在头文件 utility 中，一个 pair 保存两个数据成员。pair 包含两个成员 first 和 second，一般 first 为关键字，second 为值。pair 的典型定义如下：

pair<std::string, std::string> one;
pair<std::string, int> two{ "test", 1 };

向 map 添加元素

对 map 进行 insert 操作时，元素类型必须是 pair. 向 map 中插入元素的方法有4种，参考如下：

    void TestMapInsert()
    {
        using namespace std;

        map<string, size_t> word_count;
        word_count.insert({ "test", 1 });
        word_count.insert(make_pair("abc", 2));
        word_count.insert(make_pair("abc", 22)); // insert 成员函数支持插入重复的关键字, 这行数据会被忽略
        word_count.insert(pair<string, size_t>("cde", 3));
        word_count.insert(map<string, size_t>::value_type("fgh", 4));        
    }
}

insert 成员函数会返回一个pair，pair 的 first 成员是一个迭代器，指向给定关键字的元素；second 成员是一个 bool 值，指出元素是插入成功还是在已经在容器中。

查找关联容器中的元素

关联容器支持多种查找指定元素的方法。

find(k): 指向第一个关键字为k的元素，若k不在容器中，则返回尾后迭代器。
count(k)：返回关键字等于k的元素数量，对于不重复关键字的容器，返回值永远是0或1
lower_bound(k)：返回一个迭代器，指向第一个关键字不小于k的元素
upper_bound(k)：返回一个迭代器，指向第一个关键字大于k的元素
equal_range(k)：返回一个迭代器pair，表示关键字等于k的元素范围，若k不存在，pair的两个成员均等于 end()

相关示例代码如下：

    void TestMapFind()
    {
        using namespace std;

        map<string, size_t> word_count;
        word_count.insert({ "test", 1 });
        word_count.insert(make_pair("abc", 2));
        word_count.insert(make_pair("ABC", 123));
        word_count.insert(make_pair("abc", 22)); // insert 成员函数支持插入重复的关键字, 这行数据会被忽略
        word_count.insert(pair<string, size_t>("cde", 3));
        word_count.insert(map<string, size_t>::value_type("fgh", 4));

        string search_item = "a";
        if(word_count.find(search_item) == word_count.end())
        {
            cout << "a is not in the map" << endl;
        }

        search_item = "abc";
        auto find_cnt = word_count.count(search_item);
        auto iter = word_count.find(search_item);
        cout << "map 查找方式 1" << endl;
        while (find_cnt)
        {
            cout << iter->second << endl;
            ++iter;
            --find_cnt;
        }

        cout << "map 查找方式 2" << endl;
        for (auto beg = word_count.lower_bound(search_item), 
            end = word_count.upper_bound(search_item); beg != end; ++ beg)
        {
            cout << beg->second << endl;
        }

        cout << "map 查找方式 3" << endl;
        for (auto pos = word_count.equal_range(search_item); pos.first != pos.second; ++pos.first)
        {
            cout << pos.first->second << endl;
        }
    }

yuanrui / blog