STL常用容器2
stack容器
stack基本概念
stack是一种先进后出（First In Last Out,FILO）的数据结构，它只有一个出口
栈中只有顶端的元素才可以被外界使用，因此栈中不允许有遍历行为
栈中进入数据称为 -----入栈 push
栈中弹出数据称为 ------出栈 pop
stack常用接口
构造函数
stack stk; //stack采用模板类实现，stack对象的默认构造形式
stack(const stack &stk); //拷贝构造函数
赋值操作
stack& operator = (const stack &stk); //重载等号操作符
数据存取：
push(elem); //向栈顶添加元素
pop(); //从栈顶移除第一个元素
top(); //返回栈顶元素
大小操作
empty(); //判断栈是否为空
size(); //返回栈的大小
#include<iostream>
using namespace std;
#include<stack>
//#### 构造函数
//stack<T> stk; //stack采用模板类实现，stack对象的默认构造形式
//stack(const stack& stk); //拷贝构造函数
//#### 赋值操作
//stack& operator = (const stack& stk); //重载等号操作符
//#### 数据存取：
//push(elem); //向栈顶添加元素
//pop(); //从栈顶移除第一个元素
//top(); //返回栈顶元素
//#### 大小操作
//empty(); //判断栈是否为空
//size(); //返回栈的大小
void test01() {
stack<int> s;
s.push(10);
s.push(20);
s.push(30);
s.push(40);
stack<int> s1(s);
cout << "栈s的大小为" << s.size() << endl;
cout << "栈s1的大小为" << s1.size() << endl;
cout << "s1栈顶元素为" << s1.top() << endl;
while (!s.empty()) {
cout << "s栈顶元素为" << s.top() << endl;
s.pop();
}
cout << "栈s的大小为" << s.size() << endl;
}
int main() {
test01();
system("pause");
return 0;
}
queue容器
queue基本概念
Queue是一种先进先出（First In First Out）的数据结构，它有两个出口
队列容器允许从一端新增元素，从另一端移除元素
队列中只有队头和队尾才可以被外界使用，因此队列不允许有遍历行为
队列中进数据称为 — 入队 push
队列中出数据称为 — 出队 pop
queue常用接口
构造函数:
queue que; //queue采用模板类实现，queue对象的默认构造形式
queue(const queue &que); //拷贝构造函数
赋值操作
queue& operator=(const queue &que); //重载等号运算符
数据存取
push(elem); //往队尾添加一个元素
pop(); //从队头移除一个元素
back(); //返回最后一个元素
front(); //返回第一个元素
大小操作
empty(); //判断队列是否为空
size(); //返回队列的大小
#include<iostream>
using namespace std;
#include<queue>
//#### 构造函数:
//queue<T> que; //queue采用模板类实现，queue对象的默认构造形式
//queue(const queue& que); //拷贝构造函数
//#### 赋值操作
//queue& operator=(const queue& que); //重载等号运算符
//#### 数据存取
//push(elem); //往队尾添加一个元素
//pop(); //从队头移除一个元素
//back(); //返回最后一个元素
//front(); //返回第一个元素
//#### 大小操作
//empty(); //判断队列是否为空
//size(); //返回队列的大小
class Person {
public:
Person(string name, int age) {
this->m_Name = name;
this->m_Age = age;
}
string m_Name;
int m_Age;
};
void test01() {
Person p1("唐僧", 30);
Person p2("孙悟空", 18000);
Person p3("猪八戒", 28000);
Person p4("沙悟净", 27000);
queue<Person> q;
q.push(p1);
q.push(p2);
q.push(p3);
q.push(p4);
cout << "队列q的第一个元素姓名为 " << q.front().m_Name <<" 年龄为："<<q.front().m_Age<< endl;
cout << "队列q的最后一个元素为 " << q.back().m_Name <<" 年龄为：" << q.back().m_Age << endl;
cout << "队列q的大小为:" << q.size() << endl;
while (!q.empty()) {
cout << "队列q的第一个元素姓名为 " << q.front().m_Name << " 年龄为：" << q.front().m_Age << endl;
q.pop();
}
cout << "队列q的大小为:" << q.size() << endl;
}
int main() {
test01();
system("pause");
return 0;
}
list容器
list基本概念
**功能：**将数据进行链式存储
链表（list）是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的
链表的组成：
链表由一系列结点组成
结点的组成：
一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域
STL中的链表是一个双向循环链表
由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器
优点：
采用动态内存分配，不会造成内存浪费和溢出
链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
缺点：
链表灵活，但空间（指针域）和时间（遍历）额外耗费较大
List有一个重要的特性：
插入操作和删除操作都不会造成原有List迭代器的失效，这再vector是不成立的
list构造函数
函数原型：
- list list; //list采用模板类实现对象的默认构造形式
- list(beg , end) ; //构造函数将[beg , end)区间中的元素拷贝给本身
- list(n,elem); //构造函数将n个elem拷贝给本身
- list(const list &lst); //拷贝构造函数
list赋值和交换
函数原型
- assign(beg ,end); //将[ beg,end )区间中的数据拷贝赋值给本身
- assign(n,elem); //将n个elem拷贝赋值给本身
- list& operator=(const list &lst); // 重载等号操作符
- swap(lst); //将lst与本身的元素互换
#include<iostream>
using namespace std;
#include<list>
//list赋值和交换
//- assign(beg, end); //将[ beg,end )区间中的数据拷贝赋值给本身
//-assign(n, elem); //将n个elem拷贝赋值给本身
//-list & operator=(const list & lst); // 重载等号操作符
//-swap(lst); //将lst与本身的元素互换
//打印list集合
void printList(const list<int> &L) {
for (list<int>::const_iterator it = L.begin();it != L.end();it++) {
cout << *it << " ";
}
cout << endl;
}
void test01() {
//赋值
list<int>L1;
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
L1.push_back(40);
printList(L1);
list<int>L2;
L2 = L1;
printList(L2);
list<int>L3;
L3.assign(L2.begin(), L2.end());
printList(L3);
list<int>L4;
L4.assign(8, 8);
printList(L4);
//互换
L1.swap(L4);
printList(L1);
printList(L4);
}
int main() {
test01();
system("pause");
return 0;
}
list大小操作
函数原型
- size(); //返回容器中元素的个数
- empty(); //判断容器是否为空
- resize(num); //重新指定容器的长度为num，若容器变长，则默认值填充新位置；如果容器变短，则末尾超过容器长度的元素被删除
- resize(num，elem); //重新指定容器的长度为num，若容器变长，则elem填充新位置；如果容器变短，则末尾超过容器长度的元素被删除
list插入和删除
函数原型
- push_back(elem); //在容器尾部加入一个元素
- pop_back(); //删除容器中最后一个元素
- push_front(elem); //在容器开头插入一个元素elem
- pop_front(); //从容器中移除第一个元素
- insert(pos,elem); //在pos位置插elem元素的拷贝，返回新数据的位置
- insert(pos,n,elem); //在pos位置插入n个elem元素的拷贝，无返回值
- insert(pos,beg,end); //在pos位置插入[ beg,end )区间的数据，无返回值
- clear(); //移除容器的所有数据
- erase(beg,end); //删除[ beg,end)区间的数据，返回下一个数据的位置
- erase(pos); //删除pos位置的数据，返回下一个数据的位置
- remove(elem); //删除容器中所有与elem值匹配的元素
#include<iostream>
using namespace std;
#include<list>
//list插入与删除
/*
- push_back(elem); //在容器尾部加入一个元素
- pop_back(); //删除容器中最后一个元素
- push_front(elem); //在容器开头插入一个元素elem
- pop_front(); //从容器中移除第一个元素
- insert(pos,elem); //在pos位置插elem元素的拷贝，返回新数据的位置
- insert(pos,n,elem); //在pos位置插入n个elem元素的拷贝，无返回值
- insert(pos,beg,end); //在pos位置插入[ beg,end )区间的数据，无返回值
- clear(); //移除容器的所有数据
- erase(beg,end); //删除[ beg,end)区间的数据，返回下一个数据的位置
- erase(pos); //删除pos位置的数据，返回下一个数据的位置
- remove(elem); //删除容器中所有与elem值匹配的元素
*/
void printList(const list<int>&L) {
for (list<int>::const_iterator it = L.begin();it != L.end();it++) {
cout << *it << " ";
}
cout << endl;
}
void test01() {
list<int> L1;
//尾插
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
//头插
L1.push_front(1);
L1.push_front(2);
L1.push_front(3);
printList(L1);
//尾删
L1.pop_back();
printList(L1);
//头删
L1.pop_front();
printList(L1);
//insert插入
list<int>::iterator it = L1.begin();
//让迭代器偏移一个位置
it++;
L1.insert(it, 1000);
printList(L1);//2 1000 1 10 20
L1.insert(it, 8, 9);
printList(L1);//2 1000 9 9 9 9 9 9 9 9 1 10 20
list<int> L2;
L2.assign(2, 1);
printList(L2);
L2.insert(L2.begin(),L1.begin(), L1.end());
printList(L2);
//移除元素
L2.remove(1);
printList(L2);
//删除全部元素
L2.erase(L2.begin(), L2.end());
printList(L2);
//删除单个位置元素
cout << "删除前L1:" << endl;
printList(L1);//2 1000 9 9 9 9 9 9 9 9 1 10 20
L1.erase(L1.begin());
cout << "删除it位置后的L1：" << endl;
printList(L1);//2 1000 9 9 9 9 9 9 9 9 10 20
L1.clear();
printList(L1);
}
int main() {
test01();
system("pause");
return 0;
}
list数据存取
函数原型
front(); //返回第一个元素
back(); //返回最后一个元素
无法通过[]或at访问数据，原因：
list本质是链表，不是连续线性空间存储数据，迭代器也不支持随机访问
验证迭代器是否支持随机访问：
支持随机
迭代器=迭代器+n; //合法
反之则不支持
list反转和排序
函数原型
reverse(); //反转链表
sort(); //链表排序 (成员函数）
#include<iostream>
using namespace std;
#include<algorithm>
#include<list>
//reverse(); //反转链表
//sort(); //链表排序
void printList(const list<int>& l) {
for (list<int>::const_iterator it = l.begin();it != l.end();it++) {
cout << *it << " ";
}
cout << endl;
}
bool myCompare(int v1, int v2) {
return v1 > v2;
}
void test01() {
list<int> l1;
l1.push_back(10);
l1.push_back(20);
l1.push_back(30);
l1.push_front(1);
l1.push_front(2);
l1.push_front(3);
printList(l1);
//反转链表
l1.reverse();
//reverse(l1.begin(),l1.end());//可用
printList(l1);
//排序 默认升序
l1.sort();
//sort(it.begin(),it.end()); //不可用
printList(l1);
//排序 降序
l1.sort(myCompare);
printList(l1);
}
int main() {
test01();
system("pause");
return 0;
}
所有不支持随机访问迭代器的容器，不可以用标准算法
其内部有自己成员函数实现对应算法
排序案例
案例描述:
将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高
排序规则：
按照年龄进行升序，如果年龄相同按照身高进行降序
#include<iostream>
using namespace std;
#include<string>
#include<list>
//案例描述:
//将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高
//排序规则：
//按照年龄进行升序，如果年龄相同按照身高进行降序
class Person {
public:
Person(string name,int age,int height) {
this->m_Name = name;
this->m_Age = age;
this->m_Height = height;
}
string m_Name;
int m_Age;
int m_Height;
};
//指定规则排序
bool mCompare(Person &p1,Person &p2) {
if (p1.m_Age == p2.m_Age) {
return p1.m_Height > p2.m_Height;
}
else {
return p1.m_Age < p2.m_Age;
}
}
void test01() {
list<Person> l;//创建容器
//准备数据
Person p1("ww", 35, 170);
Person p2("ew", 45, 178);
Person p3("cw", 25, 185);
Person p4("hw", 15, 165);
Person p5("aw", 35, 190);
Person p6("fw", 45, 155);
//插入数据
l.push_back(p1);
l.push_back(p2);
l.push_back(p3);
l.push_back(p4);
l.push_back(p5);
l.push_back(p6);
//打印数据
for (list<Person>::iterator it = l.begin();it != l.end();it++) {
cout << "姓名为: " << (*it).m_Name << " 年龄为： " << (*it).m_Age << " 身高（cm）为: " << (*it).m_Height << endl;
}
//排序后
cout << "--------------------------" << endl;
l.sort(mCompare);
for (list<Person>::iterator it = l.begin();it != l.end();it++) {
cout << "姓名为: " << (*it).m_Name << " 年龄为： " << (*it).m_Age << " 身高（cm）为: " << (*it).m_Height << endl;
}
}
int main() {
test01();
system("pause");
return 0;
}