C++之STL用法

C++ STL模板包含了很多数据结构和算法,刷题中经常也会用到,本文介绍了STL里面的容器部分。看了很多牛人的博客之后,感觉自己对STL的理解还是比较浅显的,特此重新更新了一章,STL内部数据结构来说明STL中使用的数据结构。


STL容器

  • 顺序容器
    • vector:尾端插入元素有较高性能,动态数组实现;
    • deque:首尾插入元素都有较高性能,动态数据实现;
    • list:可以常数时间在任何地方插入元素,链表实现;
  • 关联容器
    • set:不同元素的集合,平衡二叉树实现,检索时间是O(long(N))
    • multiset:同上,可以包含相同元数据;
    • map:同set,但存放的是键值对
    • mutimap:同上,键可以重复
  • 容器适配器:stack,queue,priority_queue

vector

特点:

将一个元素置于一个动态数组中加以管理,可以随机存取元素。在数组尾部添加或删除元素非常快速,但是在中部或头部插入或删除元素比较耗时。

方法:

方法 说明
push_back 在数组的最后添加一个数据, 示例: c.push_back(5);
pop_back 去掉数组的最后一个数据, 示例:c.pop_back();
at 得到编号位置的数据, 示例: int d = c.at(0);
begin 得到数组头的指针, 示例: vector::iterator it = c.begin();
end 得到数组的最后一个单元+1的指针, 示例: vector::iterator it = c.end();
front 得到数组头的引用, 示例: int first = c.front();
back 得到数组的最后一个单元的引用, 示例: int last = c.back();
max_size 得到vector最大可以是多大
capacity 当前vector分配的大小
size 当前使用数据的大小
resize 改变当前使用数据的大小,如果它比当前使用的大,则填充默认值
reserve 改变当前vecotr所分配空间的大小
erase 删除指针指向的数据项
clear 清空当前的vector
rbegin 将vector反转后的开始指针返回(其实就是原来的end-1)
rend 将vector反转后的结束指针返回(其实就是原来的begin-1)
empty 判断vector是否为空
swap 与另一个vector交换数据

使用示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class VectorTest {
public:
void Test() {
// 初始化
vector<int> v1;
vector<int> v2(10, 6);
vector<int> v3(v2.begin(), v2.end());
print(v1);
print(v2);
print(v3);
// 插入数据
v1.push_back(1);
v1.push_back(2);
v1.insert(v1.begin(), 3);
v1.insert(v1.begin()+1, v2.begin(), v2.end());
print(v1);
// 赋值函数
cout << "capacity:" << v2.capacity() << endl;
v2.assign(8, 1);
cout << "capacity:" << v2.capacity() << endl;
print(v2);
// 引用函数
cout << v3.front() << endl;
cout << v3.back() << endl;
v3.at(4) = 5;
cout << v3.at(4) << endl;
// 移出和删除
v1.pop_back();
v1.erase(v1.begin()+1);
print(v1);
// 大小
cout << "capacity: " << v1.capacity() << endl;
cout << "size: " << v1.size() << endl;
cout << "max_size: " << v1.max_size() << endl;
v1.clear();
cout << "after clear" << endl;
cout << "capacity: " << v1.capacity() << endl;
cout << "size: " << v1.size() << endl;
cout << "max_size: " << v1.max_size() << endl;
// 强制清除v1内存
vector<int>().swap(v1);
cout << "capacity: " << v1.capacity() << endl;
cout << "size: " << v1.size() << endl;
cout << "max_size: " << v1.max_size() << endl;
}
void print(vector<int> vi) {
for (vector<int>::iterator it = vi.begin(); it != vi.end(); ++it)
cout << *it << " ";
cout << endl;
}
};

运行结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
6 6 6 6 6 6 6 6 6 6
6 6 6 6 6 6 6 6 6 6
3 6 6 6 6 6 6 6 6 6 6 1 2
capacity:10
capacity:10
1 1 1 1 1 1 1 1
6
6
5
3 6 6 6 6 6 6 6 6 6 1
capacity: 13
size: 11
max_size: 1073741823
after clear
capacity: 13
size: 0
max_size: 1073741823
capacity: 0
size: 0
max_size: 1073741823


deque

特点:

