本文已收录于专栏
🌲《百日算法竞赛》🌲
目录
创新互联IDC提供业务:
绵阳服务器托管,成都服务器租用,
绵阳服务器托管,重庆服务器租用等四川省内主机托管与主机租用业务;数据中心含:双线机房,BGP机房,电信机房,移动机房,联通机房。
前言：
序列容器
序列的要求：
1.vector
vector常用方法
vector遍历
2、deque
头文件
方法
3、list
头文件
方法
4、queue
方法：
关联容器
1、map
2、set
添加
获取
总结
使用
不断补充……
vector
pair
string
queue
priority_queue 优先队列（堆），默认是大根堆
stack
deque 双向队列
set , map , multiset , multimap 基于平衡二叉树（红黑树），动态维护有序序列
unordered_set , unordered_map ,
unordered_multiset , unorder_multimap 哈希表
bitset 压位
前言：
我们在打比赛的时候为了方便通常会使用模板库，C++有STL标准模板库，Java对应的则是集合框架，C++比赛经常用容器，那么什么是容器呢？
容器是储存其他对象的对象。被储存的对象必须是同一类型。
只要是学过编程的兄弟都知道，这个定义后半句好像数组，确实，但是不尽相同。
分类：
容器分为两个部分，一是序列容器（是一种各元素之间有顺序关系的线性表，是一种线性结构的可序群集。顺序性容器中的每个元素均有固定的位置，除非用删除或插入的操作改变这个位置。顺序容器的元素排列次序与元素值无关，而是由元素添加到容器里的次序决定）（forword_list,list,queue,priority_queue,stack,deque,vector,array）。
另一个是关联容器（关联式容器是非线性的树结构，更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系，也就是说元素在容器中并没有保存元素置入容器时的逻辑顺序。但是关联式容器提供了另一种根据元素特点排序的功能，这样迭代器就能根据元素的特点“顺序地”获取元素。元素是有序的集合，默认在插入的时候按升序排列（set,multiset,map,multimap）
序列容器
序列的要求：
X a(n,t) //声明一个名为a的有n个t组成的序列
X(n,t) //匿名序列（这里我们不做过多的解释）
X a(i,j) //声明一个名为a的序列，并且初始化(i,j)
的内容
X(i,j) //匿名序列
v.insert() //由于insert重载方法比较多
1.v.insert(p,t)//将t插到p的前面
2.v.insert(p,n,t)//将n个t插入p之前
3.v.insert(p,i.j)//将区间[i,j)的元素插入到p之前
v.erase(t,k)
1.v.erase(t,k)//删除他们之间的元素
2.v.erase(p)//删除p指向的元素
v.chear===v.erase(begin(),end());
1.vector
vector表示一段连续的内存，基于数组实现，他有自动的内存管理功能!
可以动态的改变vector的长度，并随着元素的增加与减小来自动改变数组大小，它提供了直接添加尾部元素或者删除元素的方法！
特点：
他可以反转序列，所以它可以反向遍历可反转序列！（基于他的rbegin,rend）
使用前要调用头文件
#include
vectorv;//默认初始化
vectorv(v1);//用v1初始化v
vectorv(v1.begin(),v1.end());//用v1初始化v
vectorv(100);//定义一个大小为100的数组！
vectorv(100,1)//定义个全为1而且长度为190的数组
vector常用方法
a.front(),a.rbegin() //首元素
a.back(),a.rend() //末尾元素
v.push_back() //增加元素
v.insert()
1.v.insert(p,t) //将t插到p的前面
2.v.insert(p,n,t) //将n个t插入p之前
3.v.insert(p,i.j) //将区间[i,j)的元素插入到p之前
v.pop_back() //删除
v.erase(t,k)
1.v.erase(t,k) //删除他们之间的元素
2.v.erase(p) //删除p指向的元素
v.clear===v.erase(begin(),end());//清空vector
vector遍历
//下标
int length = v.size();
for(int i=0;i::const_iterator iterator = v.begin();
for(;iterator != v.end();iterator++)
{
cout<<*iterator;
}
2、deque
双端队列，他的实现与vector类似，支持随机访问，但是它访问首元素的插入（push_front()）与删除（pop_front()）的时间是固定的！而且他的执行速度要比vector快很多！所以题目中有大量的操作发生在序列的起始位置与结尾处，我们就要考虑用deque!
头文件
#include
方法
只是比vector多了两个处理头的方法
d.push_front(1)；
d.pop_front(1);
3、list
双向链表，list在链表中的任意一个位置插入与删除一个元素时间是固定的！但是他不能随机访问，优点是元素的快速插入与删除！从容器中插入与删除元素之后i，迭代器指向元素将不变，不会移动已有元素，只是修改链表信息。
头文件
#include
方法
void sort() //使用<运算符对链表进行快速排序，时间复杂度O（NlogN）
void merge(list&x)
//将x与调用链表合并，要求：两个链表必须要已经排好序！
//元素将保存在调用链表中，x为空，这个时间复杂度为线性！
void remove(const T &val) //删除val的所有实例
void splice(iterator pos,listx)
//将链表x的内容加到pos的前面
void unique（） //去重(对list里面所有重复元素进行去重，然后再排序)
forward_list 容器以单链表的形式存储元素。
forward_list 的模板定义在头文件 forward_list 中。
fdrward_list 和 list 最主要的区别是:它不能反向遍历元素；只能从头到尾遍历。
想要深入了解forward_list的看这里C++ forward_list用法详解 (biancheng.net)
4、queue
这是一个配适器类，ostream_iterator就是一个配适器，让输出流能够使用迭代器接口，同样它实现了队列接口！它不仅不允许随机访问元素，而且还不能遍历队列！元素只能先进先出（FIFO）.
方法：
bool empty()//判断是否为空
front()//队首元素的访问
back()//队尾元素的访问
push(x)//队尾插入x
pop()//删除队首元素
关联容器
它运用了键值对（value-key），与java类似的map,例如hashmap，有点在于他提供了利用key快速访问功能，它的底层结构应该是一种树来实现的，所以他才有如此快的查找速度，最简单的set，他的键值对类型是一致的，而且唯一，元素默认按升序排列。map他的键值对类型不同，键是唯一的,元素默认按键的升序排列。
m.lower_bound(k)//返回一个迭代器，指向键不小于 k 的第一个元素
m.upper_bound(k)//返回一个迭代器，指向键大于 k 的第一个元素
m.equal_range(k)//返回一个迭代器的 pair 对象。它的 first 成员等价于 m.lower_bound(k)。而 second 成员则等价于 m.upper_bound(k)
1、map
map 是键－值对的集合。map 类型通常可理解为关联数组：可使用键作为下标来获取一个值，正如内置数组类型一样。而关联的本质在于元素的值与某个特定的键相关联，而并非通过元素在数组中的位置来获取。
mapmap1; //默认为空
m.insert()
1.m.insert(e)//e是一个用在m上的value_kry 类型的值。如果键（e.first不在m中，则插入一个值为e.second 的新元素；如果该键在m中已存在，则保持m不变。该函数返回一个pair类型对象，包含指向键为e.first的元素的map迭代器，以及一个 bool 类型的对象，表示是否插入了该元素
2.m.insert(begin,end)//begin和end是标记元素范围的迭代器，其中的元素必须为m.value_key 类型的键－值对。对于该范围内的所有元素，如果它的键在 m 中不存在，则将该键及其关联的值插入到 m。返回 void 类型
3.m.insert(iter,e)//e是一个用在m上的 value_key 类型的值。如果键（e.first）不在m中，则创建新元素，并以迭代器iter为起点搜索新元素存储的位置。返回一个迭代器，指向m中具有给定键的元素
m.count(k) //返回m中k的出现次数
m.find() //如果m容器中存在按k索引的元素，则返回指向该元素的迭代器。如果不存在，则返回超出末端迭代器.
m.erase() //具体与序列该方法一致！
2、set
支持插入，删除，查找等操作，就像一个集合一样。所有的操作的都是严格在logn时间之内完成，效率非常高。set和multiset的区别是：set插入的元素不能相同，但是multiset可以相同。Set默认自动排序。使用方法类似list。
set容器的定义和使用
set 容器的每个键都只能对应一个元素。以一段范围的元素初始化set对象，或在set对象中插入一组元素时，对于每个键，事实上都只添加了一个元素。
vectorivec;
for(vector::size_type i = 0; i != 10; ++i) {
ivec.push_back(i);
ivec.push_back(i);
}
setiset(ivec.begin(), ivec.end());
cout<< ivec.size()<< endl;//20个
cout<< iset.size()<< endl;// 10个
添加
setset1;
set1.insert("the"); //第一种方法：直接添加
setiset2;
iset2.insert(ivec.begin(), ivec.end());//第二中方法：通过指针迭代器
获取
setiset;
for(int i = 0; i<10; i++)
iset.insert(i);
iset.find(1)// 返回指向元素内容为1的指针
iset.find(11)// 返回指针iset.end()
iset.count(1)// 存在，返回1
iset.count(11)// 不存在，返回0
总结
- 有序容器（除了list）：存储底层vector,只是添加了不同的接口！
- deque（队列）：它不像vector 把所有的对象保存在一块连续的内存块，而是采用多个连续的存储块，并且在一个映射结构中保存对这些块及其顺序的跟踪。向deque 两端添加或删除元素的开销很小，它不需要重新分配空间。
- list（列表）：是一个线性链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。
- 后面的关联与无序关联都是用的一种树状结构！
使用
- 当数组大小未知时，和需要高效的查询功能，用vector!高效地随机存储。
- 不使用连续的内存空间,而且可以随意地进行动态操作，有大量的插入、删除操作，用list！
- 需要在两端进行push 、pop用daque！它兼顾了数组和链表的优点，它是分块的链表和多个数组的联合。所以它有被list 好的查询性能，有被vector 好的插入、删除性能。 如果你需要随即存取又关心两端数据的插入和删除，那么deque 是最佳之选。
- 需要查找或者打表可以选择map与set,当然一定条件下我们可以优秀考虑用无序关联容器！
不断补充……
vector
size()
empty()
clear()
front()/back()
push_back()/pop_back()
begin()/end()
支持比较运算符，按字典序 例:vectora(3,4);vectorb(4,3); 444>3333 a>b
nth_element(a,a+x,a+n)数组a的总长度为n，函数执行完后前x个数都比x+1位置上的小，后面所有数都比x+1位置上的数大，但不要求有序
pair
pair first 第一个元素
second 第二个元素
支持比较运算符，以first为第一关键字，以second为第二关键字（字典序）
string
substr()第一个参数开始位置，第二个参数截取的长度
c_str() 返回字符串首地址
size()/length() 返回字符串长度
empty()
clear()
push_back('c') string拼接char型
queue
size()
empty()
push()
pop()
front()
back()
priority_queue 优先队列（堆），默认是大根堆
push()
top()
pop()
定义成小根堆的方式：（1）存入其相反数-x （2）priority_queue,greater>q;
stack
size()
empty()
push()
pop()
top()
deque 双向队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
set , map , multiset , multimap 基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin()/end() ++,-- 返回前驱和后继
set/multiset set里元素维一，multiset里可以有多个相同的元素
insert() 插入一个数
find() 如果不存在返回end()
count() 返回某一个数的个数
erase()
(1)输入的是一个数x，删除所有x o(k+logn)
(2)输入的是一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bount(x) 返回大于等于x的最小的数
upper_bount(x) 返回大于x的最小的数
map/multimap
insert() 插入一个pair
erase() 输入的参数是pair或者迭代器
[ ] 时间复杂度o(logn)
unordered_set , unordered_map ,
unordered_multiset , unorder_multimap 哈希表
和上面类似，增删改更快o(1)
但不支持 lower_bound()/upper_bound()/迭代器++，--
bitset 压位
bitset<10000>s;
~ & | ^
>>,<<,==,!=,[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置置成1
set(k,v) 把第k位变成1
reset()把所有位变成0
flip() 等价于~
flip(k) 把第k位取反
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
网站栏目：算法竞赛100天第2天——STLINC++（算法竞赛必备知识总结汇总）-创新互联
文章来源：
http://cdkjz.cn/article/dpidso.html
