C++提高编程--STL常用容器（stack容器、queue容器、list容器）详解
·
C++提高编程(四)
1 STL常用容器
1.1 stack容器
1.1.1 stack基本概念
-
栈容器，它是一种先进后出的数据结构，它只有一个出口
-
栈中进入数据称为–入栈 push
-
栈中弹出数据称为–出栈 pop
-
栈不允许有遍历行为，因为只有栈顶元素才能被访问到，要想访问到里面的元素，必须进行出栈操作，但是出栈得先把里面东西拿出来，值就会少一个，遍历是一个非质变的算法，不允许元素有改动
-
栈可以判断容器是否为空，使用empty接口
-
栈可以返回元素个数，入栈时使用size统计元素个数
例图：
1.1.2 stack常用接口
功能描述：栈容器常用接口
#include <iostream>
#include<stack>
using namespace std;
//stack容器
void test01() {
//特点：符合先进后出的数据结构
stack<int>s;
//入栈
s.push(10);
s.push(18);
s.push(15);
cout << "栈的大小：" << s.size() << endl;
//只要栈不为空，查看栈顶，并且执行出栈操作
while (!s.empty()) {
//查看栈顶元素
cout << "栈顶元素为：" << s.top() << endl;
//出栈
s.pop();
}
cout << "栈的大小：" << s.size() << endl;
}
int main() {
test01();
system("pause");
return 0;
}
输出结果为：
1.2 queue容器
1.2.1 queue容器基本概念
- 队列容器，queue是一种先进先出的数据结构，它有两个出口
- 队列容器允许从一端新增元素，从另一端移除元素
- 队列中只有队头和队尾才可以被外界使用，因此不允许有遍历行为
- 判断队列是否为空–empty
- 判断队列元素个数–size
- 队列中进数据称为–入队 push
- 队列中出数据称为–出队 pop
例图：
1.2.2 queue常用接口
功能描述：栈容器常用的对外接口
#include <iostream>
#include<queue>
#include<string>
using namespace std;
//队列 queue容器
class Person {
public:
Person(string name, int age) {
this->m_Name = name;
this->m_Age = age;
}
string m_Name;
int m_Age;
};
void test01() {
//创建队列
queue<Person>q;
//准备数据
Person p1("张三", 19);
Person p2("李四", 17);
Person p3("王五", 79);
Person p4("张飞", 12);
//入队
q.push(p1);
q.push(p2);
q.push(p3);
q.push(p4);
cout << "队列大小为：" << q.size() << endl;
//判断只要队列不为空，查看队头，查看队尾，出队
while (!q.empty()) {
//查看队头
cout << "队头元素--姓名：" << q.front().m_Name << "年龄：" << q.front().m_Age << endl;
//查看队尾
cout << "队尾元素--姓名：" << q.back().m_Name << "年龄：" << q.back().m_Age << endl;
//出队
q.pop();
}
cout << "队列大小为：" << q.size() << endl;
}
int main() {
test01();
system("pause");
return 0;
}
输出结果为：
1.3 list容器
1.3.1 list基本概念
-
功能：将数据进行链式存储
-
链表(list)是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的
-
链表的组成：链表由一系列结点组成
-
结点的组成：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域
-
STL中的链表是一个双向循环链表
-
由于链表的存储方式并不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器
例图：
list的优点：
- 采用动态存储分配，不会造成内存浪费和溢出
- 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素
list缺点：
- 链表灵活，但是空间(指针域)和时间(遍历)额外耗费较大
list有一个重要的性质：
插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。
总结：STL中List和vector是两个最常被使用的容器，各有优缺点
例图：
1.3.2 list构造函数
功能描述：创建list容器
函数原型：
- listlst; //list采用模板类实现对象的默认构造形式
- list<beg,end>; //构造函数将[beg,end)区间中的元素拷贝给本身
- list(n,elem); //构造函数将n个elem拷贝给本身
- list(const list &lst); //拷贝构造函数
#include <iostream>
#include<list>
using namespace std;
//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容器
list<int>L1;//默认构造
//添加数据
L1.push_back(10);
L1.push_back(20);
L1.push_back(30);
//遍历容器
printList(L1);//提供一个printList函数做遍历
//区间方式构造
list<int>L2(L1.begin(),L1.end());
printList(L2);
//拷贝构造
list<int>L3(L2);
printList(L3);
//n个elem
list<int>L4(4, 88);
printList(L4);
}
int main() {
test01();
system("pause");
return 0;
}
输出结果为：
1.3.3 list赋值和交换
功能描述：给list容器进行赋值，以及交换list容器
函数原型：
- assign(beg,end); //将[beg,end)区间中的数据拷贝赋值给本身
- assign(n,elem); //将n个elem拷贝赋值给本身
- list&operator=(const list &lst); //重载等号操作符
- swap(lst); //将lst与本身元素互换
#include <iostream>
#include<list>
using namespace std;
//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(90);
L1.push_back(70);
L1.push_back(30);
printList(L1);
list<int>L2;
L2 = L1;//operator=赋值
printList(L2);
list<int>L3;
L3.assign(L2.begin(), L2.end());
printList(L3);
list<int>L4;
L4.assign(10, 88);
}
//交换
void test02() {
list<int>L1;
L1.push_back(10);
L1.push_back(90);
L1.push_back(70);
L1.push_back(30);
list<int>L2;
L2.assign(5, 88 ) ;
cout << "交换前：" << endl;
printList(L1);
printList(L2);
L1.swap(L2);
cout << "交换后：" << endl;
printList(L1);
printList(L2);
}
int main() {
test01();
test02();
system("pause");
return 0;
}
输出结果为：
1.3.4 list大小操作
功能描述：对list容器的大小进行操作
函数原型：
- size(); //返回容器中元素的个数
- empty(); //判断容器是否为空
- resize(num); //重新指定容器的长度为num，若容器变长，则后面用默认值填充新位置，如果容器变短，则超出部分元素被删除
- resize(num,elem); //重新指定容器的长度为num，若容器变长，则后面用elem值填充新位置，如果容器变短，则超出部分元素被删除
#include <iostream>
#include<list>
using namespace std;
//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(70);
L1.push_back(88);
printList(L1);
//判断容器是否为空
if (L1.empty()) {
cout << "L1为空" << endl;
}
else {
cout << "L1不为空" << endl;
cout << "L1的元素个数为：" << L1.size() << endl;
}
//重新指定大小
L1.resize(8,88);
printList(L1);
L1.resize(2);
printList(L1);
}
int main() {
test01();
system("pause");
return 0;
}
输出结果为：
1.3.5 list插入和删除
功能描述：对list容器进行数据的插入和删除
函数原型：
#include <iostream>
#include<list>
using namespace std;
//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>L;
//尾插
L.push_back(10);
L.push_back(80);
L.push_back(40);
//头插
L.push_front(66);
L.push_front(88);
L.push_front(99);
printList(L);
//尾删
L.pop_back();
printList(L);
//头删
L.pop_front();
printList(L);
//insert插入
list<int>::iterator it = L.begin();
L.insert(++it, 6688);
printList(L);
//删除
it = L.begin();
L.erase(++it);
printList(L);
//移除
L.push_back(99999);
L.push_back(99999);
L.push_back(99999);
L.push_back(99999);
printList(L);
L.remove(99999);
printList(L);
//清空
L.clear();
printList(L);
}
int main() {
test01();
system("pause");
return 0;
}
输出结果为：
1.3.6 list数据存取
功能描述：对list容器中数据进行存取
函数原型：
-
front(); //返回第一个元素
-
back(); //返回最后一个元素
#include <iostream>
#include<list>
using namespace std;
//list容器--数据存取
void test01() {
list<int>L1;
L1.push_back(88);
L1.push_back(99);
L1.push_back(66);
//L1[0];不可以用[]访问list容器中的元素
//L1.at(0);不可以用at方式访问list容器中的元素
//原因是list本质是链表，每个数据不是用连续线性空间存储数据，迭代器也是不支持随机访问的
cout << "第一个元素为：" << L1.front()<< endl;
cout << "最后一个元素为：" << L1.back()<< endl;
//验证迭代器是不支持随机访问的
list<int>::iterator it = L1.begin();
//it = it + 8;//不支持随机访问
it++;
it--;//支持递增递减，双向
}
int main() {
test01();
system("pause");
return 0;
}
输出结果为：
1.3.7 list反转和排序
功能描述：将容器中的元素反转，以及将容器中的数据进行排序
函数原型：
- reverse(); //反转链表
- sort(); //链表排序
#include <iostream>
#include<list>
#include<algorithm>
using namespace std;
//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(88);
L1.push_back(66);
L1.push_back(99);
L1.push_back(68);
cout << "反转前：" << endl;
printList(L1);
//反转
L1.reverse();
cout << "反转后：" << endl;
printList(L1);
}
bool myCompare(int v1,int v2) {
//降序，就让第一个数>第二个数
return v1 > v2;
}
//排序
void test02() {
list<int>L1;
L1.push_back(88);
L1.push_back(66);
L1.push_back(99);
L1.push_back(68);
cout << "排序前：" << endl;
printList(L1);
//所有不支持随机访问迭代器的容器，不可以用标准算法，sort是一个成员函数
// 不支持随机访问迭代器的容器，内部会提供对应的一些算法
// sort(L1.begin(), L1.end());
L1.sort();//默认排序规则，从小到大，升序
cout << "排序后：" << endl;
printList(L1);
//降序
L1.sort(myCompare);
printList(L1);
}
int main() {
test01();
test02();
system("pause");
return 0;
}
输出结果为：
1.3.8 排序案例
案例描述：将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高
排序规则：按照年龄进行升序，如果年龄相同按照身高进行降序
#include <iostream>
#include<list>
#include<string>
using namespace std;
//list容器排序案例，对于自定义数据类型做排序
//按照年龄进行升序，如果年龄相同按照身高进行降序
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 comparePerson(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("曹操", 18, 189);
Person p2("吕布", 34, 185);
Person p3("刘备", 35, 183);
Person p4("孙尚香",18, 168);
Person p5("小乔",18, 174);
//插入数据
L.push_back(p1);
L.push_back(p2);
L.push_back(p3);
L.push_back(p4);
L.push_back(p5);
for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {
cout << "姓名：" << (*it).m_Name << "年龄：" << (*it).m_Age << "身高：" << (*it).m_Height << endl;
}
//排序
cout << "排序后：" << endl;
L.sort(comparePerson);
for (list<Person>::iterator it = L.begin(); it != L.end(); it++) {
cout << "姓名：" << (*it).m_Name << "年龄：" << (*it).m_Age << "身高：" << (*it).m_Height << endl;
}
}
int main() {
test01();
system("pause");
return 0;
}
输出结果为：
更多推荐
25
0- 0
已为社区贡献4条内容
所有评论(0)