Vector

头文件

#include <vector>

定义

构造函数

vector(); // 空
vector( size_type num, const TYPE &val ); // 初始化多个重复项
vector( const vector &from ); // 复制容器
vector( input_iterator start, input_iterator end ); // 迭代器初始化

属性

vector可以理解成一个可以扩张的数组，每次扩张多出来一定数量的容量。这个多出多少是不确定的，不同编译器不同，VS2015是1.5，GCC是2倍，一般介于这两者之间。

1. size_type capacity() const;

• 返回当前容量
• 容量并非实际有几个元素，而是最多能放几个元素

vec.capacity()

2. void reserve (size_type n);

• 设置容器可以容纳几个元素

vec.reserve(10)

3. size_type size() const;

• 返回当前元素数量

vec.size()

4. void resize (size_type n, value_type val = value_type());

• 改变容器元素数量
• 会强制改变元素数量无论减少还是增加，都填为val

vec.resize(10)
vec.resize(10,2)

5. bool empty() const;

• 判断vector是否为空（返回true时为空）

vec.empty()

操作

1. void push_back (const value_type& val);

• 在容器末尾添加一个元素

vec.push_back(10)

2. single element (1)	iterator insert (iterator position, const value_type& val);
   fill (2)	void insert (iterator position, size_type n, const value_type& val);
   range (3)	template <class InputIterator> void insert (iterator position, InputIterator first, InputIterator last);

• 插入元素

vec.insert(vec.begin(),7); //在vec的第一个位置插入7 
vec.insert(vec1.begin()+1,3,6); //在第二个位置加入3个6 
vec.insert(vec1.begin()+2,vec1.begin(),vec2.begin()+2); //在vec的第三个位置加入vec1的第1到第2个 

3. void pop_back();

• 移除最后一个元素

vec.pop_back()

4. iterator erase (iterator position);
   iterator erase (iterator first, iterator last);

• 删除指定元素

vec.erace(vec.begin+5); //删除第六个元素
vec.erace(vec.begin,vec.begin+5); //删除第一个到第五个元素

5. range (1)	template <class InputIterator> void assign (InputIterator first, InputIterator last);
   fill (2)	void assign (size_type n, const value_type& val);

• 对vector中元素赋值
• 强制执行

vec.assign(vec1.begin(),vec1.begin()+3); //把vec1中的前3个元素赋给vec
vec.assign(3,6); //vec赋值为三个6并且之前的vec内容会被清除

6. void clear();

• 清除vector中所有元素，会析构所有元素
• 未必会改变容器大小（capacity）

vec.clear()
vector<T>().swap(x);   // 清除x所有元素并把改变容器大小

7. void swap (vector& x);

• 交换两个容器中的内容

vec.swap(vec1)

查询

1. iterator begin();
   reverse_iterator rbegin();

• begin指向当前容器起始元素的迭代器，rbegin

vec.begin()

2. reference front();

• 返回容器起始元素的引用

vec.front()

3. iterator end();
   reverse_iterator rend();

• end是指向容器末尾元素下一位的迭代器，rend是指向第一个元素前的迭代器

vec.end()

4. reference back();

• 返回容器末尾元素的引用

vec.back()

5. reference at (size_type n);

• 返回指定位置的元素的引用，比方括号更加安全，会在越界时抛出一个异常

vec.at(5)

C++11

1. const_iterator cbegin() const noexcept;
   const_iterator cend() const noexcept;
   const_reverse_iterator crbegin() const noexcept;
   const_reverse_iterator crend() const noexcept;

• 指向一个const元素的迭代器/反向迭代器

vec.cbegin();
vec.cend();
vec.crbegin();
vec.crend();

2. value_type* data() noexcept;

• 返回容器中数组的指针

int* p = myvector.data();

*p = 10;
++p;
*p = 20;
p[2] = 100;

3. template <class… Args>
   iterator emplace (const_iterator position, Args&&… args);

   template <class… Args>
   void emplace_back (Args&&… args);

• 更高效的insert()和push_back()，原地构造而不是构造再移动入容器

vec.emplace(myvector.end(), 300);
vec.emplace_back(100)

4. void shrink_to_fit();

• 把容器大小调整为容器的size

vec.shrink_to_fit();

复杂度

适合在尾部插入弹出，插入删除特定位置都是$O(n)$。