C++常用容器（下）---stack、queue、list、set、map

Ne0inhk

23 Mar 2026 — 21 min read

C++常用容器（下）—stack、queue、list、set、map

一、stack容器

概念：栈，一种先进后出（ first in，last out ）的数据结构，只有一个出口（栈顶），另外一端为栈底。入栈使用 push ，出栈使用 pop 。

栈不允许有遍历的行为，只有栈顶元素才能被外界所访问到。
栈可以判断容器是否为空，有函数 empty（）；
可以访问栈内元素个数，函数 size（）；

1.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>stk; //入栈 stk.push(1); stk.push(2); stk.push(3); cout << "栈的原始大小：" << stk.size() << endl; //查看栈中数据，看完一个元素要做出栈操作，（栈不空的情况下） while (!stk.empty()) { //查看栈顶的元素 cout << stk.top() << endl; //3 2 1 //出栈，后面才可以访问下一个元素 stk.pop(); } cout << "栈的大小： " << stk.size() << endl; }

二、queue容器

概念：队列，一种先进先出（ first in，first out）的数据结构，有两个出口（两个端口）。对头出队，对尾入队

两端都可以访问数据
只有队头和队尾才可以被访问到；不接受遍历行为
插入数据，入队push ，在队尾进行操作
删除数据，出队 pop ，在队头进行操作

1.常用的接口：

构造函数：

queue<T> q; //默认构造函数，T为数据类型，可以是系统的，也可以是自定义的 queue(const queue &que); //拷贝构造函数

其他函数：

q.empty(); //判断队列是否为空 q.size(); //访问元素个数 q.push(elem); //往队尾添加元素 q.pop(); //取出队头元素 q.back(); //返回最后一个元素（队尾元素） q.front(); //返回第一个元素（队头元素）

示例：

