容器-vector

std::vector

template < class T, class Alloc = allocator<T> > class vector; // generic template

说明：

vector是一个序列容器，可以表示为容量可变的数组。和数组一样，vector是使用连续的内存来存储它的元素，这意味着可以通过指针和offset来访问元素，和array不同的是，它们的大小可以动态变化，并且容器会自动处理它们的存储。

在内部，vector使用一个动态分配的array去存储它们的元素，这个数组可能在有新的元素在插入时会去重新分配新的内存，即具有“grow”特性。

vector可能会分配一些额外的存储空间以适应可能的增长，因此vector有一个实际的capacity。与array相比，vector消耗更多的内存，以换取管理存储和以有效的方式动态增长的能力。

性质：

1. sequence–>序列式
2. dynamic array–>动态增长容量
3. allocator-aware–>能够感知内存分配器

模板参数：

• T:元素的类型，只有保证T类型在移动时不会抛出异常，才能实现在动态扩容的时候移动其元素，而不是重新分配时copy它们。
• Alloc：用于定义存储分配模型的allocator对象的类型，一般使用默认的，它定义了最简单的内存分配模型并且与值无关。

成员类型：

构造函数：

//default (1)	
explicit vector (const allocator_type& alloc = allocator_type());
//fill (2)	Constructs a container with n elements. Each element is a copy of val
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());

关于move constructor，元素如果被移动，那么将使所有与之相关的iterator、pointer和reference全部失效。

析构函数：它会在每个包含的元素上调用allocator_traits::destory函数，并使用它的分配器回收由vector分配的所有存储空间。

operator=：

vector重载了3个版本的operator=

//copy (1)	
vector& operator= (const vector& x);
//move (2)	
vector& operator= (vector&& x);
//initializer list (3)	内部也是copy all elem
vector& operator= (initializer_list<value_type> il);

iterator：

Capacity：

函数原型：

size_type size() const noexcept;

size_type max_size() const noexcept;

void resize (size_type n);
void resize (size_type n, const value_type& val);

size_type capacity() const noexcept;

bool empty() const noexcept;

void reserve (size_type n);

void shrink_to_fit();

元素访问：

修改：

函数原型：

//range (1)	
template <class InputIterator>
void assign (InputIterator first, InputIterator last);
//fill (2)	
void assign (size_type n, const value_type& val);
//initializer list (3)	
void assign (initializer_list<value_type> il);

void push_back (const value_type& val);
void push_back (value_type&& val);

void pop_back();

//single element (1)	
iterator insert (const_iterator position, const value_type& val);
//fill (2)	
iterator insert (const_iterator position, size_type n, const value_type& val);
//range (3)	
template <class InputIterator>
iterator insert (const_iterator position, InputIterator first, InputIterator last);
//move (4)	
iterator insert (const_iterator position, value_type&& val);
//initializer list (5)	
iterator insert (const_iterator position, initializer_list<value_type> il);

iterator erase (const_iterator position);
iterator erase (const_iterator first, const_iterator last);

void swap (vector& x);	//	vector<T>().swap(x);   clear x reallocating

void clear() noexcept;
//通过在位置插入新元素来扩展容器。这个新元素使用args作为其构造的参数就地构造
template <class... Args>
iterator emplace (const_iterator position, Args&&... args);

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

std::vector::get_allocator

//返回与vector关联的分配器的对象的副本
allocator_type get_allocator() const noexcept;

特化的vector:

template < class T, class Alloc = allocator<T> > class vector; // generic template
template <class Alloc> class vector<bool,Alloc>;               // bool specialization

说明:

这是vector的一个特殊版本，用于bool类型的元素并优化空间。有以下改变：

• 不需要一个array来存储bool值，而是使每个值存储在单个bit中。
• 元素不是使用allocator对象构造的，而是直接在内部存储中适当位置上设置它们的值。
• 提供了两个函数flip和swap。
• 一个特殊的成员类型，引用，该类使用模拟bool引用的接口访问窗容器内部存储中的各个bit。

