std::vector简介及其使用

本文中的vector指的是std::vector C++11标准。

 

Vector概述

template <class T，class Alloc = allocator <T> > class vector; //通用模板

　　vector是表示可以改变大小的数组的序列容器。

　　就像数组一样，vector使用连续存储空间存储元素，这意味着它们的元素也可以使用指向其元素的指针进行偏移来访问，并与数组一样高效。但与数组不同的是， vector的大小可以动态变化，并且是由容器自动处理的。

　　在内部实现上，vector使用动态分配的数组来存储它们的元素。在插入新元素时，vector的大小增大，可能需要重新分配数组，这意味着可能要分配新数组并将原有数组中所有元素移动到这个新数组中。重新分配数组的时间成本相对高昂，因此，vector不会在每次向容器添加元素时都重新分配数组。vector容器可能会分配一些额外的存储空间来适应可能的增长，因此容器的实际容量可能比其包含的元素个数要大。不同库可以实现不同的增长策略以在使用现有内存和 重新分配内容之间取得平衡，但无论如何，重新分配内存时的数组大小应以对数增长，这样在vector末端插入单个元素时就可以得到平摊的常数时间复杂度。

　　因此，与数组相比，vector消耗更多内存，以换取以更有效的方式管理存储空间。

　　与其他动态序列容器（deques，lists和forward_lists）相比，vector可以非常高效地访问其元素（就像数组一样）并且相对高效地从其末尾添加或删除元素。 对于涉及在末尾以外的位置插入或删除元素的操作，性能比其他序列容器要差，并且与lists和forward_lists相比具有更少的迭代器和引用一致性。

 

容器属性

• 顺序存储

 　　序列容器中的元素按照严格的线性顺序存储。各个元素通过使用它们在这个序列中的位置（index）来访问。

• 动态数组

 　　允许直接访问序列中的任何元素，支持指针运算，相对快速的添加/删除序列末尾的元素。

• 分配器

　　 容器使用allocator对象来动态处理其存储需求。

 

模板参数

• T 

　　元素的类型。只有当 T 保证在移动操作时不会抛出异常，实现才会进行优化，即在重新分配数组时移动元素而不是复制它们。

　　别名为成员类型 vector :: value_type。

• Alloc

　　用于定义分配模型的分配器对象的类型。默认情况下，使用allocator类模板，该模板定义最简单的内存分配模型，并且与值无关。

　　别名为成员类型 vector :: allocator_type。

 

成员类型

member type	definition	notes
value_type	The first template parameter (T)
allocator_type	The second template parameter (Alloc)	defaults to: allocator<value_type>
reference	value_type&
const_reference	const value_type&
pointer	allocator_traits<allocator_type>::pointer	for the default allocator: value_type*
const_pointer	allocator_traits<allocator_type>::const_pointer	for the default allocator: const value_type*
iterator	a random access iterator to value_type	convertible to const_iterator
const_iterator	a random access iterator to const value_type
reverse_iterator	reverse_iterator<iterator>
const_reverse_iterator	reverse_iterator<const_iterator>
difference_type	a signed integral type, identical to: iterator_traits<iterator>::difference_type	usually the same as ptrdiff_t
size_type	an unsigned integral type that can represent any non-negative value of difference_type	usually the same as size_t

 

成员函数

•  (constructor) 构造函数

default (1)	explicit vector (const allocator_type& alloc = allocator_type());
fill (2)	explicit vector (size_type n); vector (size_type n, const value_type& val, const allocator_type& alloc = allocator_type());
range (3)	template <class InputIterator> vector (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());
copy (4)	vector (const vector& x); vector (const vector& x, const allocator_type& alloc);
move (5)	vector (vector&& x); vector (vector&& x, const allocator_type& alloc);
initializer list (6)	vector (initializer_list<value_type> il, const allocator_type& alloc = allocator_type());

default (1)	explicit vector (const allocator_type& alloc = allocator_type());
fill (2)	explicit vector (size_type n); vector (size_type n, const value_type& val, const allocator_type& alloc = allocator_type());
range (3)	template <class InputIterator> vector (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());
copy (4)	vector (const vector& x); vector (const vector& x, const allocator_type& alloc);
move (5)	vector (vector&& x); vector (vector&& x, const allocator_type& alloc);
initializer list (6)	vector (initializer_list<value_type> il, const allocator_type& alloc = allocator_type());

 　　构造函数示例：

// constructing vectors
#include <iostream>
#include <vector>

