《c++ primer笔记》第十一章关联容器_市场资讯

《c++ primer笔记》第十一章关联容器

创始人

2025-05-31 13:36:18

0次

前言

关联容器和顺序容器的许多操作都很类似，本章主要简单介绍了4种关联容器，包括如何定义、操作关联容器，内部原理也有简单涉及。

文章目录
一、关联容器
1.1定义关联容器
1.2关联容器操作
1.3无序容器

一、关联容器

关联容器支持高效的关键字查找和访问，两个主要的关联容器类型是map和set。标准库提供8个关联容器，它们的不同有三点：1）set或者map；2）关键字是否重复；3）元素保存顺序。

map

map类型也叫关联数组，意思它与数组类似，不同之处在于索引可以不是一个整数。类似顺序容器，关联容器也是模板

set

set是关键字的简单集合，下面是一个map和set简单使用的案例，代码的功能就是从用户输入的单词中，抛弃那些在set中出现的单词。

map word_count;
set exclude = { " The", "But", "OR"};
string word;
while(cin >> word) {if(exclude.find(word) == exclude.end())++word_count[word];
}

1.1定义关联容器

关联容器不支持顺序容器的位置相关操作，因为关联容器中元素是根据关键字存储的。同时也不接受构造函数或插入操作这些接受一个元素值和一个数量值的操作。关联容器的迭代器都是双向的。

每个关联容器都定义了一个默认构造函数，它创建一个指定类型的空容器。

map word_count; // 默认初始化
set exclude = { " The", "But", "OR"};
map word_count = { {"1", 1} ,{"2", 2} ,{"3", 3}}; // 列表初始化

初始化mutimap或multiset

一个map和set中的关键字必须是唯一的，对于multimap和multiset没有限制。

vec; // 含有20个数字，0-9 重复一次
set s(vec.begin(), vec.end()); // 10
multiset mset(vec.begin(), vec.end()); // 20

关键字类型的要求

前面提到有些算法比如sort的比较操作我们可以自定义，类似地，我们也可以在有序关联容器上定义比较操作。注意所提供的比较操作在关键字类型上定义一个严格弱序（小于等于）。规则就是不能出现两个一模一样的关键字。下面是一个案例，第一行代码是错误的，因为我们假如MyClass并没有<运算符，当我们有一个自定义的比较函数cmp，我们就可以在定义multiset时加入比较函数的指针类型。

mutiset; // 错误
mutiset;

pair类型

pair定义在头文件utilty中，一个pair保存两个数据成员。pair的默认构造函数对数据成员进行值初始化。

pair anon;
pair word_count;
pair> line;

pair的数据成员是public的，分别为first和second。

创建pair对象的函数

pair process(vector &v) {if(!v.empty())return {v.back(), v.back().size()}; // 列表初始化，早期C++版本只允许显示构造返回值 pair(v.back, v.back.size())elsereturn pair(); // 隐式构造返回值
}

1.2关联容器操作

对于set类型，key_type和value_type是一样的，set中保存的值就是关键字。在map中，每个元素都是是一个pair对象，包含一个关键字和一个关联的值。由于不能改变一个元素的关键字，因此这些pair的关键字部分是const的。

set::value_type v1; // string
set::key_type v2; // string
map::value_type v3; // pair
map::key_type v4; //string
map::mapped_type v5;  // int

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

auto map_it = word_count.begin();
cout << map_it->first; // 指向关键字
map_it->first = "new key"; // 错误，关键字时const

set的迭代器是const

set iset = {0,1,2,4,5,,6,6};
set::iterator set_it = iset.begin();
if(set_it != iset.end()) {*set_it = 42; // 错误，set中的关键字为只读cout << *set_it << endl;
}

关联容器和算法

一般不对关联容器使用泛型算法，因为关键字的类型为const。当然，对于一些只读元素的算法关联容器是适用的，但是这类算法都要搜索序列，而关联容器中的元素不能通过它们的关键字进行查询（没太懂）。

添加元素

insert向容器中添加一个元素或一个范围，即使添加的元素已经存在也不会对容器造成影响。

vector ivec = {2,4,5,6,7,8};
set set2;
set2.insert(ivec.begin(), ivec.end()); //{2,4,5,6,7,8}
set.inster({{2,4,5,6,7,8}}); //{2,4,5,6,7,8}

对一个map进行insert操作时，必须记住元素的类型是pair

word_count.insert({word, 1});
word_count.insert(make_pair(word,1));
word_count.insert(pair(word, 1));
word_count.insert(pair::value_type(word, 1));

检测insert的返回值

对于不包含重复关键字的容器，添加单一元素的insert和emplace版本返回一个pair，first是一个迭代器，指向具有关键字的元素；second是一个bool值，指出元素是否插入成功。

对允许重复关键字的容器，接受单个元素的insert操作返回一个指向新元素的迭代器。

删除元素

关联容器有三个版本的erase。对于不重复的容器，返回值总是0或1；允许重复的容器删除元素的数量可能大于1。

map的下标操作

map和unordered_map容器都提供了下标运算符和一个对应的at函数。set不支持下标，因为set没有与关键字相关联的值。map可以像数组一样使用[]获取关键字对应的值，值得注意的是，如果原map中没有这个关键字，则会将当前关键字存入map，对应的值会进行值初始化。