C++之vector

2020-12-23

std::vector是最为常用的容器，其定义在文件中，std::vector是封装动态数组的顺序容器。vector的存储是自动管理的，按需扩张和收缩。vector通常占用对于静态数组的空间，因为要分配更多内存以管理增长。vector在额外内存耗尽的时进行重新分配，分配之后的内存大小可以使用capacity()函数查询，多余的内存可以通过shrink_to_fit()的调用还给系统。

重分配通常是性能上有开销的操作。若元素数量已知，则 reserve() 函数可用于消除重分配。

vector 上的常见操作复杂度（效率）如下：

§ 随机访问——常数 O(1)

§ 在末尾插入或移除元素——均摊常数 O(1)

§ 插入或移除元素——与到 vector 结尾的距离成线性 O(n)

在删除元素或者增加元素的时候都有可能使vector的迭代器无效，下表表示示可能导致vector迭代器失效的操作，以及这些操作在什么情况下会使迭代器无效

操作	迭代器无效化
所有只读操作	决不
swap 、 std::swap	end()
clear 、 operator= 、 assign	始终
reserve 、 shrink_to_fit	若 vector 更改容量，则为其全部。否则为无。
erase	被擦除元素及之后的所有元素（包括 end() ）。
push_back 、 emplace_back	若 vector 更改容量，则为其全部。否则仅 end() 。
insert, emplace	若 vector 更改容量，则为其全部。否则仅为在或于插入点后者（包括 end() ）。
resize	若 vector 更改容量，则为其全部。否则仅 end() 与被擦除元素。
pop_back	被擦除元素及 end() 。

vector中的成员类型有：

成员类型	定义
value_type	T
allocator_type	Allocator
size_type	无符号整数类型（通常是 std::size_t ）
difference_type	有符号整数类型（通常是 std::ptrdiff_t ）
reference	Allocator::reference (C++11 前) value_type& (C++11 起)
const_reference	Allocator::const_reference (C++11 前) const value_type& (C++11 起)
pointer	Allocator::pointer (C++11 前) std::allocator_traits::pointer (C++11 起)
const_pointer	Allocator::const_pointer (C++11 前) std::allocator_traits::const_pointer (C++11 起)
iterator	遗留随机访问迭代器 (LegacyRandomAccessIterator)
const_iterator	常随机访问迭代器
reverse_iterator	std::reverse_iterator
const_reverse_iterator	std::reverse_iterator

vector的member function:

(构造函数)	构造 vector (公开成员函数)
(析构函数)	析构 vector (公开成员函数)
operator=	赋值给容器 (公开成员函数)
assign	将值赋给容器 (公开成员函数)
get_allocator	返回相关的分配器 (公开成员函数)
元素访问
at	访问指定的元素，同时进行越界检查 (公开成员函数)
operator[]	访问指定的元素 (公开成员函数)
front	访问第一个元素 (公开成员函数)
back	访问最后一个元素 (公开成员函数)
data	返回指向内存中数组第一个元素的指针 (公开成员函数)
迭代器
begincbegin (C++11)	返回指向起始的迭代器 (公开成员函数)
endcend (C++11)	返回指向末尾的迭代器 (公开成员函数)
rbegincrbegin (C++11)	返回指向起始的逆向迭代器 (公开成员函数)
rendcrend (C++11)	返回指向末尾的逆向迭代器 (公开成员函数)
容量
empty	检查容器是否为空 (公开成员函数)
size	返回容纳的元素数 (公开成员函数)
max_size	返回可容纳的最大元素数 (公开成员函数)
reserve	预留存储空间 (公开成员函数)
capacity	返回当前存储空间能够容纳的元素数 (公开成员函数)
shrink_to_fit (C++11)	通过释放未使用的内存减少内存的使用 (公开成员函数)
修改器
clear	清除内容 (公开成员函数)
insert	插入元素 (公开成员函数)
emplace (C++11)	原位构造元素 (公开成员函数)
erase	擦除元素 (公开成员函数)
push_back	将元素添加到容器末尾 (公开成员函数)
emplace_back (C++11)	在容器末尾就地构造元素 (公开成员函数)
pop_back	移除末元素 (公开成员函数)
resize	改变容器中可存储元素的个数 (公开成员函数)
swap	交换内容 (公开成员函数)

Non-member function:

operator== operator!= (C++20 中移除) operator<(C++20 中移除) operator<=(C++20 中移除) operator>(C++20 中移除) operator>=(C++20 中移除) operator<=>(C++20)	按照字典顺序比较 vector 中的值 (函数模板)
std::swap(std::vector)	特化 std::swap 算法 (函数模板)
erase(std::vector)erase_if(std::vector) (C++20)	擦除所有满足特定判别标准的元素 (函数模板)

示例代码：

#include <iostream>
#include <vector>
#include <algorithm>
int main() {

  //列表初始化
  std::vector<int> v1{7, 5, 16, 8};
  //自动推导，c++17
  std::vector v2(v1.begin(),v1.end());
  std::for_each(v2.begin(),v2.end(),[](int x){std::cout << x << '\t';});
  std::cout << "\n";

  v2.emplace_back(10);
  v2.emplace_back(6);
  v2.emplace_back(13);
  v2.emplace_back(4);

  std::vector v3(v2);
  std::sort(v2.begin(),v2.end());
  std::for_each(v2.begin(),v2.end(),[](int x){std::cout << x << '\t';});
  std::cout << "\n";

  std::cout << "capacity is : " <<v2.capacity() << std::endl;
  std::cout << "size is : " << v2.size() << std::endl;
  //交互
  v3.swap(v2);
  std::for_each(v3.begin(),v3.end(),[](int x){std::cout << x << '\t';});
  std::cout << "\n";

  std::for_each(v2.begin(),v2.end(),[](int x){std::cout << x << '\t';});
  std::cout << "\n";
  //清除内容
  v2.clear();
  std::cout << "capacity is : " <<v2.capacity() << std::endl;
  std::cout << "size is : " << v2.size() << std::endl;
  //归还内存
  v2.shrink_to_fit();
  std::cout << "capacity is : " <<v2.capacity() << std::endl;
  std::cout << "size is : " << v2.size() << std::endl;
  return 0;
}