int main ()
{
  // constructors used in the same order as described above:
  std::vector<int> first;                                // empty vector of ints
  std::vector<int> second (4,100);                       // four ints with value 100
  std::vector<int> third (second.begin(),second.end());  // iterating through second
  std::vector<int> fourth (third);                       // a copy of third

  // the iterator constructor can also be used to construct from arrays:
  int myints[] = {16,2,77,29};
  std::vector<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

  std::cout << "The contents of fifth are:";
  for (std::vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

Output:
The contents of fifth are: 16 2 77 29 

•  (destructor) 析构函数

~vector();

• operator= 赋值

copy (1)	vector& operator= (const vector& x);
move (2)	vector& operator= (vector&& x);
initializer list (3)	vector& operator= (initializer_list<value_type> il);

•  迭代器相关

函数	函数原型	功能描述
begin	iterator begin() noexcept;	Return iterator to   beginning
	const_iterator   begin() const noexcept;
end	iterator end() noexcept;	Return iterator to   end
	const_iterator   end() const noexcept;
rbegin	reverse_iterator rbegin()   noexcept;	Return reverse   iterator to reverse beginning
	const_reverse_iterator   rbegin() const noexcept;
rend	reverse_iterator rend()   noexcept;	Return reverse   iterator to reverse end
	const_reverse_iterator   rend() const noexcept;
cbegin	const_iterator cbegin() const   noexcept;	Return const_iterator to   beginning
cend	const_iterator cend() const noexcept;	Return const_iterator to   end
crbegin	const_reverse_iterator crbegin() const noexcept;	Return const_reverse_iterator to   reverse beginning
crend	const_reverse_iterator crend()   const noexcept;	Return const_reverse_iterator to   reverse end

 　　迭代器示例：

// vector::begin/end
#include <iostream>
#include <vector>

int main ()
{
  std::vector<int> myvector;
  for (int i=1; i<=5; i++)
    myvector.push_back(i);

  std::cout << "myvector contains:";
  for (std::vector<int>::iterator it = myvector.begin() ; it != myvector.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

Output:
myvector contains: 1 2 3 4 5

•  容器大小或容量相关

函数	函数原型	功能描述
size	size_type size() const noexcept;	Return size
max_size	size_type max_size() const   noexcept;	Return maximum size
resize	void resize (size_type n);	Change size
	void   resize (size_type n, const value_type& val);
capacity	size_type capacity() const noexcept;	Return size of allocated storage   capacity
empty	bool empty() const noexcept;	Test whether vector is   empty
reserve	void reserve (size_type n);	Request a change in   capacity
shrink_to_fit	void shrink_to_fit();	Shrink to fit

　　示例：

// comparing size, capacity and max_size
#include <iostream>
#include <vector>

int main ()
{
  std::vector<int> myvector;

  // set some content in the vector:
  for (int i=0; i<100; i++)
    myvector.push_back(i);

  std::cout << "size: " << (int) myvector.size() << '\n';
  std::cout << "capacity: " << (int) myvector.capacity() << '\n';
  std::cout << "max_size: " << (int) myvector.max_size() << '\n';
  return 0;
}

A possible output for this program could be:
size: 100
capacity: 128
max_size: 1073741823

• 成员访问相关

函数	函数原型	功能描述
operator[]	reference operator[] (size_type   n);	Access element
	const_reference operator[] (size_type n) const;
at	reference at (size_type n);	Access element
	const_reference at (size_type n) const;
front	reference front();	Access first   element
	const_reference front() const;
back	reference back();	Access last   element
	const_reference back() const;
data	value_type* data() noexcept;	Access data. Return value: A pointer to the first element in the array used internally by the vector.
	const value_type* data() const noexcept;

　　成员访问示例：

// vector::operator[]
#include <iostream>
#include <vector>

int main ()
{
  std::vector<int> myvector (10);   // 10 zero-initialized elements

  std::vector<int>::size_type sz = myvector.size();

  // assign some values:
  for (unsigned i=0; i<sz; i++) myvector[i]=i;

  // reverse vector using operator[]:
  for (unsigned i=0; i<sz/2; i++)
  {
    int temp;
    temp = myvector[sz-1-i];
    myvector[sz-1-i]=myvector[i];
    myvector[i]=temp;
  }

  std::cout << "myvector contains:";
  for (unsigned i=0; i<sz; i++)
    std::cout << ' ' << myvector[i];
  std::cout << '\n';

  return 0;
}

Output:
myvector contains: 9 8 7 6 5 4 3 2 1 0
----------------------------------------------------------------------
// vector::at
#include <iostream>
#include <vector>

int main ()
{
  std::vector<int> myvector (10);   // 10 zero-initialized ints

  // assign some values:
  for (unsigned i=0; i<myvector.size(); i++)
    myvector.at(i)=i;

  std::cout << "myvector contains:";
  for (unsigned i=0; i<myvector.size(); i++)
    std::cout << ' ' << myvector.at(i);
  std::cout << '\n';

  return 0;
}

Output:
myvector contains: 0 1 2 3 4 5 6 7 8 9
----------------------------------------------------------------------
// vector::front
#include <iostream>
#include <vector>

int main ()
{
  std::vector<int> myvector;

  myvector.push_back(78);
  myvector.push_back(16);

  // now front equals 78, and back 16

  myvector.front() -= myvector.back();

  std::cout << "myvector.front() is now " << myvector.front() << '\n';

  return 0;
}

Output:
myvector.front() is now 62
----------------------------------------------------------------------
// vector::back
#include <iostream>
#include <vector>

int main ()
{
  std::vector<int> myvector;

  myvector.push_back(10);

  while (myvector.back() != 0)
  {
    myvector.push_back ( myvector.back() -1 );
  }

  std::cout << "myvector contains:";
  for (unsigned i=0; i<myvector.size() ; i++)
    std::cout << ' ' << myvector[i];
  std::cout << '\n';

  return 0;
}

Output:
myvector contains: 10 9 8 7 6 5 4 3 2 1 0
----------------------------------------------------------------------
// vector::data
#include <iostream>
#include <vector>

int main ()
{
  std::vector<int> myvector (5);

  int* p = myvector.data();

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

  std::cout << "myvector contains:";
  for (unsigned i=0; i<myvector.size(); ++i)
    std::cout << ' ' << myvector[i];
  std::cout << '\n';

  return 0;
}

Output:
myvector contains: 10 20 0 100 0

• 添加、删除等修改相关操作

函数	函数原型	功能描述
assign	template <class InputIterator> void assign (InputIterator first, InputIterator last);	Assign vector content. Assigns new contents to the vector, replacing its current contents, and modifying its size accordingly.
	void assign (size_type n, const value_type& val);
	void assign (initializer_list<value_type> il);
push_back	void push_back (const value_type& val);	Add element at the end
	void push_back (value_type&& val);
pop_back	void pop_back();	Delete last element
insert	iterator insert (const_iterator position, const value_type& val);	Insert elements. Return value: An iterator that points to the first of the newly inserted elements.
	iterator insert (const_iterator position, size_type n, const value_type& val);
	template <class InputIterator> iterator insert (const_iterator position, InputIterator first, InputIterator last);
	iterator insert (const_iterator position, value_type&& val);
	iterator insert (const_iterator position, initializer_list<value_type> il);
erase	iterator erase (const_iterator position);	Erase elements
	iterator erase (const_iterator first, const_iterator last);
swap	void swap (vector& x);	Swap content
clear	void clear() noexcept;	Clear content
emplace	template <class...   Args> iterator emplace (const_iterator position, Args&&... args);	Construct and insert   element
emplace_back	template <class...   Args> void emplace_back (Args&&... args);	Construct and insert element at   the end

 　　示例：

// vector assign
#include <iostream>
#include <vector>

int main ()
{
  std::vector<int> first;
  std::vector<int> second;
  std::vector<int> third;

  first.assign (7,100);             // 7 ints with a value of 100

  std::vector<int>::iterator it;
  it=first.begin()+1;

  second.assign (it,first.end()-1); // the 5 central values of first

  int myints[] = {1776,7,4};
  third.assign (myints,myints+3);   // assigning from array.

  std::cout << "Size of first: " << int (first.size()) << '\n';
  std::cout << "Size of second: " << int (second.size()) << '\n';
  std::cout << "Size of third: " << int (third.size()) << '\n';
  return 0;
}

Output:
Size of first: 7
Size of second: 5
Size of third: 3
----------------------------------------------------------------------
// inserting into a vector
#include <iostream>
#include <vector>

int main ()
{
  std::vector<int> myvector (3,100);
  std::vector<int>::iterator it;

  it = myvector.begin();
  it = myvector.insert ( it , 200 );

  myvector.insert (it,2,300);

  // "it" no longer valid, get a new one:
  it = myvector.begin();

  std::vector<int> anothervector (2,400);
  myvector.insert (it+2,anothervector.begin(),anothervector.end());

  int myarray [] = { 501,502,503 };
  myvector.insert (myvector.begin(), myarray, myarray+3);

  std::cout << "myvector contains:";
  for (it=myvector.begin(); it<myvector.end(); it++)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

Output:
myvector contains: 501 502 503 300 300 400 400 200 100 100 100

• Allocator相关

函数	函数原型	功能描述
get_allocator	allocator_type get_allocator()   const noexcept;	Get allocator

 

重载的非成员函数

函数	函数原型	功能描述
relational operators	template <class T, class Alloc> bool operator== (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);	Relational operators for vector
	template <class T, class Alloc> bool operator!= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
	template <class T, class Alloc> bool operator<  (const   vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
	template <class T, class Alloc> bool operator<= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
	template <class T, class Alloc> bool operator>  (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
	template <class T, class Alloc> bool operator>= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
swap	template <class T, class Alloc> void swap (vector<T,Alloc>& x, vector<T,Alloc>& y);	Exchange contents of vectors

 

特例

函数	函数原型	功能描述
vector<bool>	template <class T, class   Alloc = allocator<T> > class vector; // generic template template <class Alloc> class vector<bool,Alloc>;   // bool specialization	Vector of bool

 　　注：vector<bool>使用不慎可能会出问题，一般都建议不要使用。

 

翻译、参考：

　　http://www.cplusplus.com/reference/vector/vector/