一、vector 向量容器
头文件：#include < vector >
-
采用顺序结构存储数据，可以使用下标进行随机访问，有时候也叫数组容器（C++11中增加了array容器，定长数组容器,相比普通数组它是类类型，增加成员函数，提高安全性）
-
vector是可变长的顺序表结构，可以自动扩容，容器中的元素存储在连续内存，支持随机访问，尾插入效率O(1)，但是在指定位置进行插入和删除效率O(n),因为要保证数据的连续性
1.构造函数：
vector( size_type num, const TYPE& val = TYPE() );
num
vector( input_iterator start, input_iterator end );
功能：
2.支持的运算符
==，!=,<=,>=,<,>,对容器整体比较，会对两个容器中的元素按顺序一次比较，一旦某个元素比较出结果就立即返回
元素需要支持 < 运算符才能比较
[] 跟普通数组一样不会检查下标是否合法，如果访问的下标>=size()的个数，可能段错误
3.成员函数：
void assign( size_type num, const TYPE& val );
功能：给向量个前num个元素赋值为val
void assign( input_iterator start, input_iterator end );
功能：使用一组范围[start,end)的数据给向量赋值
TYPE& at( size_type loc );
const TYPE& at( size_type loc ) const;
功能：访问向量loc下标的元素，功能相当于[],当loc越界时at函数会抛出异常，相比[]会更加安全
TYPE& back();
const TYPE& back() const;
功能：访问向量中的最后一个元素，访问向量中的第一个元素
TYPE& front();
const TYPE& front() const;
功能：访问向量中的第一个元素
iterator begin();
功能：返回指向第一个元素的正向迭代器
const_iterator begin() const;
功能：返回指向第一个元素的正向常迭代器
iterator end();
功能：返回指向最后一个元素的下一个位置的正向迭代器
const_iterator end() const;
功能：返回指向最后一个元素的下一个位置的正向常迭代器
注意：需要通过容器中的迭代器来操作容器的数据和内存
vector<类型> v;
vector<类型>::iterator it = v.begin( );
在C++11中auto可以用于自动识别数据类型，并定义该类型的变量，可以很方便地定义迭代器类型
auto num = 10; // num int
auto it = v.begin(); //it vector<类型>::iterator
注意：虽然迭代器在vector用处不大，但是对于其它容器，迭代器是唯一一种遍历的方式
reverse_iterator rbegin();
功能：返回一个逆向迭代器，它指向最后一个元素
const_reverse_iterator rbegin() const;
功能：返回一个逆向常迭代器，它指向最后一个元素
reverse_iterator rend();
功能：返回一个逆向迭代器，它指向第一个元素的前一个位置
const_reverse_iterator rend() const;
功能：返回一个逆向常迭代器，它指向第一个元素的前一个位置
注意：逆向迭代器也是指向一个位置，与正向迭代器的区别是，执行++操作时是往前一个元素逆向移动
size_type capacity() const;
功能：获取向量的容量
void clear();
功能：清空向量中的所有元素
容量不，删除释放所有元素，如果元素是类类型，会执行析构函数，元素数量变0
bool empty() const;
功能：当向量为空返回真
iterator erase( iterator loc );
功能：删除loc位置的元素
返回值：返回删除后loc位置的迭代器
iterator erase( iterator start, iterator end );
功能：删除 [start,end) 范围的元素
返回值：返回删除后start位置的迭代器
注意：只能提供迭代器进行删除，数量-1，容量不变
iterator insert( iterator loc, const TYPE& val );
功能：在loc位置插入值为val的元素
返回值：获取到 loc的迭代器，loc会随着函数结束有可能发生变化，如果想要连续往同一个loc位置插入，需要重新接收
void insert( iterator loc, size_type num, const TYPE& val );
功能：在loc位置插入num个值为val的元素
void insert( iterator loc, input_iterator start, input_iterator end );
功能：在loc位置插入一组[start,end)元素
注意：如果插入、添加数据时向量刚好没有空余位置时，向量会自动扩容，一般是在原容量基础上翻倍
size_type max_size() const;
功能：用于计算理论上向量能存储的最大元素数量，受元素的类型影响
void pop_back();
功能：在末尾位置删除元素
void push_back( const TYPE& val );
功能：在末尾添加一个值val的元素
效率：O(1)
void reserve( size_type size );
功能：修改向量的容量，只能比原来的容量大才能修改，
可以进行预分配，提高效率，减少扩容的次数（耗时），但是也意味着内存可能会闲置
每次扩容可能会拷贝原向量中的所有对象进行拷贝构造，还要把原向量中的对象进行析构，如果频繁的扩容会严重影响vector性能，因此需要在合适的时候进行reserve
shrink_to_fit() 取消闲置的内存
void resize( size_type num, const TYPE& val = TYPE() );
功能：修改向量的元素数量
如果num>size() 在末尾增加值为val的元素
如果num<size() 相当于在末尾删除到num个元素
size_type size() const
功能：获取向量的元素数量
void swap( container& from );
功能：交换两个向量的元素
二、list链表容器
头文件：#include < list >
是一个功能齐全的双向链表
支持的运算符：
-
==, !=, <=, >=, <, >, =
-
也是链表与链表之间的比较和赋值
-
注意：链表中元素必须支持 < 运算符才能使用
成员函数：
void assign( size_type num, const TYPE& val );
功能：向链表中赋值num个值为val的元素
void assign( input_iterator start, input_iterator end );
功能：向链表中赋值[start,end) 范围的元素
对整个链表进行赋值
| 函数名 | 功能 |
|---|---|
| back | 访问最后一个元素 |
| front | 访问第一个元素 |
| begin | 返回第一个位置正向迭代器 |
| end | 返回最后一个位置下一个位置的正向迭代器 |
| rbegin | 返回最后一个位置的逆向迭代器 |
| rend | 返回第一个位置的前一个位置的逆向迭代器 |
| clear | 清空链表中的元素 |
| empty | 判断是否为空链表 |
| max_size | 理论上最多能存储的元素个数 |
iterator erase( iterator loc );
删除loc位置的元素，只能提供迭代器，不能直接提供地址
iterator erase( iterator start, iterator end );
注意：list的迭代器不允许 it+n it+=n it-n it-=n 语法，因为list是链式结构，不支持随机访问
但是 it++ ++it 是通过节点的next找下一个节点 是允许的
iterator insert( iterator loc, const TYPE& val );
功能：在loc位置插入值val
void insert( iterator loc, size_type num, const TYPE& val );
功能：在loc位置插入num个val
template<TYPE> void insert( iterator loc, input_iterator start, input_iterator end );
功能：在loc位置插入[start,end)范围的元素
void merge( list &lst );
功能：按照顺序合并两个链表
合并后是否有序，取决于合并前是否有序（默认只对升序合并后有序）
void merge( list &lst, BinPred compfunction );
如果想要进行降序排序，需要以回调形式提供compfunction比较方式
想要有序合并，链表元素必须支持 < 运算符，否则也需要提供比较方法才能合并
合并结束后 lst的元素数量为0
pop_front 头删除
push_front 头添加
void remove( const TYPE &val );
功能：删除链表中值为val的所有元素
void remove_if( UnPred pr );
功能：删除符合条件pr的所有元素
pr
bool cmp(const TYPE& val)
{
return val >= left && val <= right;
// 符合[left,right]范围的数据删除
}
void resize( size_type num, const TYPE& val = TYPE() );
功能：修改list的元素数量
如果num>size() 在末尾增加到num个值为val元素
如果num<size() 相当于在末尾删除到num个元素
void sort();
功能：对list进行升序排序，要求元素支持< 运算符
void sort( BinPred p );
功能：对list进行排序，可通过提供二元谓词 > 运算符比较进行降序排序，如果元素不支持 < 运算符，也需要提供比较回调函数
p:
bool cmp(TYPE& a,TYPE& b)
{
return a > b; //降序
}
void splice( iterator pos, list& lst );
功能：把链表lst合并到当前链表的pos指定位置，结束后lst数量为0
void splice( iterator pos, list& lst, iterator del );
功能：把lst的del位置合并到当前链表的pos位置，并且lst中del位置会删除
void splice( iterator pos, list& lst, iterator start, iterator end );
功能：把lst的[start,end)位置合并到当前链表的pos位置，并且lst中[start,end)位置会删除
void swap( container& from );
功能：交换两个链表
void unique();
功能：删除链表中的重复元素
void unique( BinPred pr );
功能：删除链表中满足条件pr的重复元素
作业：使用list实现C++通讯录 增删改查
三、deque 双端队列容器
include < deque>
-
是下标顺序容器，它允许在首位两端快速的插入、删除数据
-
deque的元素不是全部相邻存储的：采用单独分配的固定大小数组的序列存储数据，以及额外的登记表(中控数组)，该表中记录了所有序列的地址，这表示通过下标访问元素时必须经过两次指针解引用，vector只需要一次
-
deque支持随机访问，效率依然是O(1)
-
deque的存储也可以按需自动扩展、收缩，并且deque的扩展比vector更优，因为不涉及到原内存复制、销毁环节
-
vector扩容，先申请一块更大的内存，把原内存数据拷贝，释放原内存
-
deque扩容，只需要申请一块新的固定大小序列，记录到中控数组中即可
-
-
deque比vector多push_front\pop_front操作，并且效率也能O(1)
-
vector比deque多个reserve预分配内存，因为deque不需要预分配内存来节约时间
deque的优缺点：（常考）
优点：
-
与vector相比，头部插入、删除时，不需要搬运后续元素，效率特别高（O(1)）；再扩容时，也不需要移动、释放原内存，只需要操作中控数组即可
-
与list相比，底层依然是连续空间，空间利用率更高，支持随机访问O(1)
缺点：
-
没有vector和list那么极致，随机访问的速度比vector慢（vector是真正的连续空间）；中间位置的插入、删除没有list快，list根本不需要扩容
-
不适合遍历，因为在遍历时deque的迭代器需要频繁的检查是否移动到了某个序列的末尾，并且需要解两次引用，效率低
-
因此当需要线性容器时，大多数情况下优先考虑vector、list，deque的应用不多（stack\queue）
四、stack栈容器（适配器）
头文件< stack >
-
底层由deque实现
-
不支持运算符，没有迭代器，只有无参构造和拷贝构造
empty、push、pop、top、size
五、queue队列容器（适配器）
头文件< queue >
-
底层由deque实现
-
不支持运算符，没有迭代器，只有无参构造和拷贝构造
empty\push\pop\front\back\size
六、priority_queue优先队列容器（适配器）
头文件< queue >
-
底层采用vector实现，当数据入队时，会对数据进行调整成堆结构，默认是大顶堆，元素越大，优先级越高，越先出队
-
注意：存储的元素必须支持 < 运算符，如果是类类型数据必须重载<运算符
如何调整优先队列的优先级：（小顶堆）
-
元素取反存入、取出取反
-
类型数据重载 < 运算符，调整<运算符的比较过程类
-
固定语法
priority_queue<类型,vector<类型>,greater<类型> > 队列名; // 升序 priority_queue<类型,vector<类型>,less<类型> > 队列名; // 降序
七、关联性容器（有序）
-
关联性容器可以实现快速查找（O(logn)）的容器
-
线性容器中array,vector,list,deque都可以使用全局find进行顺序查找（O(n)），必须支持运算符operator==比较
-
底层实现 红黑树（常问）
八、set集合容器
incude < set >
-
集合容器，底层采用红黑树实现，特点：元素不能重复，会自动对数据进行排序，它存储的元素必须支持<运算符，只能使用迭代器遍历
-
默认下是按照 operater< 运算符进行比较
为什么不是使用operator==来比较？
-
二叉排序树的规则：左小于根、根小于右，如果相等插入失败，==无法判断大小
-
a == b 可以使用 !(a<b || b<a)替代
构造函数：
无参、拷贝
支持的运算符：
与list一致，不支持随机访问
成员函数
iterator insert( iterator i, const TYPE& val );
功能：向set中添加val，i位置意义不大
void insert( input_iterator start, input_iterator end );
功能：向set添加一组[start,end)数据
pair<iterator,bool> insert( const TYPE& val );
功能：向set中添加val
返回值：返回键值对pair<添加的位置,是否添加成功>
size_type count( const key_type& key );
功能：查看key在set中有几个，要么0要么1
iterator find( const key_type& key );
功能：查找set中key的元素的位置，并返回该位置的迭代器
如果找不到key，返回end()位置的迭代器
pair<iterator, iterator> equal_range(const key_type& key );
功能：查看key在set中的范围，并返回该范围组成的键值对，在set中意义不大
void erase( iterator pos );
void erase( iterator start, iterator end );
size_type erase( const key_type& key );
功能：删除值为key的元素，成功返回1，失败返回0
key_compare key_comp() const;
功能：返回一个用于比较set中元素的函数对象，该对象属于set
set<int>::key_compare cmp = s.key_comp();
cmp(int,int) 第一个"小"，则为真
value_compare value_comp() const;
在set中等同于 key_comp
iterator lower_bound( const key_type& key );
功能：返回一个大于等于key的最小的元素的迭代器
iterator upper_bound( const key_type& key );
功能：返回一个大于key的最小的元素的迭代器
九、multiset多重集合容器
include < set >
- 元素可以重复，也会对元素进行排序，元素必须支持<运算符，只能用迭代器遍历
size_type count( const key_type& key );
功能：计算有几个key
pair<iterator, iterator> equal_range( const key_type& key );
功能：返回值为key的元素的范围
十、map映射容器
include < map>
-
有序键值对容器，是由key和value组成的元素（键值对、字典）pair，要求key不能重复，一个key只能对应一个值，会根据key进行排序，因此key必须支持<运算符
-
一般map中存储一些经常需要查找的数据，因为map的查找速度极快，set速度也不慢，但是map比set多一个value来进行描述，redis内存数据库中使用键值对存储数据
-
key和value一一对应，可以根据key来访问value，底层采用红黑树根据key来进行组织、管理，查找效率很高
构造函数
map( iterator start, iterator end );
功能：使用一组数据（pair类型）构造
map( iterator start, iterator end, const key_compare& cmp );
功能：使用一组数据（pair类型）构造，并提供key的比较函数
map( const key_compare& cmp );
功能：提供key的比较函数构造
支持的运算符：
-
[ ]支持通过key作为下标访问元素的value
-
既可以用于访问，当key不存在时，也可以用于插入数据< key,value >，如果key存在，则修改value
m[key] = value; // 添加、修改 m[key]; // key不存在，添加key-value value使用无参构造或者默认值0 m[key]; // key存在，访问对应的value -
成员函数at (key）也可以用于访问、修改key的value,但是当key不存在时会排除异常out_of_range
常用成员函数
iterator insert( iterator i, const TYPE& pair );
void insert( input_iterator start, input_iterator end );
pair<iterator,bool> insert( const TYPE& pair );
十一、multimup多重映射容器
include < map >
-
使用方法与map几乎类似
-
不同的是它的key可以对应多个不同的value，因此不能支持[]运算符
-
一些成员函数：count、equal_range 就变得有意义
通过迭代器删除元素需要注意的问题：
-
对于关联性容器
(set\multiset\map\multimap)，删除当前iterator会仅仅使得当前iterator失效，其余位置没有变化，因此在erase时只需要递增iterator即可依次删除，因为底层是红黑树，某个节点删除不会影响其它节点的位置map.erase(it++); -
对于线性容器
(vector\deque\stack\queue\priority_queue)，删除当前iterator后，后序所有的iterator失去原来意义，因为使用的是连续内存，删除一个，后面所有元素都重新移动，iterator不能递增删除，只能通过重新接收erase的返回值，获取新的当前iterator继续删除
it = vector.erase(it); -
list两种方式都可以
十二、bitset位集合容器
include < bitset >
-
是一种封装了各种位操作的类类型数据结构
-
!=, ==, &=, |=, ~, <<=, >>=, [ ]
成员函数
| 函数名 | 功能 |
|---|---|
| any | 有任意一位是1，返回真 |
| count | 统计二进制位是1的位数有几位 |
| filp | 所有二进制位取反\指定的二进制位取反 |
| none | 全部位没有一个是1，返回真 |
| reset | 全部二进制位置0\指定二进制位置0 |
| set | 全部二进制位置1\指定二进制位置val=1 |
| size | 获取位数 |
| test | 访问指定的二进制位的值 |
| to_string | 把所有二进制位转stirng类型 |
| to_ulong | 把所有二进制位转unsigned long类型 |
C++不常用，但是对于嵌入式软件编程会比较方便去设置二进制位
标签：容器,功能,const,iterator,STL,void,元素,key,模板 From： https://www.cnblogs.com/wangqiuji/p/17677939.html