class Person { public: Person(int age, string name) { m_age = age; m_name = name; } int m_age; string m_name; }; void test02() { queue<Person>q; //<T>表示数据类型，可以是系统的，也可以是自定义的 //准备数据 Person p1(1,"lan"); Person p2(2,"xi"); Person p3(3,"fei"); Person p4(4,"mei"); Person p5(5,"nuan"); //入队 q.push(p1); q.push(p2); q.push(p3); q.push(p4); q.push(p5); cout << "对内元素：" << q.size() << endl; //判断，只要队列不为空，就查看队头，出队 while(!q.empty()) { //查看队头 cout << "队头元素：" << q.front().m_age << " " << q.front().m_name << endl; //查看队尾 cout << "队尾元素：" << q.back().m_age << " " << q.back().m_name << endl; //出队 q.pop(); } cout << "队内大小：" << q.size() << endl; }

三、list容器

1.概念：

链表，一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。

链表由一系列结点组成；结点由两个部分组成（一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域）

优点：可以对任意的位置进行快速的添加或删除元素，只需要添加/删除对应结点，修改指针即可

缺点：对于容器的遍历速度，没有数组快（数组是连续的存储空间，只需要偏移地址就可，但链表要先去寻找下一个元素的地址，再访问）；占用的存储空间比数组大（存储数据域和指针域）

STL中的链表是一个双向循环链表，即两端都可以进行遍历访问，每个结点有两个指针，一个指向左边（上一个结点）的元素，一个指向右边（下一个结点）的元素

链表不能跳跃式访问，因为不是连续的存储空间，所以只能一个一个找，是双向迭代器。

采用动态存储分配，不会造成内存的浪费和溢出；

链表执行删除和插入方便，修改指针即可，不需要移动大量元素，vector需要移动元素

空间和时间耗费比较大，插入和删除操作都不会造成原有的list迭代器失效，不影响，还是指向原有。vector会失效（因为vector若内存空间大小改变，就会重新寻找新的空间存储数据，所以原来的迭代器会失效，因为那一片内存空间已经不是最新的数据存储空间了）。

2.list 构造函数

创建 list 容器，函数原型：

list<T>lst; //list采用模板类实现，对象的默认构造形式 list(beg,end); //构造函数将[beg，end]区间内的元素拷贝给本身 list(n,elem); //构造函数将n个elem拷贝给本身 list(const list &lst); //拷贝构造函数

示例：

void printList(const list<int>& L) { for (list<int>::const_iterator it = L.begin(); it != L.end(); it++) { cout << *it << " "; } cout << endl; } void test03() { //创建list容器 list<int>l1; //添加数据 l1.push_back(1); l1.push_back(2); l1.push_back(3); l1.push_back(4); l1.push_back(5); //遍历容器 printList(l1); //区间构造方式 list<int>l2(l1.begin(), l1.end()); //将l1的开始到结束区间的元素赋值给l2 printList(l2); //拷贝构造 list<int>l3(l2); printList(l3); //n个elem list<int>l4(7, 8); printList(l4); }

3.list赋值和交换

函数原型：

assign(beg,end); //将beg到end区间内的值赋值给本身 assign(n,elem); //将n个elem拷贝赋值给本身 list& operator=(const list &lst);//重载等号操作符，直接等 swap(lst); //将lst与本身的元素互换

示例：

void test04() { list<int>l1; l1.push_back(1); l1.push_back(2); l1.push_back(3); l1.push_back(4); l1.push_back(5); l1.push_back(6); printList(l1);//1 2 3 4 5 6 list<int>l2; l2 = l1; printList(l2);// 1 2 3 4 5 6 list<int>l3; l3.assign(l2.begin(), l2.end()); printList(l3);// 1 2 3 4 5 6 list<int>l4; l4.assign(7, 8); printList(l4);// 8 8 8 8 8 8 8 //交换 l2.swap(l4); printList(l2);// 8 8 8 8 8 8 8 printList(l4);//1 2 3 4 5 6 }

4.list 容器大小操作

函数原型

size(); //返回容器中元素的个数 empty(); //判断容器是否为空 resize(num); //重新指定容器大小为num，若容器变长，以默认值填充新位置，若容器变短，则末尾超过容器长度的元素被删除 resize(num,elem); //重新指定容器大小为num，若容器变长，以elem填充新位置，若容器变短，则末尾超过容器长度的元素被删除

示例：

void test05() { list<int>l1; l1.push_back(1); l1.push_back(2); l1.push_back(3); l1.push_back(4); l1.push_back(5); printList(l1);//1 2 3 4 5 //判断容器是否为空 if (l1.empty()) { cout << "l1 is empty!" << endl; } else { cout << "l1 is not empty!" << endl; cout << "容器大小：" << l1.size() << endl;//5 } //重新指定大小 l1.resize(6); printList(l1);//1 2 3 4 5 6 l1.resize(7, 7);//1 2 3 4 5 6 7 printList(l1); }

5.list 容器的插入和删除

函数原型：

push_back(elem); //在容器尾部插入元素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 test06() { list<int>l1; //插入元素 l1.push_back(2);//从后面插入,2 l1.push_back(3);//从后面插入, 2 3 l1.push_front(1);//从前端插入, 1 2 3 l1.push_front(0);//从前端插入，0 1 2 3 printList(l1);//0 1 2 3 //删除元素 l1.pop_back();//从后端删除一个元素，0 1 2 l1.pop_front();//从前面删除一个元素， 1 2 printList(l1);//1 2 //指定位置插入指定值 l1.insert(l1.begin(), 0);//在第一个位置插入0 printList(l1);//0 1 2 list<int>::iterator it = l1.begin(); l1.insert(++it, 0);//在it的后一个位置插入0 printList(l1);//0 0 1 2 //指定位置删除 it = l1.begin();//复位，指向开始 l1.erase(it);//删除 printList(l1);//0 1 2 it = l1.begin(); l1.erase(++it);//删除第二个元素 printList(l1);//0 2 //移除与指定元素相同的元素 l1.remove(0); printList(l1);//2 //清空 l1.clear(); printList(l1);// }

6.list 容器的数据粗存取

原型函数：

front(); //返回第一个元素 back(); //返回最后一个函数

示例：

void test07() { list<int>l; l.push_back(1); l.push_back(2); l.push_back(3); l.push_back(4); l.push_back(5); cout << "the first elem is: " << l.front() << endl;//1 cout << "the last elem is: " << l.back() << endl;//5 }

由于list容器的底层结构的原因，每个数据不是用连续的线性空间存储，每个结点的地址不连续，所以不支持[]和at（）随机访问。迭代器只能一个一个的++，–，不支持跳跃式的随机访问

7.list 容器的反转和排序

函数原型：

reverse(); //反转链表 sort(); //排序链表

示例：

bool myCompare(int v1,int v2) { //降序，第一个数大于第二个数 return v1 > v2; } void test08() { list < int>l; l.push_back(1); l.push_back(2); l.push_back(6); l.push_back(5); l.push_back(3); l.push_back(4); //排序 l.sort(); printList(l);//默认升序排序。1 2 3 4 5 6 //降序排序 //l.sort(myCompare);//降序排序,这里的myCompare,返回值为bool类型 //printList(l);//6 5 4 3 2 1 //反转 l.reverse(); printList(l);// 6 5 4 3 2 1 }

所有不支持随机访问的迭代器都不可以用标准的算法algrithm，比如sort（支持随机访问的迭代器就可以使用sort（beg，end））。不提供随机访问的迭代器，内部会提供一些算法函数，比如这里的sort

排序案例

将Person自定义数据类型进行排序，Person中属性有姓名、年龄、身高。按照年龄进行升序排序，如果年龄相同按照身高进行降序排序

class Person { public: Person(int age, string name, int high) { this->m_Age = age; this->m_Name = name; this->m_High = high; } int m_Age; string m_Name; int m_High; }; //高级排序 bool comparePerson(Person& p1, Person& p2) { //按照年龄 升序,年龄相同，按照身高降序排序 if (p1.m_Age == p2.m_Age) { return p1.m_High > p2.m_High;//降序排序 } return p1.m_Age < p2.m_Age; } void test01() { //准备数据 Person p1(10, "懒羊羊", 10); Person p2(13, "喜羊羊", 15); Person p3(13, "沸羊羊", 16); Person p4(12, "美羊羊", 13); Person p5(15, "暖羊羊", 18); //创建链表，并插入数据； list<Person>l1; l1.push_back(p1); l1.push_back(p2); l1.push_back(p3); l1.push_back(p4); l1.push_back(p5); for (list<Person>::iterator it = l1.begin(); it != l1.end(); it++) { cout << (*it).m_Name << " " << (*it).m_Age << " " << it->m_High << endl; } cout << "排序后：" << endl; //排序 l1.sort(comparePerson); for (list<Person>::iterator it = l1.begin(); it != l1.end(); it++) { cout << (*it).m_Name << " " << (*it).m_Age << " " << it->m_High << endl; } }

list类型为自定义类型时，排序需要自定义排序方法

四、set / multiset容器

1.基本概念

集合容器/关联式容器，所有元素都会在插入时自动被排序，底层结构是用二叉树实现。包含头文件set

set和multiset区别：

set不允许有重复的元素；
multiset可以有重复元素；

构造和赋值操作

原型函数：

set<T>st; //默认构造函数 set(const set &st); //拷贝构造函数 set& operator=(const set &st); //重载等号操作符

示例：

void test01() { set<int>s;//创建容器 //该容器插入数据的方式只有insert s.insert(1); s.insert(5); s.insert(3); s.insert(4); s.insert(2); //遍历容器 printSet(s);//1 2 3 4 5 //拷贝构造函数 set<int>s2(s); printSet(s2); //等号重载赋值 set<int>s3; s3 = s2; printSet(s3);

若要插入重复的值，则使用multiset。插入数据的方式只有insert

2.大小和交换

函数原型：

size(); empty(); swap(st);

使用示例：

void test02() { set<int>s1; s1.insert(1); s1.insert(2); s1.insert(4); s1.insert(3); s1.insert(5); set<int>s2; s2.insert(6); s2.insert(7); s2.insert(9); s2.insert(5); s2.insert(8); //遍历： printSet(s1);//1 2 3 4 5 printSet(s2);//5 6 7 8 9 if (s1.empty()) { cout << "s1 is empty!" << endl; } else { cout << "s1 is not empty!" << endl; cout << "s1的大小：" << s1.size() << endl;//5 } //交换 s1.swap(s2); printSet(s1);//5 6 7 8 9 printSet(s2);//1 2 3 4 5 }

set 容器不允许有相同的元素存在，所以没有重新设置容器容量大小的函数，只有获得该容器容量大小的函数。

3.set 容器的插入和删除

函数原型：

insert(elem); //在容器中插入元素 clear(); //清除所有元素 erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器 erase(beg,end); //删除区间beg到end的元素，返回下一个元素的迭代器 erase(elem); //删除值为elem的元素

使用示例：

void test03() { //创建容器 set<int>s1; //插入数据 s1.insert(5); s1.insert(7); s1.insert(6); s1.insert(8); s1.insert(4); s1.insert(3); //遍历输出数据 printSet(s1);//3 4 5 6 7 8 //删除数据 set<int>::iterator it = s1.begin(); s1.erase(it);//删除指定pos迭代器位置的值 printSet(s1);//4 5 6 7 8 //删除重载版本 s1.erase(4); printSet(s1);//5 6 7 8 //清空 s1.clear(); printSet(s1);// }

4.set 查找和统计

函数原型：

find(key); //查找key是否存在，若存在，返回该键元素的迭代器，若不存在，返回set.endd() count(key); //统计key的元素个数

使用示例：

void test04() { //创建容器 set<int>s1; //插入数据 s1.insert(7); s1.insert(8); s1.insert(6); s1.insert(5); s1.insert(9); printSet(s1); //查找元素 set<int>::iterator it; it = s1.find(6); //判断是否查找到数据 if (it != s1.end()) { cout << "find it: " << *it << endl; } else { cout << "not find" << endl; } //统计 int num = s1.count(5); cout << "num = " << num << endl; }

对于set而言，统计的结果只能是 0 或 1 。

5.set 和 multiset 的区别

区别：

set 不可以插入重复数据，而multiset可以；
set插入数据的同时会返回插入结果，表示插入是否成功；
multiset 不会检测数据，因此可以插入重复数据

void test05() { set<int>s1; pair<set<int>::iterator,bool> ret = s1.insert(7); pair<set<int>::iterator,bool> ret1 = s1.insert(7); //判断是否插入成功 if (ret.second) { cout << "the first insert is succesful!" << endl;//√ } else { cout << "the first insert is fail" << endl; } if (ret1.second) { cout << "the second insert is succesful" << endl; } else { cout << "the second insert is fail" << endl;//√ } multiset<int>s2; s2.insert(7); s2.insert(7); for (multiset<int>::iterator it = s2.begin(); it != s2.end(); it++) { cout << *it << " "; } cout << endl; }

set 容器 insert 插入时，返回值类型为 pairib ，pairib是一个对组（迭代器，bool）

multiset 容器 insert插入时，返回值类型是 iterator ，直接插入，返回迭代器，所以可以插入重复的值

6.pair的使用，创建pair对组

概念：成对出现的数据，利用队组可以返回两个数据

创建方式：

pair<type,type> p (value1,value2); pair<type,type> p = make_pair(value1,value2);

使用示例：

void test06() { //第一种方式 pair<string, int>p("懒羊羊", 10); //打印数据 cout << "姓名：" << p.first << " age: " << p.second << endl; //第二种方式 pair<string, int> p1 = make_pair("喜羊羊", 13); cout << "name: " << p1.first << " age: " << p1.second << endl; }

7.set 容器排序

（1）利用仿函数，可以指定改变排序规则

class MyCompare { public: //这里如果没有const会报错C3848错误，但是在code：blocks中可以运行，是visual studio 的编译问题，这这里加上const限定修饰，不会报错 bool operator()(int v1,int v2)const//仿函数，返回值为bool类型，重载类型为（），第二个（）为函数的括号 { return v1 > v2;//降序 } }; void test07() { set<int>s1; s1.insert(7); s1.insert(8); s1.insert(6); s1.insert(5); s1.insert(9); //默认情况是从小到大排序 for (set<int>::iterator it = s1.begin(); it != s1.end(); it++) { cout << *it << " "; } cout << endl; //指定排序规则，要在排序之前指定，现在指定从大到小 set<int, MyCompare>s2;;//利用仿函数排序规则进行插入排序 s2.insert(9); s2.insert(5); s2.insert(6); s2.insert(7); s2.insert(8); for (set<int,MyCompare>::iterator it1 = s2.begin(); it1 != s2.end(); it1++) { cout << *it1 << " "; } cout << endl; }

（2）set存放自定义数据类型，指定排序规则

class Person { public: Person(string name,int age) { this->m_Name = name; this->m_Age = age; } string m_Name; int m_Age; }; class comparePerson { public: bool operator()(const Person& p1, const Person& p2)const { //按照年龄进行降序 return p1.m_Age > p2.m_Age; } }; void test08() { //自定义数据类型都会指定排序规则 set<Person,comparePerson>s1; Person p1("懒羊羊", 10); Person p2("喜羊羊", 13); Person p3("费羊羊", 14); s1.insert(p1); s1.insert(p2); s1.insert(p3); for (set<Person,comparePerson>::iterator it = s1.begin(); it != s1.end(); it++) { cout << "name: "<<it->m_Name << " age: "<<it->m_Age << endl; } cout << endl; }

五、map / multimap容器

1.基本概念

map 中所有元素都是 pair 对组
pair 中第一个元素为 key（键值），起到索引作用，第二个元素为value（实值）
所有元素都会根据元素的键值（key）自动排序

本质：map / multimap 属于关联式容器，底层结构是用二叉树实现

优点：可以根据key值快速找到value值

map / multimap区别：map不允许容器中有重复key值元素，multimap允许有重复的key值元素

2.map 构造和赋值

函数原型：

map<T1,T2>mp; //默认构造 map(const map &mp); //拷贝构造 map&operator=(const map &mp); //重载等号操作符

使用示例：

//遍历函数 void printMap(map<int, int>& mp) { for (map<int, int>::iterator it = mp.begin(); it != mp.end(); it++) { //it是一个迭代器，本身是一个指针，若要.使用，这需要指针解引用*，反之可以直接->指向即可 cout << "key = " << (*it).first << " value = " << it->second << endl; } cout << endl; } //map容器构造与赋值 void test01() { map<int, int>mp; mp.insert(pair<int, int>(1, 10)); mp.insert(pair<int, int>(2, 20)); mp.insert(pair<int, int>(3, 30)); mp.insert(pair<int, int>(4, 40)); mp.insert(pair<int, int>(5, 50)); printMap(mp); //拷贝构造 map<int, int>m2(mp); printMap(m2); //赋值 map<int, int>m3; m3 = m2; printMap(m3); }

map容器中所有元素都是成对出现的，所有元素插入时都得使用对组

3.map 容大小和交换

函数原型：

size(); //返回目前容器中元素的个数 empty(); //判断容器是否为空 swap(mp); //交换两个集合容器

使用示例：

void test02() { map<int, int>m1; m1.insert(pair<int, int>(1, 10)); m1.insert(pair<int, int>(2, 20)); m1.insert(pair<int, int>(3, 30)); m1.insert(pair<int, int>(4, 40)); m1.insert(pair<int, int>(5, 50)); //大小 if (m1.empty()) { cout << "the map vector is empty! " << endl; } else { cout << "the map vector is not empty!" << endl; cout << "the map size is: " << m1.size() << endl; } //交换 map<int, int>m2; m2.insert(pair<int, int>(5, 50)); m2.insert(pair<int, int>(6, 60)); m2.insert(pair<int, int>(7, 70)); m2.insert(pair<int, int>(8, 80)); m2.insert(pair<int, int>(9, 90)); cout << "befor swap: " << endl; printMap(m1); printMap(m2); m1.swap(m2); cout << "after swap: " << endl; printMap(m1); printMap(m2); }

4.map 容器插入和删除

函数原型：

insert(elem); //在容器中插入元素 clear(); //清除所有元素 erase(pos); //删除pos迭代器所指的元素，返回下一个元素的迭代器 erase(beg,end); //删除区间beg到end的元素，返回下一个元素的迭代器 erase(key); //删除容器中值为key的元素

使用示例：

void test03() { map<int, int>m1; //插入数据 m1.insert(pair<int, int>(1, 10));//第一种方法 m1.insert(make_pair(2, 20));//第二种 m1.insert(map<int, int>::value_type(3, 30));//第三种 m1[4] = 40;//第四种，不推荐使用 //打印遍历map容器 printMap(m1); cout << m1[5] << endl;//没有插入第五个元素，会自行创建，键值为5，实值为0 //不建议用[]插入值，但是可以用key访问到value值 //删除 m1.erase(m1.begin());//删除第一个元素 m1.erase(3);//删除key值为3的元素，若填入没有的key值，则不会变化 m1.erase(m1.begin(), m1.end());//删除区间内的值，相当于清空 m1.clear();//清空容器 }

不建议用[]插入值，但是可以用key访问到value值

5.map容器查找和统计

函数原型：

find(key); //查找key是否存在，若存在，返回该键的元素的迭代器，若不存在在，返回set.end(); count(key); //统计key的元素的个数

使用示例：

void test04() { map<int, int>m1; m1.insert(make_pair(7, 70)); m1.insert(pair<int, int>(6, 60)); m1.insert(make_pair(8, 80)); m1.insert(make_pair(9, 90)); m1.insert(make_pair(5, 50)); //查找 map<int, int>::iterator pos = m1.find(7); if (pos != m1.end()) { cout << "find it,the key is " << (*pos).first << " , the value is " << pos->second << endl; } else { cout << "cannot find it !" << endl; } //统计 cout << "the key is 3 have " << m1.count(3) << " 个" << endl; }

map 容器中不允许插入重复的key的元素，第二个一样的key的值不会被插入，map统计的结果只能是0或1，multimap的count统计可能大于1.

6.map 容器排序sort（）

//map排序 //设置仿函数，改变排序规则，默认排序规则为升序 class myCompare { public: bool operator()(int v1, int v2)const { return v1 > v2;//降序排序 } }; void test05() { map < int, int,myCompare > m1; m1.insert(make_pair(7, 70)); m1.insert(make_pair(9, 90)); m1.insert(make_pair(6, 60)); m1.insert(make_pair(5, 50)); m1.insert(pair<int, int>(8, 80)); for (map<int, int,myCompare>::iterator it = m1.begin(); it != m1.end(); it++) { //it是一个迭代器，本身是一个指针，若要.使用，这需要指针解引用*，反之可以直接->指向即可 cout << "key = " << (*it).first << " value = " << it->second << endl; } }

利用仿函数，可以改变排序规则

C++常用容器（下）---stack、queue、list、set、map

Ne0inhk