C++中的STL用法总结

C++中的STL用法总结

2 queue

3 priority_queue

优先队列（Priority Queue）是一种容器适配器，是在容器queue的基础上实现的。它能够在常数时间内查找最大（默认情况下）元素，插入和删除操作的时间复杂度为$O(logn)$。

3.1 优先级队列常用成员函数

  • push():
  • top(): 获取队列顶部元素；
  • pop(): 删除队列顶部元素；
  • size(): 获取优先级队列中元素个数；
  • empty():判断优先级队列是否为空。

示例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// 遍历优先级队列
template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}

std::priority_queue<int> q;
for(int n : {1,8,5,6,3,4,0,9,7,2}) {
    q.push(n);
}

std::priority_queue<int, std::vector<int>, std::greater<int> > q2;
for(int n : {1,8,5,6,3,4,0,9,7,2}) {
    q2.push(n);
}

4 stack

4.1 常用成员函数

  • top(): accesses the top element

  • empty(): checks whether the underlying container is empty

  • push(): inserts element at the top

  • emplace: constructs element in-place at the top

  • pop()：removes the top element

5 deque

6 array

7 list

8 forward_list

9 map系列

9.1 map

9.1.1 map功能说明

C++中的容器map是存放key,value键-值对的数据结构。内部的key唯一且会按照比较函数进行排序。特性如下：

  • key唯一
  • 内部数据有序
  • 内存数据结构：红黑树（平衡二叉树）
  • 迭代器按照key的升序顺序遍历数据

9.2 multimap

9.2.1 multimap功能说明

数据结构和map相同，区别在于内部的key可以重复。特性如下：

  • key可以重复
  • 内部数据有序
  • 内存数据结构：红黑树（平衡二叉树）
  • 迭代器按照key的升序顺序遍历数据，对于相同的键，按照插入顺序排列；

9.3 unordered_map

9.3.1 unordered_map功能说明

C++中的容器map是存放key,value键-值对的数据结构。内部的key唯一，但是不会对键值对进行排序；特性如下：

  • key唯一
  • 内部数据无序
  • 内部数据结构：哈希表

9.3.2 unordered_map常用接口函数

9.3.2.1 迭代方法
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// 方法1
std::unordered_map<int, std::string> mag = {{1, "foo"}, {3, "bar"}, {2, "baz"}};
for(auto iter = mag.begin(); iter != mag.end(); ++iter) {
    std::cout << "fisrt:" << item->first << ", second: " << item->second << std::endl;
}

// 方法2
for(auto item : mag) {
    std::cout << "fisrt:" << item->first << ", second: " << item->second << std::endl;
}
9.3.2.1 查找元素：find()
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// find()
// insert()
std::unordered_map<int,int> example;
auto item = example.find(2); // Finds an element with key equivalent to 2
if(item != example.end()) {
    std::cout << "Found element, fisrt:" << item->first << ", second: " << item->second << std::endl;
    item->second++;
} else {
    std::cout << "Not found element!" << std::endl;
    example[2] = 1;
}
9.3.2.2 更新map
1
2
3
4

std::unordered_map<std::string, size_t>  word_map;
for (const auto &w : { "this", "sentence", "is", "not", "a", "sentence", "this", "sentence", "is", "a", "hoax"}) {
    ++word_map[w];
}

9.4 unordered_multimap

9.4.1 unordered_multimap功能说明

数据结构和unordered_map相同，区别在于内部的key可以重复。特性如下：

  • key不唯一，但每个键关联的值可以不同。
  • 内部数据无序
  • 内部数据结构：哈希表

10 set系列

在C++标准模板库（STL）中，set、multiset、unordered_set和unordered_multiset是四种常用的关联容器。

10.1 set功能说明

C++中的set容器是一种关联容器，内部存储的是有序唯一的key。特性如下：

  • key唯一
  • 内部数据有序
  • 内部数据结构：红黑树（平衡二叉树）

10.2 multiset

10.2.1 multiset功能说明

C++中的multiset容器是一种关联容器，特性和set类似，唯一区别是可以存在重复的key。特性如下：

  • key不唯一
  • 内部数据有序
  • 内部数据结构：红黑树（平衡二叉树）

10.3 unordered_set

10.3.1 unordered_set功能说明

C++中的unordered_set容器是一种关联容器，内部存储的key唯一。特性如下：

  • key唯一
  • 内部数据无序
  • 内部数据结构：哈希表

10.3.2 unordered_set常用成员函数

  • empty()

  • size():

  • insert(): Inserts element(s) into the container, if the container doesn’t already contain an element with an equivalent key.

  • emplace(): Inserts a new element into the container constructed in-place with the given args if there is no element with the key in the container.

  • erase(): erases elements

  • find(): finds element with specific key

10.4 unordered_multiset

10.4.1 unordered_multiset功能说明

C++中的unordered_multiset容器是一种关联容器，内部存储的key唯一。特性如下：

  • key不唯一
  • 内部数据无序
  • 内部数据结构：哈希表