class vector<bool>::reference {
  friend class vector;
  reference() noexcept;                                 // no public constructor
public:
  ~reference();
  operator bool () const noexcept;                      // convert to bool
  reference& operator= (const bool x) noexcept;         // assign from bool
  reference& operator= (const reference& x) noexcept;   // assign from bit
  void flip();                                          // flip bit value.
};

除data、emplace和emplace_back外，vector有和vector相同的特化处理过的成员函数。

两个新增的成员函数：

void flip() noexcept;	//翻转容器中的所有值，true-->false  false-->true


//swap containers (1)	
void swap (vector& x);
//swap elements (2)	
static void swap (reference ref1, reference ref2) noexcept;

测试代码：

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
	//ctor
	vector<int> v1;
	vector<int> v2(5);
	vector<int> v3(5, 1);
	vector<int> v4(v3.begin(), v3.end());
	vector<int> v5(v4);
	vector<int> v6({ 1,2,3,4,5,6 });

	//operator=
	vector<int>v7 = v1;
	vector<int>v8 = { 1,2,3,4,5,6 };

	//capacity
	vector<int> v(10);	//init 0
	cout << "size=" << v.size() << endl;	//10
	cout << "max_size=" << v.max_size() << endl;	//4611686018427387903
	cout << "capacity=" << v.capacity() << endl;	//10
	cout << "v is empty:" << (bool)v.empty() << endl;	//false
	v.reserve(20);
	cout << "请求更改capacity为20，更改后capacity=" << v.capacity() << endl;	//20
	v.shrink_to_fit();
	cout << "优化capacity大小，capacity=" << v.capacity();	//10

	//元素访问
	vector<string> strV{ "I", "love", "you","!" };
	cout << "first elem is " << strV.front() << endl;	//I
	cout << "last elem is " << strV.back() << endl;		//!
	cout << "begin elem is " << *strV.data() << endl;	//I
	cout << "second elem is " << strV.at(1) << endl;	//love
	cout << "third elem is " << strV[2] << endl;		//you

	//修改
	vector<double> doubleV{ 5.20,13.14 };
	vector<double>doubleV_{ 7,2,5 };
	doubleV.assign({ 1.1,2.2 });
	vector<char> chV;
	chV.push_back('i');
	chV.push_back(' ');
	chV.push_back('l');
	chV.push_back('o');
	chV.push_back('v');
	chV.pop_back();
	chV.insert(chV.end(), { 'v','e',' ', 'y','o','u' });
	chV.erase(chV.begin());
	vector<char>().swap(chV); //等价于chv.clear()
	
	//emplace
	std::vector<int> myvector = { 10,20,30 };
	auto it = myvector.emplace(myvector.begin() + 1, 100);
	myvector.emplace(it, 200);
	myvector.emplace(myvector.end(), 300);
	myvector.emplace_back(300);
	myvector.emplace_back(400);
	std::cout << "myvector contains:";
	for (auto& x : myvector)
		std::cout << ' ' << x;
	std::cout << '\n';
	return 0;
}

测试vector<bool>

void test_flip()
{
	std::vector<bool> mask;

	mask.push_back(true);
	mask.push_back(false);
	mask.push_back(false);
	mask.push_back(true);

	mask.flip();

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

void test_swap()
{
	std::vector<bool> foo;
	std::vector<bool> bar;

	foo.push_back(false);
	foo.push_back(true);
	foo.push_back(false);

	bar.push_back(true);
	bar.push_back(false);

	foo.swap(foo[0], foo[1]);
	bar.swap(bar.front(), bar.back());

	foo.swap(bar);

	std::cout << std::boolalpha;
	std::cout << "foo contains:";
	for (unsigned i = 0; i < foo.size(); i++) std::cout << ' ' << foo[i];
	std::cout << "\nbar contains:";
	for (unsigned i = 0; i < bar.size(); i++) std::cout << ' ' << bar[i];
	std::cout << '\n';
}