“double-ended queue” 双端队列,可以随机存取。数组尾部或头部添加或删除元素非常快速,但在中部插入或删除元素比较费时。

  • 随机访问方便,即支持 [ ] 操作符和vector.at() ,但性能没有vector 好;
  • 可以在内部进行插入和删除操作,但性能不及list ;
  • 可以在两端进行push 、pop ;
  • 相对于verctor 占用更多的内存。

方法:

相同于vector,新增了push_front和pop_front方法

方法 说明
push_front 在头部加入一个元素
pop_front 删除头部元素

使用示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class DequeTest {
public:
void Test() {
// 初始化
deque<int> d1;
deque<int> d2(20, 1);
deque<int> d3(d2);
deque<int> d4(d3.begin(), d3.end());
print(d1);
print(d2);
print(d3);
print(d4);
// 插入
d1.push_back(5);
d1.push_back(7);
d1.push_front(6);
print(d1);
// 查找
const int findnum = 6;
auto pos = find(d1.begin(), d1.end(), findnum);
if (pos != d1.end())
printf("find %d success\n", findnum);
else
printf("find failed\n");
// 删除
d1.pop_back();
d1.pop_front();
print(d1);
}
void print(const deque<int> di) const {
for (deque<int>::const_iterator cit = di.cbegin(); cit != di.cend(); ++cit)
cout << *cit << " ";
cout << endl;
}
};

运行结果:

1
2
3
4
5
6
7
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
6 5 7
find 6 success
5


list

特点:

双向链表,不提供随机存取(按顺序存储),在任何位置插入或删除动作都非常迅速。只能顺序访问(从前向后或者从后向前)。与前面两种容器类有一个明显的区别就是:它不支持随机访问。要访问表中某个下标处的项需要从表头或表尾处(接近该下标的一端)开始循环。而且缺少下标预算符:operator[]。

方法:

方法 说明
merge 合并两个list
remove_if 按条件删除元素
sort 给list排序
splice 合并两个list,源list的内容部分或全部元素删除,拼插入到目的list
unique 删除list中重复的元素

使用示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class ListTest {
public:
void Test() {
list<int> l1;
list<int> l2(5);
list<int> l3(2,3);
list<int> l4(l3.begin(), l3.end());
print(l1);
print(l2);
print(l3);
print(l4);
// 插入
l1.push_back(5);
l1.push_front(6);
l1.push_back(7);
print(l1);
// 累加算法
int result = accumulate(l1.begin(), l1.end(), 0);
cout << "sum = " << result << endl;
// 求最大值
auto max_num = max_element(l1.begin(), l1.end());
cout << "the maximum element in l1 is " << *max_num << endl;
}
void print(const list<int> &li) const {
for (list<int>::const_iterator cit = li.cbegin(); cit != li.cend();
++cit)
cout << *cit << " ";
cout << endl;
}
};

运行结果:

1
2
3
4
5
6
7
0 0 0 0 0
3 3
3 3
6 5 7
sum = 18
the maximum element in l1 is 7


map

特点:

Map的元素是成对的键值/实值,内部的元素依据其值自动排序,Map内的相同数值的元素只能出现一次,map就是一个容器,里面装的就是若干个pair。每个pair的第一个元素,称为键(注意键的类型必须支持小于(<)操作),第二个元素,称为值。对于普通的map,每个键都对应一个值。这样的看起来,键类似于数组的下标,而值类似于数组的值。map类定义了3种类型,分别为key_type、mapped_type以及vaule_type。他们分别表示了键的类型、值的类型,以及一个pair类型,pair的第一个元素是键,第二个元素是值。

方法:

方法 说明
at 取出对应键值的元素
count 返回指定键值的元素个数,在map中只能是0或者1
find 如果k在m中的键值存在则返回相应的迭代器,否则返回超出来末端迭代器

使用示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class MapTest {
public:
void Test() {
map<string, int> m1;
// 插入
m1["Peter"] = 1;
m1["Alice"] = 3;
m1.insert(map<string, int>::value_type("Bob", 2));
print(m1);
// 查找
auto it = m1.find("Bob");
if (it != m1.end())
cout << "find success " << endl;
else
cout << "find failed" << endl;
// 统计
int result = m1.count("Bob");
cout << "result: " << result << endl;
// 删除
int ret = m1.erase("Bob");
if (ret)
cout << "remove success" << endl;
else
cout << "can't find" << endl;
auto iter = m1.erase(m1.begin());
print(m1);
}
void print(const map<string, int> &m) const {
for (map<string, int>::const_iterator cit = m.cbegin(); cit != m.cend();
++cit)
cout << (*cit).first << ":" << (*cit).second << endl;
}
};

