--- title: "C++常用容器" author: "Perrin Yong" author_profile: https://www.pystone.net/profile/ published_by: "Perrin Yong" canonical: https://www.pystone.net/notes/cpp-common-containers/ type: note content_role: unspecified visibility: public id_stability: rename-stable source_path: "10-计算机、信息技术与工程/02-编程语言与运行时/C++/C++常用容器.md" content_hash: 8d9721a4b9e8eeb386b6d8f0fa5eeb9b89ffd26b633c0d769ea9e61b4f4eb461 knowledge_version: 224c990773de.5fa8af6e39fa site_commit: 224c990773de166d23a886306577dd90379529ce notes_commit: 5fa8af6e39fa3891d1b9b4832bfa6c4e0ecaaf0a --- # C++常用容器 > 创建时间：2020/1/16 22:12 * stack * Set * 关联容器与顺序容器 * set分类 * 特点 * 用法 * map * pair * map * 插入方法： * 查找和读取 * 删除 * 基本操作函数总结 template > class stack; 第一个是T，表示栈中存放的数据的类型，比如int，double，或者结构体之类。 第二个参数指明底层实现的容器类型，也就是指明这个栈的内部实现方式，比如vector，deque，list。如果不指明它，默认使用deque(双端队列)。一般情况下不需要指定这一项参数。 ```cpp string str1 = "test"; string str2 = "test"; ``` ```cpp string str1 = "test"; string str2 = "test"; ``` ```cpp string str1 = "test"; string str2 = "test"; ``` ## Set ### 关联容器与顺序容器 * 顺序容器（sequence container）包括vector、deque、list、forward_list、array、string，所有顺序容器都提供了快速顺序访问元素的能力。 * 顺序容器中的元素是按它们在容器中的位置来顺序保存和访问的 * 关联容器（associative container）包括set、map * 关联容器中的元素是按关键字来保存和访问的 关联容器 **不支持** 顺序容器的 **位置相关的操作** 。原因是关联容器中元素是根据关键字存储的，这些操作对关联容器没有意义。 ### set分类 1. 按关键字有序保存元素：set；multiset(关键字可重复出现t)； 2. 无序集合：unordered_set(用哈希函数组织的set)；unordered_multiset(哈希组织的set，关键字可以重复出现)。 ### 特点 * set中元素 **值唯一，自动排序** ，元素的值不能直接被改变。 * set内部采用 **红黑树** （RB树）(Red-Black Tree)，一种非常高效的平衡检索二叉树，插入和删除操作效率较高。 **O(log n)** ### 用法 ```cpp string str1 = "test"; string str2 = "test"; ``` ## map ### pair #include * pair p; * pair p1(0, "Hello"); * pair p2 = make_pair(1, "World"); * p.first * p.second ### map > map內部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能 * map m; * map m(m2); * map m(b, e); //两个迭代器 map的value_type是存储元素的键以及值的pair类型，键为const。 #### 插入方法： 1. 使用下标 在map中使用下标访问不存在的元素将导致在map容器中添加一个新的元素。 如果已经有该key，会覆盖以前该关键字对应的值 ```cpp string str1 = "test"; string str2 = "test"; ``` 2. 使用insert函数 * m.insert(e) * m.insert(beg, end) * m.insert(iter, e) 当map中有这个关键字时，insert操作是不能在插入数据的 ```cpp string str1 = "test"; string str2 = "test"; ``` #### 查找和读取 1. 用下标的方法读取map中元素时，若map中不存在该元素，则会在map中插入。 2. count(k) ： 只是查找该元素是否存在 3. find(k) ： 想取得key对应的值 ```cpp string str1 = "test"; string str2 = "test"; ``` #### 删除 * m.erase(k); //key * m.erase(p); //迭代器p * m.erase(b, e); //迭代器b、e #### 基本操作函数总结 C++ maps是一种关联式容器，包含“关键字/值”对 begin() 返回指向map头部的迭代器 clear(） 删除所有元素 count() 返回指定元素出现的次数 empty() 如果map为空则返回true end() 返回指向map末尾的迭代器 equal_range() 返回特殊条目的迭代器对 erase() 删除一个元素 find() 查找一个元素 get_allocator() 返回map的配置器 insert() 插入元素 key_comp() 返回比较元素key的函数 lower_bound() 返回键值>=给定元素的第一个位置 max_size() 返回可以容纳的最大元素个数 rbegin() 返回一个指向map尾部的逆向迭代器 rend() 返回一个指向map头部的逆向迭代器 size() 返回map中元素的个数 swap() 交换两个map upper_bound() 返回键值>给定元素的第一个位置 value_comp() 返回比较元素value的函数