C++关联容器

关联容器

关联容器支持高效的关键字查找和访问，两个主要的关联容器是map和set，map中的元素是一些关键字-值(key-value)对:关键字起到索引的作用，值表示与索引相关联的数据。set中每个元素只包含一个关键字：set支持高效的关键字查询操作，检查一个给定关键字是否在set中。

标准库提供了8个关联容器，这8个容器的不同体现在关键字是否能重复，是否按顺序保存元素，这里的顺序不是指元素添加顺序，而是关键字的比较顺序，multi表示关键字可重复，unordered表示元素是无序保存的。

• map
• set
• multimap，
• multiset，
• unordered_map
• unordered_set
• unordered_multimap
• unordered_multiset

关键字类型的要求

对于有序容器，关键字类型必须定义元素比较的方法，默认情况下标准库使用关键字类型的<运算符来比较，也可以在创建有序容器时自定义比较操作函数。

bool myCompare(int value1, int value2)
{
    return value1 < value2;
}

int main()
{
    map<string, int, decltype(myCompare)*> myMap1;
    map<string, int> myMap2;
    system("pause");
}

pair类型

map的元素是pair类型，其中first成员存储关键字，second成员存储值，使用make_pair可以创建一个pair。

int main()
{
    map<string, int> myMap;
    myMap["hello"] = 666;
    cout<< myMap.begin()->first <<endl;//hello
    cout << myMap.begin()->second << endl;//666
    system("pause");
}
 

关联容器中的类型

关联容器中表示容器关键字和值的类型：

• key_type，关键字类型。
• mapped_type，关键字关联的类型，只用于map。
• value_type，对于set，与key_type相同，对于map，为pair<const key_type,mapped_type>。

关联容器迭代器

当解引用一个关联容器迭代器时，返回一个类型为容器的value_type的值的引用，set的迭代器只允许读取元素的值，但不能修改。
遍历map:

int main()
{
    std::map<std::string, int> myMap;
    myMap["xiaoming"] = 1;
    myMap["xiaohong"] = 100;
    myMap["xiaozhang"] = 200;
    
    auto iter = myMap.cbegin();
    while (iter!=myMap.cend()) {
        std::cout << iter->first << ":" << iter->second << std::endl;
        iter++;
    }
    system("pause");
    return 0;
}

关联容器和算法

我们通常不对关联容器使用泛型算法，因为关键字是const的这一特性意味不能将关联容器传递给修改或重排容器元素的算法。关联容器可用于只读取元素的算法，使用关联容器专用的find函数比泛型find快的多。

关联容器添加元素

关联容器的insert成员向容器添加一个元素或一个元素范围，由于map和set包含不重复的关键字，因此插入一个已存在的元素对容器没任何影响，和顺序容器类似，也可以使用emplace构造元素。

添加单一元素的insert和emplace返回一个pair，其中first成员是一个迭代器指向新元素，second成员是一个bool值，指出元素是插入成功还是已经存在于容器中。

关联容器删除元素

关联容器定义了三个版本的erase，与顺序容器一样，我们可以通过传递erase一个迭代器或一个迭代器对来删除一个元素或一个元素范围。

关联容器提供一个额外的erase操作，它接受一个key_type参数，删除所有匹配给定关键字的元素，返回实际删除的元素的数量。

int main()
{
    multimap<string, int> myMap;
    myMap.insert({ "key", 1 });
    myMap.insert({ "key", 2 });
    myMap.insert({ "key", 3 });
    myMap.insert({ "key", 4 });
    cout << myMap.erase("key") << endl;//4
    system("pause");
}
 

map的下标操作

map和unordered_map提供了下标运算符和一个对应的at函数，set没有与关键字相关联的值，所以不支持下标操作，multimap和unorder_multimap可能有多个值与一个关键字关联，所以也不支持下标操作。

map下标运算符接受一个索引(关键字)获取与此关键字相关联的值，值得注意的是，如果关键字不在map中，会为它创建一个元素插入到map，关联值将进行值初始化。由于下标运算符可能插入一个新元素，所以只可以对非const的map使用下标操作。

int main()
{
    map<string, int> myMap;
    cout << myMap["test"] << endl;//0
    cout << myMap.size() << endl;//1
    system("pause");
}

与下标运算符不同，at会检查关键字是否存在，不存在则抛出out_of_range异常。

int main()
{
    map<string, int> myMap;
    if (myMap["test1"] == 1) {
        cout << "test1==1" << endl;
    }
    try {
        if (myMap.at("test2") == 1) {//关键字不存在，抛出异常
            cout << "test2==1" << endl;
        }
    }
    catch(...){
        cout << "catch exception" << endl;
    }
    cout << myMap.size() << endl;//1
    system("pause");
}

关联容器访问元素

关联容器提供多种查找一个指定元素的方法：

无序容器

无序容器不是使用比较运算符来组织元素，而是使用一个哈希函数和关键字类型的==运算符，在关键字类型的元素没有明显的顺序关系的情况下，使用无序容器更好，因为维护元素的顺序有一定代价。

无序容器在存储上组织为一组桶，每个桶保存零个或多个元素，无序容器使用哈希函数将元素映射到桶。为了访问一个元素，容器首先计算元素的哈希值，它指出应该搜索哪个桶，容器将哈希值相同的元素保存到相同的桶中，如果容器允许重复关键字，所有具有相同关键字的元素也都会在同一个桶中。

标准库为内置类型(包括指针)，一些标准库类型(例如string和智能指针)提供了hash模板，因此我们可以直接定义关键字为上述类型的无序容器。

我们可以提供函数替换哈希函数和==运算符：

class MyClass 
{
public:
    string value;
};

size_t myHash(const MyClass& value)
{
    return hash<string>()(value.value);
}
 
bool myEqual(const MyClass& value1, const MyClass& value2)
{
    return value1.value== value2.value;
}

int main()
{
    unordered_map<string, int,decltype(myHash)*,decltype(myEqual)*> myMap;
    system("pause");
}