三、常用容器(Stack、Queue、List、Set)
2018-06-16 本文已影响0人
木鱼_cc
1.Stack 栈容器
栈同数据结构的定义和特性一样，自己去查，这里介绍栈的API
特别说明：stack没有遍历行为！！
构造函数
stack<T> stkT;//stack采用模板类实现，stack对象的默认构造函数
stack(const stack &stk);//拷贝构造函数
stack赋值操作
stack & operator=(const stack &stk);//重载等号操作符
数据存取操作
void push(const TYPE & elem);//向栈顶添加一个元素
void pop();//从栈顶移除一个元素
TYPE & top();//返回栈顶元素
大小操作
bool empty();//判断堆栈是否为空
int size();//返回堆栈的大小
2.Queue 队列
2.1queue概念
queue是一种先进先出(first in first out,FIFO)的数据类型，它有两个口，数据元素只能从一个口进，从另一个口出。队列只允许从队尾加入元素，队头删除元素，必须符合先进先出原则，queue和stack一样不具有遍历行为！
1.png
特点
- 必须从一个口数据元素入队，另一个口数据元素出队
- 不能随机存取，不支持遍历
2.2queue常用API
构造函数
queue<T> queT;//queue采用模板类实现，queue对象的默认构造形式
queue(const queue &que);//拷贝构造函数
queue存取、插入和删除操作
void push(const TYPE &elem);//往队尾添加元素
void pop();//从队头移除第一个元素
TYPE & back();//返回最后一个元素
TYPE & front();//返回第一个元素
queue赋值操作
queue& operator=(const queue &que);
queue大小操作
bool empty();//判断队列是否为空
int size();//返回队列大小
3.list容器（双向链表）
3.1list特性
链表是一种物理存储单元上非连续、非顺序的存储数据结构，数据元素的逻辑顺序是通过链表中的指针次序实现的。链表由一系列的结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域
2.png
特性总结
- 采用动态存储分配，不会造成内存浪费和溢出
- 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
- 链表灵活，但是空间和时间额外消耗较大
3.2 list常用API
list初始化
list<T> list;//默认构造函数
list(iterator beg,iterator end);//构造函数将[beg,end)区间中的元素拷贝给本身
list(int n,TYPE & elem);//构造函数将n个elem拷贝给自身
list(const list &lst);//拷贝构造函数
list数据元素插入和删除操作
void push_back(const TYPE &elem);//在容器尾部加入一个元素
void pop_back();//在容器尾部删除一个元素
push_front(const TYPE &elem);//在容器头部加入一个元素
pop_front(const TYPE &elem);//在容器开头移除一个元素
iterator insert(iterator pos,const TYPE & elem);//在pos位置插elem元素的拷贝，返回新数据的位置
void insert(iterator pos,int n,const TYPE &elem);//在pos位置插入n个elem元素
void insert(iterator pos,iterator beg,iterator end);//在pos位置插入[beg,end)区间的数据
void clear();//移除容器的所有数据
iterator erase(iterator beg,iterator end);//删除[beg,end)区间的数据，返回下一个数据的位置
iterator erase(iterator pos);//删除pos位置的数据，返回下一个数据的位置
void remove(const &TYPE elem);//删除容器中所有与elem值匹配的元素
大小操作
int size();//返回容器中的元素个数
bool empty();//判断容器是否为空
void resize(int num);//重新制定容器长度为num,若边长，则以默认值填充新位置
//若变短，则末尾超出容器长度的元素被删除
void resize(int num,const TYPE & elem);//重新制定容器长度为num,若边长，则以elem填充新位置
//若变短，则末尾超出容器长度的元素被删除
list赋值操作
void assign(iterator beg,iterator end);//将[beg,end)区间中的数据拷贝赋值给本身
void assign(int num,const TYPE &elem);//将n个elem拷贝给自身
list & operator=(const list &lst);//重载=号操作符
void swap(lst);//将lst与本身的元素互换
注意：assign和assign并不是叠加关系，而是重新构造的关系
list数据的存取
TYPE front();//返回第一个元素
TYPE back();//返回最后一个元素
list反转排列排序
void reverse();//反转链表 1,3,5 变 5,3,1
void sort();//List排序，默认从小到大
链表和数组有什么区别
- 数组必须实现定义固定的长度（元素个数），不能适应数据动态增减的情况。当数据增加时，可能超出原先定义的元素的个数；当数据减少时，造成内存浪费
- 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除
4. Set集合
4.1 set/multiset特性
set/multiset的特性是所有元素会根据元素的值自动进行排序。set是以RB-tree(红黑树,平衡二叉树的一种)为底层机制，其查找效率非常好。set容器中不允许重复元素，multiset允许重复元素
1.png
问：我们可以通过set的迭代器改变元素的值吗？
答：不行，因为set集合是根据元素值进行排序的，关系到set的排序规则，如果任意改变set的元素值，会严重破会set组织。只能先删掉，再插入，就是二叉排序树的关系嘛！！
set构造函数
set<T> st;//默认构造函数
multiset<T> mst;//multiset默认构造函数
set(const set &st);//拷贝构造函数
set赋值操作
set & operator=(const set &st);
void swap(st);//交换两个集合器
set大小操作
int size();//返回容器中元素的数目
bool empty();//判断容器是否为空
set插入和删除操作
void insert(const TYPE & elem);//在容器中插入元素
void clear();//清楚所有元素
iterator erase(iterator pos);//删除pos爹地器所指的元素，返回下一个元素的迭代器
iterator erase(iterator beg,iterator end);//删除区间[beg,end)的所有元素，返回下一个元素的迭代器
int erase(const TYPE &elem);//删除容器中值为elem的元素
void test(){
set<int> myset;//默认从小到大排序
myset.insert(4);
myset.insert(2);
myset.insert(1);
myset.insert(5);
myset.insert(2);
printSet(myset);
//删除
myset.erase(myset.begin());//删除第一个元素
myset.erase(2);//根据元素值删除
printSet(myset);
myset.erase(myset.beigin(),myset.end());//myset.clear();
cout<<"size:"<<myset.size();
}
2.png
multiset操作同理类似
#include <set>
int main(int argc, char const *argv[])
{
multiset<int> muset;
muset.insert(10);
muset.insert(20);
muset.insert(5);
muset.insert(35);
muset.insert(5);
for (multiset<int>::iterator it = muset.begin(); it != muset.end();it++)
{
cout<<*it<<" "<<endl;
}
return 0;
}
3.jpg
set查找操作
iterator find(const TYPE &key);//在当前集合中查找等于key值的元素，并返回指向该元素的迭代器；如果没有找到，返回指向集合最后一个元素的迭代器。
iterator lower_bound(const TYPE &keyElem);//返回第一个>=keyElem元素的迭代器
iterator upper_bound(const TYPE &keyElem);//返回第一个>keyElem元素的迭代器
pairii equal_bound(const TYPE &keyElem);//返回容器中key与keyElem相等的上下限的两个迭代器
class Teacher
{
public:
Teacher(int id,int age){
this->id = id;
this->age = age;
}
private:
int id;
int age;
}
class compare
{
public:
bool operator()(Teacher t1,Teacher t2){
return t1.id>t2.id;
}
}
void test(){
Teacher t1(1,2),t2(3,4),t3(5,6);
set<Teacher,compare> myset;
myset.insert(t1);
myset.insert(t2);
myset.insert(t3);
set<Teacher,compare>::iterator pos = myset.find(Teacher(3,10));
if (pos == myset.end())//竟然能查找到，因为它是根据id排序的
//所以查找也是根据id查找的,id = 3和t2重复！
//所以能查到
{
cout<<"没有查找到!"<<endl;
}
else{
cout<<"查找到:"<<pos->id<<":"<<pos->age<<endl;
}
}
----------------------------------------------------
void test2(){
set<int> myset;
myset.insert(10);
myset.insert(5);
myset.insert(1);
myset.insert(8);
set<int>::iterator pos = myset.lower_bound(5);//查找第一个>=5的迭代器
if (pos ==myset.end())
{
cout<<"没有找到"<<endl;
}
else{
cout<<"找到:"<<*pos<<endl;
}
pos = myset.upper_bound(5);//返回第一个>keyElem元素的迭代器
if (pos ==myset.end())
{
cout<<"没有找到"<<endl;
}
else{
cout<<"找到:"<<*pos<<endl;
}
pair<set<int>::iterator,set<int>iterator> pos2 = myset.equal_range(5);
if (pos2.first == myset.end())
{
cout<<"没有找到"<<endl;
}
else{
cout<<"找到:"<<*(pos2.first)<<endl;
}
if (pos2.second == myset.end())
{
cout<<"没有找到"<<endl;
}
else{
cout<<"找到:"<<*(pos2.first)<<endl;
}
}
问题：我们发现打印出来set集合中的元素都是从小到大的升序排序，那么我们如何制定排序为降序呢？这个问题呢？我们需要了解函数对象的概念。
#include <functional>//预定义函数对象
set<int,greater<int>> myset;//从大到小
set<int,less<int>> myset;//从小到大
template<class T>
class compare{
public:
bool operator()(T v1,T v2) const{
return v1>v2;
}
};
//函数对象
compare mycom;
mycom<int>(1,2);//函数对象 仿函数
set<int,compare<int>> myset;
