deque 双端队列容器
与vector一样，采用线性表顺序存储结构。唯一不同是 deque 采用分块的线性存储结构来存储数据。deque 块在头部和尾部都可插入和删除元素,而不需移动其他元素(使用 push_back()方法在尾部插入元素会扩张队列；而使用 push_front()方法在首部插入元素和使用 insert()方法在中间插入元素只是将原位置上的元素值覆盖,不会增加新元素)。考虑到容器元素的内存分配策略和操作的性能时 deque 相对于 vector更有优势。
deque函数
创建 deque 对象，三种方法
创建没有任何元素的 deque 对象, 如:
deque<int> d;创建具有 n 个元素的 deque 对象,如:
deque<int> d(10); //创建具有 10 个整型元素的 deque 对象 d创建具有 n 个元素的 deque 对象,并赋初值,如:
deque<int> d(10,8.5); //创建具有 10 个整型元素的 deque 对象 d,每个元素值为 8.5
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int main()
{
deque<int> d;
//使用 push_back()方法从尾部插入元素,会不断扩张队列。
d.push_back(1);
d.push_back(2);
d.push_back(3);
//以数组方式输出元素
cout<<d[0]<<" "<<d[1]<<" "<<d[2]<<endl;
//前向遍历
for(int i=0;i < d.size(); i++)
cout<<d[i]<<" ";
cout<<endl;
//以前向迭代器的方式遍历
deque<int>::iterator it;
for(it=d.begin();it!=d.end();it++)
cout<<*it<<" ";
cout<<endl;
//反向遍历
deque<int>::reverse_iterator rit;
for(rit=d.rbegin();rit!=d.rend();rit++)
cout<<*rit<<" ";
cout<<endl;
//从头部插入元素,不会增加新元素,只将原有的元素覆盖。
d.push_front(10);
d.push_front(20);
//以数组方式输出元素
cout<<d[0]<<" "<<d[1]<<" "<<d[2]<<endl;
//从中间插入元素,不会增加新元素,只将原有的元素覆盖。
d.insert(d.begin() + 1, 88);
cout<<d[0]<<" "<<d[1]<<" "<<d[2]<<endl;
return 0;
}
删除元素，可以从双端队列容器的首部、尾部、中部删除元素，并可以清空双端队列容器。
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int main()
{
deque<int> d;
//使用 push_back()方法从尾部插入元素,会不断扩张队列。
d.push_back(1);
d.push_back(2);
d.push_back(3);
d.push_back(4);
d.push_back(5);
//采用 pop_front()方法从头部删除元素
d.pop_front();
d.pop_front();
//以前向迭代器的方式遍历
deque<int>::iterator it;
for(it = d.begin(); it != d.end(); it++)
cout<<*it<<" ";
cout<<endl;
d.push_front(2);
d.push_front(1);
//采用 pop_back()方法从尾部删除元素
d.pop_back();
for(it = d.begin(); it != d.end(); it++)
cout<<*it<<" ";
cout<<endl;
//使用 erase()方法从中间删除元素,其参数是迭代器位置
d.push_back(5);
//从中间删除元素,erase 的参数是迭代器位置
d.erase(d.begin()+1);
for(it = d.begin(); it != d.end(); it++)
cout<<*it<<" ";
cout<<endl;
//使用 clear()方法清空 deque 对象
d.clear();
//输出元素的个数
cout<<d.size()<<endl;
return 0;
}
list 双向链表容器
list 容器实现了双向链表的数据结构。由于 list 对象的节点并不要求在一段连续的内存中，所以对于迭代器只能通过“++”或“- -”的操作将迭代器移动到后继/前驱节点元素处。而不能对迭代器进行+n 或-n 的操作。
创建链表
//创建空链表
list<int> l;
//创建具有 n 个元素的链表
list<int> l(10);
list函数
#include <iostream>
#include <algorithm>
#include <list>
using namespace std;
int main()
{
list<int> l;
//1. 采用 push_back()方法往尾部插入新元素,链表自动扩张
l.push_back(2);
l.push_back(1);
l.push_back(5);
//2. 采用 push_front()方法往首部插入新元素,链表自动扩张
l.push_front(8);
//3. 采用 insert()方法往迭代器位置处插入新元素,链表自动扩张。注意,迭代器只能进行“++”或“- -”操作,不能进行+n 或-n 的操作,因为元素的位置并不是物理相连的。
list<int>::iterator it;
it = l.begin();
it++; //注意,链表的迭代器只能进行++或--操作,而不能进行+n 操作
l.insert(it,20);
for(it = l.begin(); it != l.end(); it++)
cout<<*it<<" ";
cout<<endl;
//反向遍历链表
list<int>::reverse_iterator rit;
for(rit=l.rbegin();rit!=l.rend();rit++)
cout<<*rit<<" ";
cout<<endl;
//找到该元素,则返回该元素迭代器位置;否则返回 end()迭代器位置
it=find(l.begin(), l.end(), 5);
if(it!=l.end())//找到
cout<<"find it"<<endl;
else
cout<<"not find it"<<endl;
//sort()方法可以对链表元素进行升序排列
l.sort();
for(it = l.begin(); it != l.end(); it++)
cout<<*it<<" ";
cout<<endl;
//unique()方法可以剔除连续重复元素,只保留一个
l.push_back(2);
l.push_back(2);
l.push_back(9);
l.unique();
for(it = l.begin(); it != l.end(); it++)
cout<<*it<<" ";
cout<<endl;
//使用 remove()方法删除链表中一个元素,值相同的元素都会被删除。
l.push_back(2);
l.remove(2);
for(it = l.begin(); it != l.end(); it++)
cout<<*it<<" ";
cout<<endl;
//pop_front()方法删除链表首元素,使用 pop_back()方法删除链表尾元素
l.pop_front();
l.pop_back();
for(it = l.begin(); it != l.end(); it++)
cout<<*it<<" ";
cout<<endl;
//erase()方法删除迭代器位置上的元素
l.push_back(5);
l.push_back(0);
it=l.begin();
it++;
it++;
l.erase(it);
for(it = l.begin(); it != l.end(); it++)
cout<<*it<<" ";
cout<<endl;
//使用 clear()方法清空链表
l.clear();
//打印链表元素个数
cout<<l.size()<<endl;
return 0;
}
bitset 位集合容器
bitset 容器是一个 bit 位元素的序列容器,每个元素只占一个 bit 位,取值为 0 或 1,因而很节省内存空间。
创建 bitset 对象时必须要指定容器的大小。bitset 对象的大小一经定义就不能修改了。
bitset函数
#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;
int print(const bitset<10> &x)
{
//下标法输出所有元素,第 0 位是最低位,第 9 位是最高位
for(int i = x.size() - 1; i >= 0; i--)
cout<<x[i];
cout<<endl;
return 0;
}
int main()
{
bitset<10> b;
//1. 采用下标法设置元素值
b[1]=1;
b[6]=1;
b[9]=1;
print(b);
//2. 采用 set(pos)方法,设置某 pos 位
b.set(1,0);
b.set(5,1);
b.set(9,0);
print(b);
//3. 采用 set()方法,一次性将元素设置为 1
b.set();
print(b);
//4. 采用 reset(pos)方法,将某 pos 位设置为 0
b.reset(0);
b.reset(2);
b.reset(3);
b.reset(4);
b.reset(5);
b.reset(7);
b.reset(8);
//直接向输出流输出全部元素
cout<<b<<endl;
return 0;
}
