<参看 c++primer p407,ch11>
1. 概述
顺序容器包括vector、deque、list、forward_list、array、string，顺序容器都提供了快速(顺序)访问元素的能力, vector封装数组，list封装了链表
关联容器包括set、map, set存储的是key类型的元素, map存储的元素是{key,val}组成的pair类型,
创建一个pair可以 pair<T1,T2> p; 或者pair<T1,T2> p(v1,v2); 或 pair<T1,T2> p={v1,v2}; 或 make_pair(v1,v2)
访问一个pair则 p.first 和 p.second
set包含以下几种:
set<T> 容器保存 T 类型的对象，保存的对象不重复。元素有序，默认用 less 对象比较。可以用相等、不相等来判断对象是否相同。(内部采用红黑树 实现) 需要 #include <set> multiSet<T> 与set<T>区别在他可以保存重复的对象。#include <multiset>unorderd_set<T> 容器保存 T 类型的对象，保存的对象不重复。元素在容器中的位置由元素的哈希值决定。默认用 equal_to 判断元素是否相等。(内部采用hash表 实现),需要 include <unorderd_set> unordered_multiset<T> 与unorderd_set<T>区别在它可以保存重复的对象。include <unordered_multiset>
map包含以下几种
map<Tkey,Tval> 键值对集合(红黑树实现), 支持[ ]操作(set不支持因为没有获取val的意义)multimap<Tkey,Tval> key可以重复的键值对集合(红黑树实现),(不支持[ ] 操作因为可能返回多个val)unordered_map<Tkey,Tval> 键值对集合(hash表 实现),支持[ ]操作unordered_multimap<Tkey,Tval> key可以重复的键值对集合(hash表 实现)
set的迭代器是const的
map和set的插入删除效率比用其他序列容器高？ 因为内部采用红黑树/哈希表, 不涉及内存的拷贝和移动等操作
为何每次insert之后，以前保存的iterator不会失效？ iterator 相当于指向节点的指针，内存没有变，指向内存的指针不会失效(当然被删除的那个元素本身已经失效了)。相对于vector，每一次删除和插入，指针都有可能失效。因为为了保证内部数据的连续存放，vector管理的那块内存可能被扩容(伴随着释放和重新分配)。特别在和find等算法在一起使用时,牢记不要使用过期的iterator。
2. 一些接口
成员函数
含义
begin()
返回容器的第一个元素,map是pair类型,set则就是key的类型
end()
返回容器的最后一个元素
clear()
删除容器中的所有的元素
empty()
判断容器是否为空
max_size()
返回容器可能包含的元素最大个数
size()
返回当前容器中的元素个数
rbegin()
返回的值和end()相同
rend()
返回的值和rbegin()相同
———————
—————————————————————————————————-
erase(iterator)
删除iterator指向的元素
erase(first,second)
删除iterator first和second之间的元素
erase(k)
删除键值key=k的元素
find(k)
返回key=k对应的iterator，如果没找到则返回end()
insert(k)
将k插入到键值对集合中，返回值是pair<iterator,bool>，bool标志着插入是否成功，插入成功iterator代表插入的元素，若key=k的元素已经存在，则iterator表示已经存在的那个元素
insert(first,second)
将iteratot first到second之间的元素插入到set中，返回值是void.
———————
—————————————————————————————————-
lower_bound(key_value)
返回第一个大于等于key_value的iterator
upper_bound(key_value)
返回最后一个大于key_value的iterator
equal_range()
返回一对iterator，表示关键字等于
count()
用来查找set中某个某个键值出现的次数(对于key可重复的map/set常用)
此外 unsorted_map unsorted_set还提供了一些和bucket桶相关的api
3. demo1 统计word
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 map <string , size_t > word_cnt;set <string > exclude = {"and" ,"And" ,"or" ,"Or" ,"the" ,"The" }; string word;while (cin >>word){ if (exclude.find(word) == exclude.end()) { ++word_cnt[word]; } } for (const auto &w : word_cnt) cout <<"key=" <<w.first<<",val=" <<w.second<<endl ;
与上面等价的版本:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 map <string , size_t > word_cnt;set <string > exclude = {"and" ,"And" ,"or" ,"Or" ,"the" ,"The" }; string word;while (cin >>word){ if (exclude.find(word) == exclude.end()) { auto ret = word_cnt.insert({word,1 }); if (!ret.second) ++ret.first->second; } } auto map_it = word_cnt.cbegin(); while (map_it != word_cnt.cend()){ cout <<"key=" <<map_it->first<<",val=" <<map_it->second<<endl ; map_it++; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 #include <iostream> #include <set> using namespace std; int main() { int a[] = {1,2,3}; set<int> s(a,a+3); set<int>::iterator iter; if((iter = s.find(2)) != s.end()) { cout<<*iter<<endl;//输出为2 } return 0; }
4. demo2-map使用 参考
4.1. 声明 1 2 3 4 5 #include <map> map <int , string > ID_Name;map <int , string > ID_Name = { { 2015 , "Jim" }, { 2016 , "Tom" }, { 2017 , "Bob" } };
4.2. 插入 使用[ ]进行单个插入 1 2 3 4 map <int , string > ID_Name;ID_Name[2015 ] = "Tom" ;
使用insert进行单个和多个插入 1 2 3 4 5 6 7 8 9 10 11 pair<iterator,bool > insert (const value_type& val); iterator insert (const_iterator position, const value_type& val) ;void insert (InputIterator first, InputIterator last) void insert (initializer_list <value_type> il)
使用实例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include <iostream> #include <map> int main () std ::map <char , int > mymap; mymap.insert(std ::pair<char , int >('a' , 100 )); mymap.insert(std ::pair<char , int >('z' , 200 )); std ::pair<std ::map <char , int >::iterator, bool > ret; ret = mymap.insert(std ::pair<char , int >('z' , 500 )); if (ret.second == false ) { std ::cout << "element 'z' already existed" ; std ::cout << " with a value of " << ret.first->second << '\n' ; } std ::map <char , int >::iterator it = mymap.begin(); mymap.insert(it, std ::pair<char , int >('b' , 300 )); mymap.insert(it, std ::pair<char , int >('c' , 400 )); std ::map <char , int > anothermap; anothermap.insert(mymap.begin(), mymap.find('c' )); anothermap.insert({ { 'd' , 100 }, {'e' , 200 } }); return 0 ; }
4.3. 取值 1 2 3 4 5 6 7 8 map <int , string > ID_Name;cout <<ID_Name[2016 ].c_str()<<endl ;ID_Name.at(2016 ) = "Bob" ;
4.4. 容量查询 1 2 3 4 5 6 7 8 9 10 11 12 bool empty () size_t size();size_t max_size();size_t count( const Key& key ) const ;
4.5. 迭代器 8个获取迭代器的函数 begin(), end(), rbegin(),rend() 以及对应的 cbegin(), cend(), crbegin(),crend() 。二者的区别在于，后者返回 const_iterator，而前者则根据map的类型返回iterator 或者 const_iterator。const情况下，不允许对值进行修改。如下面代码所示：
1 2 3 4 5 6 7 8 9 map <int ,int >::iterator it;map <int ,int > mmap;const map <int ,int > const_mmap;it = mmap.begin(); mmap.cbegin(); const_mmap.begin(); const_mmap.cbegin();
返回的迭代器可以进行加减操作，此外，如果map为空，则 begin = end。
4.6. 查找 1 2 3 4 iterator find (const key_type& k) ;const_iterator find (const key_type& k) const ;
实例:
1 2 3 4 5 6 7 8 9 std ::map <char ,int > mymap;std ::map <char ,int >::iterator it;mymap['a' ]=50 ; mymap['b' ]=100 ; mymap['c' ]=150 ; mymap['d' ]=200 ; it = mymap.find('b' ); if (it != mymap.end()) mymap.erase (it);
4.7. 删除 1 2 3 4 5 6 7 8 iterator erase ( iterator pos ) iterator erase ( const_iterator first, const_iterator last ) ;size_t erase( const key_type& key );void clear ()
4.8. 交换 1 2 void swap ( map & other )
