Sec11 关联容器
-
两个主要的关联容器:
map
:key-value对,关键字起到索引的作用,值表示与索引关联的数据
例子:字典set
:每个元素只包含一个关键字,set支持高效的关键字查询操作
-
STL提供8个关联容器
按关键字有序保存元素 map: 关联数组 set: 关键字即值,只保存关键字 multimap: 关键字可重复的map multiset: 关键字可重复的set 无序集合(哈希阻止) unordered_map unordered_set unordered_multimap unordered_multiset
-
在set中找单词
set<string> exclude; if(exclude.find(word) == exclude.end()){ ++word_cound[word]; }
find返一个迭代器,如果给定关键字在set中,迭代器指向关键字,否则,find返回尾后迭代器
11.2 关联容器概述
-
定义set,只需指名关键词类型
定义map,需要指名关键词和value类型 -
关键字类型的要求
对于有序容器,map,multimap,set和multiset,关键字类型必须定义元素比较的方法,默认情况是用<,但也可以自定义
-
可以像一个算法提供我们自己定义的比较操作。所提供的操作必须在关键字类型上定义一个严格弱序。
-
使用关键字类型的比较函数
用来阻止一个容器中元素的操作的类型也是该容器类型的一部分。bool compareISBN(const Sales_data &lhs, const Sales_data &rhs) { return lhs.isbn() < rhs.isbn(); } multiset<Sales_data, decltype(compareISBN)*> bookstore(compareISBN)
常常用decltype指出自定义操作的类型,注意,当用decltype来获得一个函数指针类型时,必须加上一个*来指出我们要使用一个给定函数类型的指针。然后用compareISBN来初始化bookstore。这样添加元素的时候就可以使用自定义排序类型了
-
-
pair类型
定义在头文件utility中。创建pair必须提供两个类型名。- 比较操作:
是先比较first再比较second的
- 比较操作:
11.3 关联容器操作
key_type; 此容器类型的关键字类型
mapped_type; 每个关键字关联的类型,只适用于map
value_type; 对于set,与key_type相同,对于map,为pair<const key_type, mapped_type>
-
关联容器迭代器
解引用一个关联容器迭代器时,我们会得到一个类型为容器的value_type的值的引用。
记得对map而言,value_type是一个pair类型,记得用first和second来访问。iter->first,iter->second
-
set的迭代器是const的
set的元素仅可读 -
遍历是按照字典序排列的。升序
-
map<int, int> m; auto it = m.begin(); it->second = 0;
-
-
算法:
通常不用泛型算法。通常用自己定义的find。要快得多(hash) -
添加元素
用insert,但是注意对于set和map来说,插入一个已经存在的元素对容器没有影响
-
注意,对map插入元素,元素必须是pair
// 向word_count插入word的4种方法 word_count.insert({word, 1}); word_count.insert(make_pair(word, 1)); word_count.insert(pair<string, size_t>(word, 1)); word_count.insert(map<string, size_t>::value_type(word, 1));
用insert会返回一个迭代器,第一个first包含指向具有指定关键字的元素,以及一个指示插入是否成功的bool值
如果bool值为false,可能是插入了重复的值- 对于multi容器,接受单个元素的insert操作返回一个指向新元素的迭代器。无须返回bool值。
-
-
删除元素
erase有3个版本:- 传递一个迭代器
- 传递一个迭代器对
- 接受一个key_type参数,此版本删除所有匹配得给定关键字的元素,返回实际删除的元素数量
-
map的下标操作
map<string, size_t> word_count; word_count['Anna'] = 1;
注:使用一个不在容器内的下标,会添加这个容器并赋值!
c.at(k)
,单纯的访问关键字为k的元素,带参数检查- 对map来说,迭代器解引用与下标运算返回的类型不是一样的
对map下标运算,会获得mapped_type对象,当解引用时,得到value_type对象
- 对map来说,迭代器解引用与下标运算返回的类型不是一样的
-
访问元素
iset.find():返回一个迭代器,如果找到就是指向找到,如果未找到就返回尾迭代器
关心特定元素是否已在容器。
iset.count():返回元素个数 -
注:下标操作和at操作,只适用于非const的map和unorder_map
-
lower_bound(k), upper_bound(k)
返回迭代器,指向第一个关键字 不小于/不大于 k的元素
则:使用相同的关键字调用l和u会得到一个迭代器范围!表示具有该关键字的范围 -
equal_rage(k):
返回一个迭代器pair,表示关键字等于k的元素范围,若k不存在,则pair俩成员均为尾迭代器 -
为什么建议对map使用find代替下标操作:
对map和unordered_map类型,如果下标访问一个不存在的元素,则会加入进去!!!!
11.4 无序容器
原理一般是哈希 hash
- 操作:
find,insert等 - 存储上组织为 桶
bucket
每个桶保存0或者多个元素
// 桶接口
c.bucket_count();
c.max_bucket_count();
c.bucket_size(n);
c.bucket(k);
// 桶迭代
local_iterator; // 可以用访问桶中元素的迭代器版本
const_local_iterator;
c.begin(n), c.end();
c.cbegin(n), c.cend();
// 哈希策略
c.load_factor();
c.max_load_factor();
c.rehash(n);
c.reverse(n);
注意:hash函数是可重载的
标签:11,map,set,word,迭代,容器,关键字,Sec,Cpp From: https://www.cnblogs.com/orangestar/p/16995833.html