C++11 中 vector 的基本操作及使用注意事项_vector pop_front

C++ 中 vector 的基本操作及使用注意事项

1. 基本操作

1.1 初始化

// 括号
std::vector<int> a (5); //0,0,0,0,0
std::vector<int> b (5,1); //1,1,1,1,1

// 花括号
std::vector<int> c = {1,2,3,4,5,6};
std::vector<int> c {1,2,3,4,5,6}； // 和上面的写法等价
1
2
3
4
5
6
7

1.2 赋值

std::vector<int> foo (3,0);
std::vector<int> bar (5,0);

bar = foo; //Copies all the elements from foo into the bar.
1
2
3
4

1.3 内存

vector的内存也是连续的，可以和数组切换。

• 动态扩容

std::vector<int> a;
for (int i = 0; i < 1000; ++i)
{
    a.push_back(i);
    std::cout << "size: " << a.size() << " capacity: " << a.capacity() << std::endl;
}
1
2
3
4
5
6

• reserve

std::vector<int> a;
a.reserve(1000); // size: 0 capacity: 1000
1
2

扩充：

reserve 和 resize 的区别?

resize 会调用构造函数，而 reserve 仅仅是开辟内存空间。直观的表现就是 resize 会改变 vector size 的值（此时 capacity 也可能会改变），而 reserve 改变的是 capacity。

vector<int> a(100, 1};
vector<int> b;
b.resize(100);	// 这里如果是 reserve 会出错
std::copy(a.begin(), a.begin() + step, b.begin());
1
2
3
4

1.4 增

// insert 在指定位置之前插入指定数量的值
// 插入的过程中可能会造成realloc,这时 it 失效
std::vector<int> a = {1,2,3,4,5,6};
a.reserve(10);	// 注意这里开辟了capcity，插入不会 realloc， it 不会失效，仍然指向 begin 位置
std::vector<int>::iterator it = a.begin();
a.insert(it, 1); // a = {1,1,2,3,4,5,6}
a.insert(it, 3, 2); // a = {2,2,2,1,1,2,3,4,5,6} 注意插入的位置

std::vector<int> b = {11, 20, 30};
std::vector<int>::iterator it1 = b.begin();
a.insert(it, it1, it1 + 2); // a = {11,20,1,1,2,2,2,2,3,4,5,6}

// emplace c++11
auto it = a.emplace ( a.begin()+1, 100 ); // a = {11,100,20,1,1,2,2,2,2,3,4,5,6}
a.emplace ( it, 200 ); // a = {11,200,100,20,1,1,2,2,2,2,3,4,5,6}

a.emplace ( a.end(), 300 ); // a = {11,200,100,20,1,1,2,2,2,2,3,4,5,6,300}
// a.emplace_back(300)

a.push_back(7);

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

C++11 及之后应该优先考虑用 emplace 或者 emplace_back，因为原地构造后加入容器，效率更高。

1.5 查

// 下标
a[0]

// at
a.at(0)	// 推荐使用，越界会抛异常

// iterator
a.begin()
a.rbegin() //reverse
a.cbegin() //const
a.crbegin()

//特殊位置
a.front()
a.back()

// data
int* p = myvector.data();
cout << *p;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1.6 改

// 批量修改
a.assign(5,1);
a.assign(b.begin(), b.begin()+5)
a.swap(b) //交换 a, b 的data

// 单个修改。。。
1
2
3
4
5
6

1.7 删

a.erase(b.begin()) //删除单个，这里需要注意的是 erase 返回的是删除位置的下一个位置的迭代器
a.erase(b.begin(), b.begin()+5) //删除多个
a.clear();//删除所有
1
2
3

2. 结合算法

2.1 排序

利用 algorithm 提供的 sort 进行排序。

sort(vector.begin(), vector.end());	// 从小到大排序
sort(a.begin(), a.end(), [](int x, int y) {return x > y; }); // 从大到小排序
1
2

2.2 统计

下面这段代码，统计了从 m_PixGroup[uwChannel][wKey] 到 m_PixGroup[uwChannel][wKey + ulLen -1] 中 大于 rBenchMark 的值的个数。

ulCount = std::count_if(m_PixGroup[uwChannel][wKey], m_PixGroup[uwChannel][wKey] + ulLen, [rBenchMark](double x) {return x > rBenchMark;});
1

2.4 求和

int sum = 0;
sum = accumulate(a.begin(), a.end(), sum);
1
2

2.5 查找

find(a.begin(), a.end(), num_to_find);
1

2.3 最大值

int m = *max(a.begin(), a.end())	// 返回的是迭代器
1

3. 注意事项

3.1 速度

map 和 set 的效率比较高。

int n = 10000000;
auto t11 = std::chrono::steady_clock::now();
int* a = new int[n];
for (int i = 0; i < n; ++i)
{
    a[i] = i;
}
auto t12 = std::chrono::steady_clock::now();

