vector容器
C++ STL vector
是一个动态数组容器，它可以在运行时调整大小，并且支持随机访问。以下是
vector 常用的基本操作：
创建vector
1
2
3
4
5
6
7
8
| #include <vector>
std::vector<int> v;
std::vector<int> v(size);
std::vector<int> v(size, value);
std::vector<int> v2(v1);
std::vector<int> v3 = {1,2,3};
std::vector<int> v4(v3.begin() + 1, ilist.end() - 1);
|
访问 vector 元素
1
2
3
4
5
| v[index];
v.at(index);
v.front();
v.back();
v.data();
|
修改 vector 元素
1
2
3
4
5
6
7
8
9
| v[index] = value;
v.at(index) = value;
v.emplace_back(value);
v.pop_back();
v.insert(iterator, value);
v.erase(iterator);
v.clear();
v.resize(size);
v.resize(size, value);
|
vector 容量操作
1
2
3
4
5
| v.size();
v.capacity();
v.empty();
v.reserve(capacity);
v.shrink_to_fit();
|
vector 遍历操作
1
2
3
4
5
6
7
8
9
10
11
| for (auto it = v.begin(); it != v.end(); it++) {
std::cout << *it << " ";
}
for (auto x : v) {
std::cout << x << " ";
}
std::for_each(v.begin(), v.end(), [](int x) {
std::cout << x << " ";
});
|
两个元素之间的范围
我们知道，作用于同一容器的 2
个同类型迭代器可以有效指定一个区间范围。在此基础上，如果想获取该指定范围内包含元素的个数，就可以借助
distance() 函数。
distance()
函数用于计算两个迭代器表示的范围内包含元素的个数，其语法格式如下：
1
2
| template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type distance (InputIterator first, InputIterator last);
|
其中，first 和 last
都为迭代器，其类型可以是输入迭代器、前向迭代器、双向迭代器以及随机访问迭代器；该函数会返回[first,
last)范围内包含的元素的个数。
例子：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| #include <iostream>
#include <iterator>
#include <list>
using namespace std;
list<int> mylist;
for (int i = 0; i < 10; i++) {
mylist.push_back(i);
}
list<int>::iterator first = mylist.begin();
list<int>::iterator last = mylist.end();
cout << "distance() = " << distance(first, last);
|
查找某个值所在位置
使用 std::find()方法，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <iostream>
#include <vector>
#include <algorithm>
int main()
{
std::vector<int> v = { 7, 3, 6, 2, 6 };
int key = 6;
std::vector<int>::iterator itr = std::find(v.begin(), v.end(), key);
if (itr != v.cend()) {
std::cout << "Element present at index " << std::distance(v.begin(), itr);
}
else {
std::cout << "Element not found";
}
return 0;
}
|
查找最大元素和最小元素
max_element()函数是算法标头的库函数，用于查找范围中的最大元素，它接受容器范围[start，end]，并返回一个迭代器，该迭代器指向给定范围中具有最大值的元素。
参数：
- iterator start, iterator end,容器开始和结束位置;
- [compare comp]，可选参数，可以与给定范围内的元素进行比较。
返回值:
iterator -
返回一个迭代器，该迭代器指向给定范围内具有最大值的元素。
min_element()同理，参数用法也相同，不同的是它返回的是最小元素的迭代器。
stack容器
C++ STL 标准库中的 stack
是一个后进先出（LIFO）的容器适配器，它可以使用不同的底层容器（默认使用
deque）实现。以下是 stack 常用的基本操作：
创建 stack
1
2
3
4
5
| #include <stack>
std::stack<int> s;
std::stack<int> s1(s);
std::stack<int, std::vector<int>> s2;
|
stack 元素操作
1
2
3
4
5
| s.emplace(value);
s.pop();
s.top();
s.empty();
s.size();
|
遍历 stack
stack 是不支持迭代器的容器，因此我们只能通过弹出元素的方式遍历
stack。
1
2
3
4
5
6
| while (!s.empty())
{
int x = s.top();
s.pop();
std::cout << x << " ";
}
|
注意：在遍历 stack 时，一定要判断 stack 是否为空，否则会发生
undefined behavior。
queue容器
C++ STL 标准库中的 queue
是一个先进先出（FIFO）的容器适配器，它也可以使用不同的底层容器（默认使用
deque）实现。以下是 queue 常用的基本操作：
创建 queue
1
2
3
4
5
| #include <queue>
std::queue<int> q;
std::queue<int> q1(q);
std::queue<int, std::list<int>> q2;
|
queue 元素操作
1
2
3
4
5
6
| q.emplace(value);
q.pop();
q.front();
q.back();
q.empty();
q.size();
|
遍历 queue
queue 是不支持迭代器的容器，因此我们只能通过弹出元素的方式遍历
queue。
1
2
3
4
5
6
| while (!q.empty())
{
int x = q.front();
q.pop();
std::cout << x << " ";
}
|
注意：在遍历 queue 时，一定要判断 queue 是否为空，否则会发生
undefined behavior。
unordered_map容器
unordered_map定义如下：
1
2
3
4
5
6
7
| template<class Key,
class Ty,
class Hash = std::hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<std::pair<const Key, Ty> > >
class unordered_map;
> class unordered_map
|
- 第1个参数:存储key值。
- 第2个参数:存储mapped value。
- 第3个参数:为哈希函数的函数对象。它将key作为参数，并利用函数对象中的哈希函数返回类型为size_t的唯一哈希值。默认值为std::hash<
key >。
- 第4个参数:为等比函数的函数对象。它内部通过等比操作符’=='来判断两个key是否相等，返回值为bool类型。默认值是std::equal_to<
key >。
基本操作
插入元素
一种插入的特殊情况是，unordered_map插入的值是int类型(key的类型无所谓)，这时候可以用第二种方式插入:
1
2
3
4
5
6
7
8
9
| int main(int argc, char const *argv[])
{
std::unordered_map<int, int> hash_map;
hash_map.insert({1, 1});
hash_map[0]++;
return 0;
}
|
删除元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int main(int argc, char const *argv[])
{
std::unordered_map<int, int> hash_map;
hash_map.insert({1, 1});
hash_map[0]++;
mymap.erase(mymap.begin());
mymap.erase(1);
mymap.clear();
return 0;
}
|
查找元素
1
2
3
4
5
6
7
8
9
10
11
12
13
| int main(int argc, char const *argv[])
{
std::unordered_map<int, int> hash_map;
hash_map.insert({1, 1});
hash_map[0]++;
if(hash_map.find(key) != hash_map.end())
std::cout<<"True"<<endl;
else
std::cout<<"False"<<endl;
return 0;
}
|
unordered_set容器
C++ STL 中的 unordered_set
是一个关联容器，它提供了一种存储唯一元素的无序集合。与 set
不同，unordered_set
内部的元素是无序的，因此在插入和查找时，它的性能通常比有序的关联容器 set
更快。
以下是一些 unordered_set 的基本用法示例：
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
| #include <iostream>
#include <unordered_set>
int main()
{
std::unordered_set<int> mySet;
mySet.insert(2);
mySet.insert(3);
mySet.insert(4);
auto it = mySet.find(3);
if (it != mySet.end())
std::cout << "Found " << *it << std::endl;
else
std::cout << "Not found" << std::endl;
if (mySet.count(4) > 0)
std::cout << "4 is in the set" << std::endl;
for (auto& element : mySet)
std::cout << element << std::endl;
return 0;
}
|
输出为:
1
2
3
4
5
| Found 3
4 is in the set
2
3
4
|
需要注意的是，在 unordered_set
中，元素的顺序是不确定的，因此输出的结果可能与上面的示例不完全一致。
STL中emplace和push的区别
在 C++ STL 标准库中，容器中的 emplace() 和
push()
都可以用来向容器中添加新元素。但是它们的底层实现和作用不同。
push()
push()
是一个成员函数，用于将一个已经构造好的元素加入到容器的尾部，即将元素的副本或引用添加到容器中。因此，需要将元素先构造出来，再将其加入容器中。例如：
1
2
| std::vector<int> v;
v.push_back(1);
|
这里的 push_back() 函数首先构造了一个 int
类型的元素，然后将其加入到了 vector 的尾部。
emplace()
emplace()
是一个可变参数模板函数，它在容器的尾部直接构造一个新的元素，而不需要将元素构造出来再加入容器。因此，它比
push() 更加高效。
例如，对于 vector 容器来说，下面的代码：
1
2
| std::vector<std::pair<int, double>> v;
v.emplace_back(1, 2.0);
|
将直接在 vector 的尾部构造一个 pair<int, double>
类型的元素，而不需要先构造一个 pair<int, double>
对象，然后再将其加入到 vector 中。
总结
emplace() 可以直接在容器中构造新的元素，而
push() 需要先将元素构造出来，再加入到容器中。emplace() 更加高效，因为它省去了元素构造的过程，而
push() 则需要先构造元素，再将其加入容器。