C++常用容器

创建时间：2020/1/16 22:12

• stack
  • Set
    • 关联容器与顺序容器
    • set分类
    • 特点
    • 用法
  • map
    • pair
    • map
      • 插入方法：
      • 查找和读取
      • 删除
      • 基本操作函数总结

template <class T, class Container = deque > class stack; 第一个是T，表示栈中存放的数据的类型，比如int，double，或者结构体之类。 第二个参数指明底层实现的容器类型，也就是指明这个栈的内部实现方式，比如vector，deque，list。如果不指明它，默认使用deque(双端队列)。一般情况下不需要指定这一项参数。

string str1 = "test";
string str2 = "test";

string str1 = "test";
string str2 = "test";

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)

用法

string str1 = "test";
string str2 = "test";

map

pair

#include

• pair<T1, T2> p;
• pair<int, string> p1(0, "Hello");
• pair<int, string> p2 = make_pair(1, "World");
• p.first
• p.second

map

map內部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能

• map<k, v> m;
• map<k, v> m(m2);
• map<k, v> m(b, e); //两个迭代器

map的value_type是存储元素的键以及值的pair类型，键为const。

插入方法：

1. 使用下标 在map中使用下标访问不存在的元素将导致在map容器中添加一个新的元素。 如果已经有该key，会覆盖以前该关键字对应的值

string str1 = "test";
string str2 = "test";

1. 使用insert函数

• m.insert(e)
• m.insert(beg, end)
• m.insert(iter, e) 当map中有这个关键字时，insert操作是不能在插入数据的

string str1 = "test";
string str2 = "test";

查找和读取

1. 用下标的方法读取map中元素时，若map中不存在该元素，则会在map中插入。
2. count(k) ： 只是查找该元素是否存在
3. find(k) ： 想取得key对应的值

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的函数