C++常用容器(下)---stack、queue、list、set、map
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; } } 利用仿函数,可以改变排序规则