熟悉容器的使用是掌握STL的基本步骤。
许多容器都支持empty()、size()、front()、back()、begin()、end()等方法,这是因为算法进行了封装。
1. 序列式容器
序列容器以线性序列的方式存储元素。元素在序列中的顺序与存储的顺序相同,没有对元素进行排序。
vector的基本用法
长度可变序列,但只能在序列的末尾高效地增加或删除元素。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16vector<类型>T; //构建
T.push_back(x); //尾部新增一个元素x
T.insert(iterator it, int x); //在it指向的元素前新增一个x
T.insert(iterator it, int n, int x); //在it指向元素前插入n个x
T.erase(iterator it); //删除it指向的元素
T.erase(iterator first, iterator last); //删除[last,first)中元素
T.pop_back(); //删除最后一个元素
T.empty(); //判断是否为空
T.size(); //返回元素个数
T.at(index); //返回index编号元素
reverse(T.begin(), T.end()); //反转T中元素
T.begin(); //返回首元素指针
T.end(); //返回最后一个元素+1的指针
T.front(); //返回首元素引用
T.back(); //返回尾元素引用
sort(T.begin(), T.end()); //排序deque的基本用法
以双端队列形式组织元素,在尾部和头部插入删除迅速,在中间插入删除元素则比较费时,因为必须移动中间其它元素。1
2
3
4
5
6
7
8
9
10
11
12
13deque<类型>T; //声明一个双端队列
deque<类型>T(size,value); //声明具有size个value默认值的双端队列
T.push_front(x); //在头部插入x
T.push_back(x); //在尾部插入x
T.pop_front(); //弹出头部的一个元素
T.pop_back(); //弹出尾部的一个元素
T.front(); //返回第一个元素的引用
T.back(); //返回最后一个元素的引用
T.begin();
T.end();
T.size();
T.at(index);
T.insert(it, x);list的基本用法
list实现的是双向链表,与vector比它允许快速的插入和删除,但随机访问比较慢。1
2
3
4
5
6
7
8
9
10
11
12
13list<类型>T; // 构建
T.push_back(x);
T.push_front(x);
T.pop_back();
T.pop_front();
T.front();
T.back();
T.begin();
T.reverse();
T.sort();
T.end();
T.insert(x);
T.remove(x);
2. 关联式容器
- map的基本用法
map是关联容器的一种,通过键值对来存储。map内部自建一颗红黑树(平衡二叉树),这棵树具有对数据的自动排序功能(按照键值排序,当键值是不可比较元素时需指定比较仿函数)。
map容器有4中,每一种都由类模板定义,因为修改键会扰乱容器中元素的顺序,每种map容器模板都有不同的特性:
- map:唯一<key,value>对应,默认按键值从小到大排序。
- mutlimap:允许使用重复的键。
- unordered_map:元素的顺序并不是直接由键值确定的,而是由键值的哈希值决定的。
- unordered_multimap:通过哈希值确定对象的位置,允许有重复的键。
1
2
3
4
5
6
7
8
9map< int,string > T; //构建
T.insert(make_pair<int,string>(1, "student_one")); //插入
T.empty();
T.size();
T.erase(key); //根据key删除,返回删除元素的数量
T.erase(iterator it); //删除迭代器指向位置的键值对,并返回指向下一个元素的迭代器
T.at(key); // 根据key获取对应value值
T.find(key); //返回指向键值key的迭代器指针
T.count(key);
2.mutlimap的基本用法
mutlimap容器保存的是有序的键值对,键值可以重复。
1 | //操作与map类似 |
3.set的基本用法
set搜索、移除、插入都是对数复杂度,以红黑树实现。set内的元素会被自动排序,set中的元素即是键值又是实值,set不允许两个元素有相同的值。不能通过set的迭代器去修改set元素,当对容器中的元素进行插入或删除时,操作之前的所有迭代器在操作之后依然有效。
定义set容器的模板如下:
- set: 容器保存 T 类型的对象,而且保存的对象是唯一的。其中保存的元素是有序的,默认用 less
对象比较。 - multiset:容器保存 T 类型对象的方式相同,但它可以保存重复的对象。
- unordered_set:容器保存 T 类型的对象,而且对象是唯一的。元素在容器中的位置由元素的哈希值决定。
- unordered_mutliset:容器保存 T 类型对象的方式和 unorderd_set 相同,但它可以保存重复的对象。
1
2
3
4
5set<类型>T; //构建
T.insert(x);
T.count(x);
T.find(x);
T.erase(x);
4.mutliset的基本用法
1 | //操作与set类似 |
3. 容器适配器
stack的基本用法
实现类似于栈的功能(后进先出):1
2
3
4
5
6stack <类型> T; //构建
T.empty();
T.push(item);
T.pop();
x = T.top();
int size = T.size();queue的基本用法
实现类似于队列的功能(先进先出):1
2
3
4
5
6
7queue <类型> T; //构建
T.push(item); //push到队列尾部
T.pop(); //弹出队首
x = T.front();
y = T.back();
T.size();
T.empty();prority_queue的基本用法
priority_queue 容器适配器定义了一个元素有序排列的队列。默认队列头部的元素优先级最高。它和queue不同的是我们可以自定义其中数据的优先级,让优先级高的排在队列前面,优先出队。
但是如何定义“优先级”完全取决于我们自己。如果一个优先级队列记录的是医院里等待接受急救的病人,那么病人病情的严重性就是优先级。如果队列元素是银行的借贷业务,那么借记可能会优先于信贷。1
2
3
4
5
6
7
8prority_queue <类型> T; //构建
priority_queue <int,vector<int>,greater<int> > q; //升序序列
priority_queue <int,vector<int>,less<int> > q; //降序序列
T.push(x); //按优先级push到合适位置
T.pop();
T.top();
T.size();
T.empty();