int temp = 0;
auto t13 = std::chrono::steady_clock::now();
for (int i = 0; i < n; ++i)
{
    temp = a[i];
}
auto t14 = std::chrono::steady_clock::now();

auto t21 = std::chrono::steady_clock::now();
std::vector<int> b;
for (int i = 0; i < n; ++i)
{
    b.push_back(i);
}
auto t22 = std::chrono::steady_clock::now();

auto t23 = std::chrono::steady_clock::now();
for (int i = 0; i < n; ++i)
{
    temp = b[i];
}
auto t24 = std::chrono::steady_clock::now();

auto t25 = std::chrono::steady_clock::now();
std::vector<int>::const_iterator it = b.begin();
std::vector<int>::const_iterator it_end = b.end();
//for (; it != b.end(); ++it)	// need 7045ms
for (; it != it_end; ++ it)
{
    temp = *it;
}
auto t26 = std::chrono::steady_clock::now();

auto t27 = std::chrono::steady_clock::now();
for (auto i : b)
{
    temp = i;
}
auto t28 = std::chrono::steady_clock::now();

double a_c = std::chrono::duration<double, std::milli>(t12 - t11).count();
double a_v = std::chrono::duration<double, std::milli>(t14 - t13).count();
double b_c = std::chrono::duration<double, std::milli>(t22 - t21).count();
double b_v = std::chrono::duration<double, std::milli>(t24 - t23).count();
double b_i = std::chrono::duration<double, std::milli>(t26 - t25).count();
double b_a = std::chrono::duration<double, std::milli>(t28 - t27).count();

std::cout << "create array(ms): " << a_c << std::endl;
std::cout << "visit array(ms): " << a_v << std::endl;
std::cout << "create vector(ms): " << b_c << std::endl;
std::cout << "visit vector by index(ms): " << b_v << std::endl;
std::cout << "visit vector by iterator(ms): " << b_i << std::endl;
std::cout << "visit vector by :(ms): " << b_a << std::endl;

delete[] a;
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
53
54
55
56
57
58
59
60
61
62
63
64

Debug:

Release:

3.2 压缩空间

当我们 erase 或者 clear 数据后，vector 的空间（capacity）是没有释放的，可以 通过 swap 或者 shrink_to_fit 释放空间。

	// swap
	std::vector<int> a = { 1,2,3,4 };
	std::cout << "size: " << a.size() << " capacity: " << a.capacity() << std::endl;

	a.erase(a.begin());
	std::cout << "size: " << a.size() << " capacity: " << a.capacity() << std::endl;

	std::vector<int>(a).swap(a);
	
	std::cout << "size: " << a.size() << " capacity: " << a.capacity() << std::endl;

	// a.shrink_to_fit();
	a.clear();
	std::cout << "size: " << a.size() << " capacity: " << a.capacity() << std::endl;

	a.shrink_to_fit();
	std::cout << "size: " << a.size() << " capacity: " << a.capacity() << std::endl;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.3 兼容性

以 vector 做为接口时，如果出现 debug， release 混用（B.dll 依赖 Ad.dll）， 可能造成兼容性问题。

4 补充

4.1 vector 和 list 的区别？

• vector底层实现是数组，所以在内存中是连续存放的，随机读取效率高，但插入、删除效率低；
• list底层实现是双向链表，所以在内存中是任意存放的，插入、删除效率高，但访问元素效率低。
• vector在中间节点进行插入、删除会导致内存拷贝，而list不会。
• vector一次性分配好内存，不够时才进行扩容；list每次插入新节点都会进行内存申请。

4.2 deque 和 vector 的区别？

deque（双端队列）是由一段一段的定量连续空间构成，可以向两端发展，因此不论在尾部或头部安插元素都十分迅速。 在中间部分安插元素则比较费时，因为必须移动其它元素。

deque 与 vector 的用法基本一致，除了以下几处不同：

• deque 没有 reserve 和 capacity，而 vector 有；
• deque 有 push_front() 和 pop_front() 函数，而 vector 没有；
• deque 没有 data() 函数，而 vector 有。

4.3 unique_pointer 可以作为 vector 的元素吗？

不能。因为STL的标准容器规定它所容纳的元素必须是可以拷贝构造和可被转移赋值的，而unique_pointer 不能，可以用shared_ptr智能指针代替。

4.4 vector 可以取代指针吗？

基本都是采用 vector 。如果从性能的角度考虑的话，vector 主要有两个劣势：

• 如果引发动态扩容，不可避免的需要重新申请内存，然后拷贝数据到新的内存
• 插入数据的时候可能引起不必要的构造

针对上面两点可以针对性的避免：

• 使用 reserve 提前预估内存大小
• 采用 emplace/emplace_back 插入元素

参考

• cplusplus-std::vector
• cppreference-std::vector