运行结果:

1
2
3
4
5
6
7
Alice:3
Bob:2
Peter:1
find success
result: 1
remove success
Peter:1


set

特点:

set只有键,没有值,所以他的vaule_type不是pair类型,而是key_type类型。同样的,它也支持insert、find、count操作。map比较适合于储存键值对应的情况,而set适合于储存键,判断键在不在这个集合中,比如黑名单之类的。

方法:

和map一样

使用示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class SetTest {
public:
void Test() {
// 初始化
set<string> s;
// 插入
s.insert("Peter");
s.insert("Bob");
pair<set<string>::iterator,bool> ret = s.insert("Peter");
if (ret.second)
cout << "insert success" << endl;
else
cout << "the word exists" << endl;
print(s);
// 查找
set<string>::iterator iter = s.find("Bob");
if (iter != s.end())
cout << "find success" << endl;
else
cout << "failed find" << endl;
// 统计
int result = s.count("Peter");
cout << "result" << result << endl;
}
void print(const set<string> &s) const {
for (set<string>::const_iterator cit = s.begin(); cit != s.end();
++cit)
cout << *cit << " ";
cout << endl;
}
};

运行结果:

1
2
3
4
the word exists
Bob Peter
find success
result1


multimap

使用方法同map


multiset

使用方法同set


stack

特点:

可以使用三种顺序容器vector、deque(默认)中的任何一个作为stack的底层模型

方法:

方法 说明
empty 判断栈是否为空
pust 压入一个数据
pop 弹出一个数据
size 返回栈的长度
top 得到栈顶数据

使用示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class StackTest {
public:
void Test() {
// 初始化
stack<int> sDeque;
stack<int, vector<int>> sVector;
// push
for (int i=0; i<10; ++i)
sDeque.push(i);
// pop
while (!sDeque.empty()) {
cout << sDeque.top() << " ";
sDeque.pop();
}
cout << endl;
}
};

运行结果:

1
9 8 7 6 5 4 3 2 1 0


queue

特点:

可以使用deque(默认)或vector作为底层容器

方法:

方法 说明
push 将一个元素输入放到队列
pop 取出一个元素
back 队尾元素
front 队头元素
size 队列长度
empty 判断队列是否为空

使用示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class QueueTest {
public:
void Test() {
queue<int> q;
queue<int, vector<int>> qVector;
// push
for (int i=0; i<10; ++i)
q.push(i);
// back & front
cout << "back: " << q.back() << endl;
cout << "front: " << q.front() << endl;
// pop
while (!q.empty()) {
cout << q.front() << " ";
q.pop();
}
cout << endl;
}
};

运行结果:

1
2
3
back: 9
front: 0
0 1 2 3 4 5 6 7 8 9


priority_queue

特点:

priority_queue也是一个队列,其元素按有序顺序排列。其不采用严格的 FIFO 顺序,给定时刻位于队头的元素正是有最高优先级的元素。如果两个元素有相同的优先级,那么它们在队列中的顺序就遵循FIFO语义。默认适配的底层容器是vector,也可以使用deque,list不能用,因为priority_queue要求能对元素随机访问以便进行排序。

方法:

方法 说明
push 将一个元素输入放到队列
pop 取出一个元素
top 取出优先级最大或最少的元素
empty 判断队列是否为空

使用示例:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class PriorityQueueTest {
public:
struct cmp {
bool operator() (int &a, int &b) {
return a > b;
}
};
struct Node {
bool operator< (Node &a, Node &b) {
if (a.priority == b.priority) return a.val < b.val;
return a.priority < b.priority;
}
int priority;
int val;
};
void Test() {
priority_queue<int> maxHeap;
priority_queue<int, deque<int>, cmp> minHeap;
priority_queue<Node> NodeHeap;
// push
for (int i=0; i<10; ++i) {
maxHeap.push(i);
minHeap.push(i);
}
// pop
while (!maxHeap.empty()) {
cout << maxHeap.top() << " ";
maxHeap.pop();
}
cout << endl;
while (!minHeap.empty()) {
cout << minHeap.top() << " ";
minHeap.pop();
}
cout << endl;
}
};

运行结果:

1
2
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9


参考资料:
C++ STL简单介绍
C++ STL详解之容器
C++ STL详解之适配器