目录

基本概念

dequeue的基本使用：

queue的基本使用：

priority_queue基本操作：

list的基本方法：

参考：

---

 

基本概念

双端队列deque： 

 底层数据结构为一个中央控制器和多个缓冲区，详细见STL源码剖析P146，支持首尾（中间不能）快速增删，也支持随机访问，deque是一个双端队列(double-ended queue)，也是在堆中保存内容的.它的保存形式如下:

[堆1] --> [堆2] -->[堆3] --> ...每个堆保存好几个元素,然后堆和堆之间有指针指向,看起来像是list和vector的结合品.

适配器queue priority_queue：

端单queue:底层一般用list或deque实现，封闭头部即可，不用vector的原因应该是容量大小有限制，扩容耗时

优先级队列priority_queue：底层实现是vector，使用堆的方式创建（堆）。

list  底层数据结构为双向链表，支持快速增删

dequeue的基本使用：

#include"iostream"
#include"deque"
#include"algorithm"using namespace std;void PrintDeque(deque<int>&d)
{for (deque<int>::iterator it = d.begin(); it != d.end(); it++){cout << *it << ' ';}cout<< endl;
}void baseoperator()
{//初始化deque<int>d1;d1.push_back(1);d1.push_back(2);d1.push_back(3);d1.push_front(-1);d1.push_front(-2);d1.push_front(-3);deque<int>d2(10);for (int i = 0; i < 10; i++){d2[i] = i + 7;}PrintDeque(d1);cout << "头部元素：" << d1.front() << endl;cout << "尾部元素：" << d1.back() << endl;//删除头部尾部元素d1.pop_back();d1.pop_front();PrintDeque(d1);//查找2的数组下标deque<int>::iterator it =find(d1.begin(), d1.end(), 2);if (it != d1.end()){    //distance()算从形参1到形参2的距离cout << "2的下标是:" << distance(d1.begin(), it) << endl;}else{cout << "没有找到2" << endl;}//插入和删除d2.erase(d2.begin(), d2.end() - 8);//删除指定的区间PrintDeque(d2);d2.erase(d2.begin());//删除指定位置的元素PrintDeque(d2);d2[1] = 2;d2[4] = 2;d2[6] = 2;PrintDeque(d2);for (deque<int>::iterator it = d2.begin(); it != d2.end();){if (*it == 2){it = d2.erase(it);//eraser删除之后，将迭代器自动向后移一位}elseit++;}PrintDeque(d2);//头插和尾插d2.insert(d2.begin(), -100);d2.insert(d2.end(), 100);PrintDeque(d2);
}void main()
{baseoperator();system("pause");
}

queue的基本使用：

#include"iostream"
#include"algorithm"
#include"queue"using namespace std;class Teacher//同一工程不同文件定义名字相同类或函数会串包（定义不同）若完全相则不会
{
public:Teacher(){age = 0;strcpy(name, "NULL");}~Teacher(){}void print(){cout << name << '\t' << age << endl;}
public:char name[64];int age;
};void queuebaseOpt()
{queue<int> q1;q1.push(1);q1.push(2);q1.push(3);q1.back() = 4;q1.front() = -1;while (!q1.empty()){cout << q1.front()<<' ';q1.pop();}
}//算法和容器分离
void queuebaseOptTeacher()
{queue<Teacher> q1;queue<Teacher> v2;//容器：存放非基础类型Teacher t1, t2, t3,t4;t1.age = 23;t2.age = 25;t3.age = 30;t4.age = 34;strcpy(t4.name, "maliu");strcpy(t1.name, "zhangsan");strcpy(t2.name, "lisi");strcpy(t3.name, "wangwu");q1.push(t1);q1.push(t2);q1.push(t3);q1.back() = t4;while (!q1.empty()){cout << q1.front().name <<'\t'<< q1.front().age<< endl;q1.pop();}
}void main()
{//queuebaseOpt();queuebaseOptTeacher();system("pause");
}

priority_queue基本操作：

 

/使用方法 priority(Type,Conteiner,Function)
//std::priority_queue<T, std::vector<T>, greater<T>> pq;
//不加后面两个参数的话默认为 container 默认为vector function默认为less  大顶堆 
//小顶堆 基本类型 priority_queue<int, vector<int>, greater<int> >q3;
//自定义型 则重载< 
//函数greater在<functional>
class Teacher_08
{
public:Teacher_08(){age = 0;strcpy(name, "NULL");}~Teacher_08(){}void print(){cout << name << '\t' << age << endl;}bool operator<(Teacher_08 &a) const{if (this->age == a.age)return this->age <= a.age;elsereturn (this->age > a.age);}
public:char name[64];int age;
};void baseOpt_priqueue()
{priority_queue<int> q1;//默认是最大值优先队列 q1等价于q2priority_queue<int, vector<int>, less<int>>q2;priority_queue<int, vector<int>, greater<int> >q3;q2.push(1);q2.push(3);q2.push(4);q2.push(6);cout << "q2.size" << q2.size() << endl;while (!q2.empty()){cout << q2.top() << ' ';q2.pop();}cout << endl;q3.push(6);q3.push(3);q3.push(2);q3.push(1);while (!q3.empty()){cout << q3.top() << ' ';q3.pop();}cout << endl;Teacher_08 t1, t2, t3;priority_queue<Teacher_08>q4;t1.age = 39;t2.age = 25;t3.age = 30;strcpy(t1.name, "zhangsan");strcpy(t2.name, "lisi");strcpy(t3.name, "wangwu");}void main()
{baseOpt_priqueue();system("pause");}

list的基本方法：

#include"iostream"
#include"list"using namespace std;
void PrintList(list<int>&l1)
{for (list<int>::iterator it = l1.begin(); it != l1.end(); it++){cout << *it << ' ';}cout << endl;
}void basrOptList()
{list<int>l1;l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_front(1);l1.push_back(5);cout << "list的大小" << l1.size() << endl;PrintList(l1);//list不能随机访问 it + 5非法//1 list的下标从0开始   2 inssert 插入到制定下标位置，原来位置的数往后挪//1 2 3 4 5list<int>::iterator it = l1.begin();it++;	it++;	it++;l1.insert(it, 100);PrintList(l1);//删除插入//	list.insert(pos,elem);   //在pos位置插入一个elem元素的拷贝，返回新数据的位置。//	list.insert(pos, n, elem);   //在pos位置插入n个elem数据，无返回值。//  	list.insert(pos, beg, end);   //在pos位置插入[beg,end)区间的数据，无返回值。//	list.clear();		//移除容器的所有数据//	list.erase(beg, end);  //删除[beg,end)区间的数据，返回下一个数据的位置。//	list.erase(pos);    //删除pos位置的数据，返回下一个数据的位置。//	lst.remove(elem);   //删除容器中所有与elem值匹配的元素。list<int>::iterator itA = l1.begin();l1.erase(itA, it);	PrintList(l1);l1.insert(l1.begin(), -100);	l1.insert(it, 3, -100);   PrintList(l1);l1.remove(-100);PrintList(l1);
}
void main()
{basrOptList();system("pause");}

参考：

<<c++ primer >>

C++ Reference