stack容器
stack(栈)容器是一种先进后出的容器,两端只有一个开口,只能从这一个开口插入和删除数据。
头文件
使用时包含头文件stack
#include<stack>
构造函数
stack<T> stkT;//stack采用模板类实现,stack对象的默认构造形式 stack(const stack &stk);//拷贝构造函数
赋值函数
stack&operator=(const stack &stk);//重载等号操作符
数据存取
push(elem);//向栈顶添加元素 pop();//从栈顶移除第一个元素 top();//返回栈顶元素
大小函数
empty();//判断堆栈是否为空 size();//返回堆栈的大小
queue容器
Queue是一种先进先出(First In First Out,FIFO)的数据结构,它有两个出口。
- 1.队列容器允许从一端新增元素,从另一端移除元素
- 2.队列中只有对头和队尾才可以被外界使用,因此队列不允许有遍历的行为
- 3.队列中进数据称为–入队push
- 4.队列中出数据称为–出队pop
头文件
queue模版类的定义在头文件中。
#include<queue>
构造函数
queue<T> queT;//queue采用模板类实现,queue对象的默认构造形式 queue(const queue &que);//拷贝构造函数 //案例 queue<int> q1; queue<int> q2(q1);
相关函数
push(elem);//往队尾添加元素 pop();//从队头移除第一个元素 back();//返回最后一个元素 front();//返回第一个元素 empty();//判断队列是否为空 size();//返回队列的大小
deque容器
deque双端队列,可以对头端和尾端进行插入删除操作。
deque队列为一个给定类型的元素进行线性处理,像向量一样,它能够快速地随机访问任一个元素,并且能够高效地插入和删除容器的尾部元素。但它又与vector不同,deque支持高效插入和删除容器的头部元素。
构造函数
deque<T> deqT; //默认构造形式 deque(beg, end); //构造函数将[beg,end]区间中的元素拷贝给本身 deque(n, elem); //构造函数将n个elem拷贝给本身 deque(const deque &deq); //拷贝构造函数
案例:
deque<int> a; // 定义一个int类型的双端队列a deque<int> a(10); //定义一个int类型的双端队列a,并设置初始大小为10 deque<int> a(10, 1); //定义一个int类型的双端队列a,并设置初始大小为10且初始值都为1 deque<int> b(a); //定义并用双端队列a初始化双端队列b deque<int> b(a.begin(), a.begin()+3); //将双端队列a中从第0个到第2个(共3个)作为双端队列b的初始值
添加函数
d.push_front(const T& x);//头部添加元素 d.push_back(const T& x);//末尾添加元素 d.insert(iterator it, const T& x);//任意位置插入一个元素 d.insert(iterator it, int n, const T& x);//任意位置插入n 个相同元素 d.insert(iterator it, iterator first, iterator last);//插入另一个向量的[forst,last] 间的数据
案例:
#include <iostream> #include <deque> using namespace std; int main(){ deque<int> d1; //头部增加元素 d1.push_front(4); //末尾添加元素 d1.push_back(5); //任意位置插入一个元素 deque<int>::iterator it = d1.begin();d1.insert(it, 2); //任意位置插入n个相同元素 it = d1.begin(); d1.insert(it, 3, 9); //插入另一个向量的[forst,last]间的数据 deque<int> d2(5, 8); it = d1.begin(); d1.insert(it, d2.end() -1, d2.end()); //遍历显示 for (it = d1.begin(); it != d1.end(); it++) cout << *it << " "; // 输出:8 9 9 9 2 4 5 cout << endl; return 0; }
删除函数
d1.pop_front();//头部删除元素 d1.pop_back();//末尾删除元素 d1.erase(iterator it);//任意位置删除一个元素 d1.erase(iterator first, iterator last);//删除[first,last] 之间的元素 d1.clear();//清空所有元素:
访问函数
下标访问:deq[1]; // 并不会检查是否越界
at 方法访问:deq.at(1); // 以上两者的区别就是 at 会检查是否越界,是则抛出 out of range 异常
访问第一个元素:deq.front();
访问最后一个元素:deq.back();
大小函数
d.size();//容器大小 d.max_size();//容器最大容量 d.resize();//更改容器大小 deq.empty();//容器判空 deq.shrink_to_fit();//减少容器大小到满足元素所占存储空间的大小
其他函数
deq.assign(int nSize, const T& x); //多个元素赋值 // 类似于初始化时用数组进行赋值 swap(deque&);//交换两个同类型容器的元素
案例:
#include <iostream> #include <deque> using namespace std; int main(){ // 多个元素赋值 deque<int> d1; d1.assign(3, 1); deque<int> d2; d2.assign(3, 2); // 交换两个容器的元素 d1.swap(d2); // 遍历显示 cout << "d1: "; for (int i = 0; i < d1.size(); i++) cout << d1[i] << " "; // 输出:2 2 2 cout << endl; // 遍历显示 cout << "d2: "; for (int i = 0; i < d2.size(); i++) cout << d2[i] << " "; // 输出:1 1 1 cout << endl; return 0; }
list容器
list是一种序列式容器。list容器完成的功能实际上和数据结构中的双向链表是极其相似的,list中的数据元素是通过链表指针串连成逻辑意义上的线性表,也就是list也具有链表的主要优点,即:在链表的任一位置进行元素的插入、删除操作都是快速的。
头文件
#include<list>
初始化
list<int> l1; //创建一个空链表 list<int> l2(10); //创建一个链表其有10个空元素 list<int> l3(5,20); //创建一个链表其有5个元素内容为20 list<int> l4(l3.begin(),l3.end()); //创建一个链表其内容为l3的内容 list<int> l5(l4); //创建一个链表其内容为l4的内容
迭代器
遍历元素:
list<int> li={1,2,3,4,5,6}; for(list<int>::iterator it=li.begin();it!=li.end();it++){ cout<<*it<<' '; }
也可以使用auto
常用函数
empty():返回一个bool类型的值,只存在真和假,当链表为空时为真,不为空时为假
size():返回链表元素的个数
链表前插入push_front():表示在链表最前端插入一个数据
删除pop_front():表示在链表最前端删除一个数据
链表后插入push_back():表示在链表尾插入一个数据
删除pop_back():表示将链表尾删除一个数据
插入insert():插入元素到指定位置,通过在元素之前在指定位置插入新元素来扩展向量,从而有效地增加容器大小所插入的元素数量。
//插入单一数据到指定位置 iterator insert (iterator position, const value_type& val); //插入一段数据到指定位置 void insert (iterator position, size_type n, const value_type& val); //插入一段别的容器的数据到指定位置 template <class InputIterator> void insert (iterator position, InputIterator first, InputIterator last); //案例 li.insert(li.begin(),100); //在链表最前端插入数据100 li.insert(li.begin(),3,200); //在链表最前端插入3个数据内容为200 list<int> k(2,50); //创建一个新的链表k,其拥有2个元素内容均为50 li.insert(li.begin(),li.begin(),li.end()); //在链表v最前端插入链表上K的全部内容
erase():删除一个元素,或者是一段区间的元素,将会自动缩减空间使用。
iterator erase (iterator position); iterator erase (iterator first, iterator last); //案例 li.erase(li.begin()); //删除 li.erase(li.begin(),li.begin()+4); //删除前4个元素
排序sort():让整个链表变成升序状态,或者变成自定义的排序状态
template <class Compare> void sort (Compare comp); //案例 #include<iostream> #include<list> using namespace std; int cmp(const int &a,const int &b){ return a>b;//简单的自定义降序序列 } int main(){ list<int> li; //创建一个空链表 for(int i=10;i>=6;i--){ li.push_back(i); } li.push_front(3); li.push_back(20); list<int> li2(li); for(list<int>::iterator it=li.begin();it!=li.end();it++){ cout<<*it<<' '; } cout<<endl; //排序前3 10 9 8 7 6 20// li.sort(); for(list<int>::iterator it=li.begin();it!=li.end();it++){ cout<<*it<<' '; } cout<<endl; //默认排序后3 6 7 8 9 10 20// li2.sort(cmp); for(list<int>::iterator it=li2.begin();it!=li2.end();it++){ cout<<*it<<' '; } cout<<endl; //自定义排序后20 10 9 8 7 6 3// return 0; }
reverse():
相对于自定义的降序方法,STL提供了一个默认的降序方法reverse(),类似于sort一样直接使用即可。
函数列表
Lst1.assign() 给list赋值 Lst1.back() 返回最后一个元素 Lst1.begin() 返回指向第一个元素的迭代器 Lst1.clear() 删除所有元素 Lst1.empty() 如果list是空的则返回true Lst1.end() 返回末尾的迭代器 Lst1.erase() 删除一个元素 Lst1.front() 返回第一个元素 Lst1.get_allocator() 返回list的配置器 Lst1.insert() 插入一个元素到list中 Lst1.max_size() 返回list能容纳的最大元素数量 Lst1.merge() 合并两个list Lst1.pop_back() 删除最后一个元素 Lst1.pop_front() 删除第一个元素 Lst1.push_back() 在list的末尾添加一个元素 Lst1.push_front() 在list的头部添加一个元素 Lst1.rbegin() 返回指向第一个元素的逆向迭代器 Lst1.remove() 从list删除元素 Lst1.remove_if() 按指定条件删除元素 Lst1.rend() 指向list末尾的逆向迭代器 Lst1.resize() 改变list的大小 Lst1.reverse() 把list的元素倒转 Lst1.size() 返回list中的元素个数 Lst1.sort() 给list排序 Lst1.splice() 合并两个list Lst1.swap() 交换两个list Lst1.unique() 删除list中重复的元素
set/multiset容器
set/multiset属于关联式容器,底层结构使用二叉树实现的。
set/multiset的特点是:所有的元素在插入时会自动被排序。
而set与multiset容器的区别就是:set容器中不允许有重复的元素,而multiset允许容器中有重复的元素。
构造和赋值
set<T> st 默认构造函数 set(const set &st) 拷贝构造函数 set& operator=(const set &st) 重载等号操作符
插入与删除
insert(elem) 在容器中插入元素 clear() 清除所有元素 erase(pos) 删除pos迭代器所指的元素,返回下一个元素的迭代器 erase(beg,end) 删除区间[beg,end)的所有元素,返回下一个元素的迭代器 erase(elem) 删除容器中值为elem的元素
大小与交换
size() 返回容器中元素的数目 empty() 判断容器是否为空 swap(st) 交换两个集合容器
查找与统计
find(key) 查找key是否存在,若存在返回该键的元素的迭代器;若不存在,返回set.end() count(key) 统计key的元素个数
案例:
#include<iostream> #include <set> using namespace std; //set容器的查找与统计 int main() { set<int> s1; //插入数据 s1.insert(20); s1.insert(30); s1.insert(10); s1.insert(40); //查找 set<int>::iterator pos = s1.find(30); if (pos != s1.end()) {//找到元素 cout << "找到该元素:" << *pos << endl; } else { cout << "未找到该元素" << endl; } //统计 //这里需要注意set容器不予许出现重复的元素 //因此count返回的值只能为0或者1 //统计30的个数 s1.insert(30); s1.insert(30); int num = s1.count(30); cout << "30的个数为:" << num << endl; //1 return 0; }
set与multiset容器的区别
- 1.Multiset是set集合容器的一种,其拥有set的全部内容,在此基础之上,multiset还具备了可以重复保存元素的功能,因此会有略微和set的差别。
- 2.Multise容器在执行insert()时,只要数据不是非法数据和空数据,insert就总是能够执行,无论时一个数据还是一段数据。
- 3.Multiset容器中的find()函数回返回和参数匹配的第一个元素的迭代器,即时存在多个元素也只是返回第一个,如{10,20,20,20}搜索20进行匹配将会返回第二个参数,如果没有符合的参数则结束迭代器。
- 4.同理诸如lower_bound()等的需要进行一个位置的返回值,则统统返回第一个发现的值。
map/multimap容器
map容器中所有元素都是pair,pair中第一个元素为key(键值),起到索引作用,第二个元素为value(实值)。
同时,所有元素都会根据元素的键值自动排序。
map/multimap属于关联式容器,底层数据结构是用二叉树实现的。它的优点就是可以根据key值快速找到value值。
这里需要了解map与multimap的区别:
即map不予许容器中有重复的key值元素;而multimap允许容器中有重复的key值元素,这里的区别与set与multiset十分类似。
Pair对组
pair只含有两个元素,可以看作是只有两个元素的结构体。对于成对出现的数据,利用对组可以返回两个数据。
应用:
- 代替二元结构体
- 作为map键值对进行插入
- 在创建pair对象时,必须提供两个类型名,两个对应的类型名的类型不必相同,可以在定义时进行成员初始化。
头文件:
#include<utility>
vs里面,某些编译器可以不声明这个头文件而直接使用,貌似在C++中,pair被放入了std命名空间中了。
格式为:
template <class T1, class T2> struct pair;
在现实情况中我们可以像类似于STL创建新容器一样创建pair也可以直接使用,如下:
pair<int,int> p; pair<int,int> p(10,20);
或者是
map<char,int> m; m.insert(pair<char,int>('a',10));
Pair数据访问
//数据类型 pair<string, int>p("公孙离", 17); cout << "姓名:" << p.first << " 年岁:" << p.second << endl; //和结构体类似,first代表第一个元素,second代表第二个元素 pair<char, float>p1=make_pair(‘p’,3.14); cout << "字符:" << p1.first << " 小数:" << p1.second << endl;
make_pair
函数原型template pair make_pair(T1 a, T2 b) { return pair(a, b); }
可以通过make_pair生成我们的所需要的pair,对于一般的pair而言,如果需要对其进行赋值,则需要
pair<int,int> p; p.first=10,p.second=20;
但如果使用make_pair方法,则可以变成如下内容:
pair<int,int> p; p=make_pair(10,20);
可以看见,使用make_pair不仅仅让我们免去了对两个变量进行分开来的访问赋值,同时make_pair也智能的接受变量的类型,不需要再度指定,也就是说,make_pair本身是接受隐式类型转换的,比如定义的是一个int类型,使用make_pair传入一个float类型的参数,make_pair不会报错,而是回自动的进行一个类型转换,将float变为int,这样可以获得更高的灵活度,同时也会有一些小问题。
构造与赋值
map<T,T> mmap 默认构造函数 map(const map &mp) 拷贝构造函数 map& operator=(const map &mp) 重载等号操作符
案例:
#include<iostream> #include<map> using namespace std; //map容器的构造与赋值 void printMap(map<int, int>& m) { for (auto it = m.begin(); it != m.end(); it++) { cout << "key =" << it->first << " value =" << it->second << endl; } cout << endl; } int main() { //创建map容器 map<int, int> m; //插入数据里面需要传入的是对组 m.insert(pair<int, int>(1, 10));//pair<int, int>(1, 10)为匿名二元组 m.insert(pair<int, int>(3, 30)); m.insert(pair<int, int>(4, 40)); m.insert(pair<int, int>(2, 20)); //插入元素后会根据key自动进行升序排列 printMap(m); //拷贝构造 map<int, int> m2(m); printMap(m2); //赋值 map<int, int> m3; m3 = m2; printMap(m3); return 0; }
大小与交换
size() 返回容器中元素的数目 empty() 判断容器中是否为空 swap(st) 交换两个集合容器
插入与删除
insert(elem) 在容器中插入元素 clear() 清除所有元素 erase(pos) 删除pos迭代器所指的元素,返回下一个元素的迭代器 erase(beg,end) 删除区间[beg,end)的所有元素,返回下一个元素的迭代器 erase(key) 删除容器中值为key的元素
案例:
#include<iostream> #include <map> using namespace std; int main() { map<int, int> m; m.insert(pair<int, int>(1, 10));//插入第一种 m.insert(make_pair(2, 20));//插入第二种 m.insert(map<int, int>::value_type(3, 30));//插入第三种不建议使用 //插入第四种最简单 //[]不建议插入通过[]可以利用key访问到value //使用[]插入元素的时候,如果key不存在将会自动创建键值对 m[4] = 40; printMap(m); m.erase(m.begin());//删除 printMap(m); m.erase(3);//删除直接传入key printMap(m); //全部删除 m.clear();//相当于m.erase(m.begin(),m.end()) printMap(m); return 0; }
查找与统计
find(key) 查找key是否存在,返回该键的元素的迭代器;若不存在返回map.end() count(key) 统计key的元素的个数
案例:
#include<iostream> #include<map> using namespace std; int main() { //查找 map<int, int> m; m.insert(pair<int, int>(1, 10)); m.insert(pair<int, int>(3, 30)); m.insert(pair<int, int>(2, 20)); //查找键为3的键值对 map<int,int>::iterator pos=m.find(3); if (pos != m.end()) { cout << "查到了元素key=" << pos->first << " value=" << pos->second << endl; } else { cout << "未找到元素" << endl; } //统计 //由于map容器中key不能重复出现因此count统计的结果只有0或1 int num=m.count(3);//返回结果为整型 cout << "num=" << num << endl; return 0; }
Multimap容器
Multimap时map映射容器的一种,其拥有map的全部内容,并在此基础之上,multimap还具有了可以重复保存元素的功能,与上文的mutliset差不多,任何进行访问单个值得语句访问均只会返回第一个位置,这里不再多说,而是举一个实际中可能用得到得例子。
有没有一种方法,使得一个key值能够对应多个value,产生一种诸如一个学生有多门考试成绩一样的映射。
我们都知道map关联容器是使得一个数据与另一个数据发生映射的容器,通过key得到value产生一一对应,那么multimap在此基础上使得map元素可以重复,因此这种情况可以使用multimap。