C++：[STL]详解STL之sequence container的操作及使用(vector)

1.引入

STL，即 standard tempalate library，标准模板库，是C++的重要组成部分。C++ STL（标准模板库）是一套功能强大的 C++ 模板类，提供了通用的模板类和函数，这些模板类和函数可以实现多种流行和常用的算法和数据结构，如向量、链表、队列、栈。

---

STL的构成：

组成部分	描述
iterator(迭代器)	迭代器用于遍历对象集合的元素。
container(容器)	容器是用来管理某一类对象的集合。
Generic algorithm(泛型算法)	算法作用于容器。它们提供了执行各种操作的方式，包括对容器内容执行初始化、排序、搜索和转换等操作。

---

容器的构成：

分类	举例
Sequential Container（线性容器）	vector, list, deque
Associative Container (关联容器)	map, multimap, set, multiset
Container Adapter (容器适配器)	stack, queue

---

2.vector类介绍

According to cplusplus.com,

Vectors are sequence containers representing arrays that can change in size.

Just like arrays, vectors use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently as in arrays.* But unlike arrays, their size can change dynamically, with their storage being handled automatically by the container*.

Internally, vectors use a dynamically allocated array to store their elements. This array may need to be reallocated in order to grow in size when new elements are inserted, which implies allocating a new array and moving all elements to it. This is a relatively expensive task in terms of processing time, and thus, vectors do not reallocate each time an element is added to the container.

Instead, vector containers may allocate some extra storage to accommodate for possible growth, and thus the container may have an actual capacity greater than the storage strictly needed to contain its elements (i.e., its size). Libraries can implement different strategies for growth to balance between memory usage and reallocations, but in any case, reallocations should only happen at logarithmically growing intervals of size so that the insertion of inpidual elements at the end of the vector can be provided with amortised constant time complexity (see push_back).

Therefore, compared to arrays, vectors consume more memory in exchange for the ability to manage storage and grow dynamically in an efficient way.

Compared to the other dynamic sequence containers (deques, lists and forward_lists), vectors are very efficient accessing its elements (just like arrays) and relatively efficient adding or removing elements from its end. For operations that involve inserting or removing elements at positions other than the end, they perform worse than the others, and have less consistent iterators and references than lists and forward_lists.

分析：

(1)vector是array的升级版

vector是一个sequence容器，是array的升级版，主要因为vector能高效地对内存进行管理以及动态增长。但是，vector其实就是将array和方法封装形成的一个类。

(2)vector容器的内存管理

vector的容器大小可以动态增长，但是并不意味着每一次插入操作都进行reallocate。内存的分配与释放耗费的资源是比较大的，因此应当减少它的次数。与此同时，这也就意味着容器的容量(capacity)与容器目前容纳的大小(size)是不等的，前者应大于后者。

补充：上文也说了，对于vector内存的增长有很多strategies，例如第一次增长我增加2个内存单位，第二次增长我增加4个内存单位，第三次，第四次，… 第n次我增长2^n(前提是vector内存不够时再分配)，这样也就大大减少了reallocate的次数。

(3)vector容器的意义

然后，vector虽然相对于array消耗了更多的内存，但是却实现了对内存的高效管理和增长，这种消耗是值得的。

(4)vector容器与其他容器的比较

与其他的sequence容器比较(如list，dequeue), vector访问元素的效率较高，但是对于增加与删除操作就不如其他两个容器了。

---

时间复杂度：

container	access	insert or erase
vector	O(1)	O(n^2)
list	O(n)	O(n)
dequeue	O(n)	O(n)

---

虽然list和deque时间复杂度相同，但是因为空间复杂度不同，二者效率也是不同的。

到这里，在对vector容器有一定了解之后，我们开始接触vector容器的各种操作。

3.vector类常用操作

注：列操作清单，详解在后文。

操作	作用
(constructor)	Construct vector
(destructor)	Vector destructor
operator=	Assign content
begin	Return iterator to beginning
end	Return iterator to end
rbegin	Return reverse iterator to reverse beginning
rend	Return reverse iterator to reverse end
cbegin (c++11)	Return const_iterator to beginning
cend (c++11)	Return const_iterator to end
crbegin (c++11)	Return const_reverse_iterator to reverse beginning
crend (c++11)	Return const_reverse_iterator to reverse end
size	Return size
max_size	Return maximum size
resize	Change size
capacity	Return size of allocated storage capacity
empty	Test whether vector is empty
reserve	Request a change in capacity
shrink_to_fit (c++11)	Shrink to fit
operator[]	Access element
at	Access element
front	Access first element
back	Access last element
data (c++11)	Access data
assign	Assign vector content
push_back	Add element at the end
pop_back	Delete last element
insert	Insert elements
erase	Erase elements
swap	Swap content
clear	Clear content
emplace (c++11)	Construct and insert element
emplace_back (c++11)	Construct and insert element at the end
get_allocator	Get allocator

4.vector容器操作详解

(1)Constructor

// default (1)  
explicit vector (const allocator_type& alloc = allocator_type());
// fill (2) 
explicit vector (size_type n, const value_type& val = value_type(),
                 const allocator_type& alloc = allocator_type());
// range (3)    
template 
         vector (InputIterator first, InputIterator last,
                 const allocator_type& alloc = allocator_type());
// copy (4) 
vector (const vector& x);

构造函数在对象建立时调用，实现内存的动态分配及容器的初始化。
分析：
default(1): 默认构造函数
fill(2)：构造函数，构造一个大小为n的vector容器，每个元素赋值为val，即构造大小为n的容器，并用val充满
fill(3): 传入两个迭代器对象(或为指针，其实iterator的本质就是指针)，将二者间的内容拷贝到vector中(拷贝前会构造对应大小的容器)
注意：拷贝的范围：[first, last)
copy(4)：复制构造函数。传入vector对象，进行拷贝

补充：

alloc
Allocator object.
The container keeps and uses an internal copy of this allocator.
Member type allocator_type is the internal allocator type used by the container, defined in vector as an alias of its second template parameter (Alloc).
If allocator_type is an instantiation of the default allocator (which has no state), this is not relevant.

vector内部有自己的allocator，能够实现动态内存的分配与释放，所以源码中一般不会直接使用new和delete，这样使得内存分配与释放更加安全。

// copy (1) 
 vector& operator= (const vector& x);

copy1: 重载”＝”运算符，实现vector对象的拷贝。在源码实现中，要避免内存泄漏。

(2)Destructor

// destruct
~vector();

析构函数，在对象销毁时调用，能够实现内存的释放，避免内存泄漏。

(3)Iterators

// begin()
      iterator begin();
const_iterator begin() const;

begin():返回指向第一个元素的迭代器。此处既能返回iterator也能返回const_iterator，取决于vector对象的属性。如果vector对象是const，那么返回const_iterator;如果vactor对象不是const，那么返回iterator。
注意：要区分begin()与front()的区别，begin()返回迭代器对象，front()返回容器内的元素对象。

在c++11标准中新增加了cbegin()，用于返回const类型的iterator。

const_iterator cbegin() const noexcept;

A const_iterator is an iterator that points to const content. This iterator can be increased and decreased (unless it is itself also const), just like the iterator returned by vector::begin, but it cannot be used to modify the contents it points to, even if the vector object is not itself const.

If the container is empty, the returned iterator value shall not be dereferenced.

注：
(1)当vector对象不为const时，const_iterator对象自身可以递增或递减;
但是不能对迭代器指向的对象进行修改；当vector对象为const时，const_iterator对象即不能递增递减，也不能对指向对象进行修改。
(2)如果容器为空，begin()与end()返回的对象相同(cbegin()也是如此)，即指向一个非法的空间。

// rbegin()
      reverse_iterator rbegin();
const_reverse_iterator rbegin() const;

rbegin()：返回一个指向最后一个元素的迭代器对象。

同样，c++11中专门定义了一个返回const_iterator对象的函数crbegin()。

// crbegin()
const_reverse_iterator crbegin() const noexcept;

crbegin():返回指向最后一个元素的const_iterator对象。

// end()
      iterator end();
const_iterator end() const;

end():返回一个指向紧接在最后一个元素之后的虚拟元素(实际不存在)，专业的说法就是past-the-end element。

The past-the-end element is the theoretical element that would follow the last element in the vector. It does not point to any element, and thus shall not be dereferenced.

Because the ranges used by functions of the standard library do not include the element pointed by their closing iterator, this function is often used in combination with vector::begin to specify a range including all the elements in the container.

同样，c++11也定义了一个返回const_interator对象的函数cend()

// cend()
const_iterator cend() const noexcept;

cend():返回一个指向const类型的past-the-end element的迭代器。

// rend()
reverse_iterator rend();
const_reverse_iterator rend() const;

rend():返回一个指向位于第一个元素之前的虚拟元素。

Returns a reverse iterator pointing to the theoretical element preceding the first element in the vector (which is considered its reverse end).

同样，c++11中定义了返回const_iterator对象的函数crend()。

// crend()
const_reverse_iterator crend() const noexcept;

crend():返回一个const类型的指向位于第一个元素之前的虚拟元素。

Returns a const_reverse_iterator pointing to the theoretical element preceding the first element in the container (which is considered its reverse end).

总结: begin()与end()搭配使用可以实现正向遍历，rbegin()与rend()搭配使用可以实现逆向遍历。

(4)Capacity

// size()
size_type size() const;

size(): 返回容器内元素的数目(unsigned int对象)

// max_size()
size_type max_size() const;

max_size():返回该该容器能容纳元素的最大数量(unsigned int对象)

也许你会疑惑，max_size()与capacity()的功能是相似的，为什么不删去其中一个？
cplusplus.com给出的解释是：max_size是容器大小理论上的一个限制，而capacity是容器大小实际上的一个限制。

// capacity()
size_type max_size() const;

capacity()： 返回动态分配的内存大小

Notice that this capacity does not suppose a limit on the size of the vector. When this capacity is exhausted and more is needed, it is automatically expanded by the container (reallocating it storage space). The theoretical limit on the size of a vector is given by member max_size.

// resize()
void resize (size_type n, value_type val = value_type());

resize():
将容器大小变为n，下面分三种情况讨论：
(1)如果size > n，那么只保留前n个元素；
(2)如果size < n, 那么多出的部分用val填充；
(3)如果n > max_size, 那么重新分配内存，多出的部分用val填充。
注意：当n < max_size时，不发生内存的重新分配，只改变size大小。若size > n,则使用allocator中的destroy函数，将超出的部分删去。即当n < max_size时，resize()改变的是size而不是max_size。

// empty()
bool empty() const;

empty(): 判断容器是否为空(size 是否为 0)。若为空，返回true；若不为空，返回false。

// reserve()
void reserve (size_type n);

reserve():如果容器的capacity小于n，便会重新分配内存使其capacity达到n；如果capacity 大于等于n，便不会进行任何操作，也就是说，不会影响容器的capacity。

Requests that the vector capacity be at least enough to contain n elements.

// shrink_to_fit()
void shrink_to_fit();

shrink_to_fit():使capacity缩减至size。

Requests the container to reduce its capacity to fit its size.

(5)Element access

// operator []()
      reference operator[] (size_type n);
const_reference operator[] (size_type n) const;

operator ：重载[]运算符。返回处于位置n的元素的引用。

// at()
      reference at (size_type n);
const_reference at (size_type n) const;

at()： 返回位置n的元素的引用。

此时你便会感到疑惑，[]与at()有相同的作用，为何不删除其中一个呢？其实二者是有区别的。[]没有对边界限制，即使用[]有可能出现越界的情况；而at()有对边界的限制，一旦出现越界，便会抛出异常。

A similar member function, vector::at, has the same behavior as this operator function, except that vector::at is bound-checked and signals if the requested position is out of range by throwing an out_of_range exception.

As for []:
Portable programs should never call this function with an argument n that is out of range, since this causes undefined behavior.

// front()
      reference front();
const_reference front() const;

front():返回第一个元素的引用

Calling this function on an empty container causes undefined behavior.
因此在调用front()之前要先确认容器不为空,调用back()也是如此。

// back()
      reference back();
const_reference back() const;

back(): 返回容器内最后一个元素的引用。

c++11中还定义了一个返回指向内部数组的指针的函数data()：

// data()
      value_type* data() noexcept;
const value_type* data() const noexcept;

data():返回一个指向vector内部数组的指针。

Returns a direct pointer to the memory array used internally by the vector to store its owned elements.

(6)Modifiers

// assign()
// range (1)    
template 
  void assign (InputIterator first, InputIterator last);
// fill (2) 
void assign (size_type n, const value_type& val);

range(1):传入两个迭代器对象，将其之间的内容赋值给vector容器，类似于构造函数中的vector (InputIterator first, InputIterator last, const allocator_type& alloc = allocator_type());
fill(2):将其size变为n，并全部赋值为val。
注意：当传入的元素数量大于capacity，便会reallocate；
当传入的元素数量小于capacity，便不会reallocate，只会影响size的大小。

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

push_back():在容器尾部插入val(此处的尾部指最后一个元素之后的位置)

注意： vector容器没有push_front()函数

// pop_back()
void pop_back();

pop_back:弹出最后一个元素，即删去。
注意： vector中也没有pop_front()函数。

// insert()

// 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 
    void insert (iterator position, InputIterator first, InputIterator last);

single element(1):在迭代器所指向元素的前方插入val
fill(2)：在迭代器所指向元素的前方插入n个val
range(3):在迭代器所指向元素的前方插入[first, last)之间的元素。

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

erase(): 删除迭代器所指向的元素或者迭代器所指向的区间[first,last)的元素，并返回指向被删除元素的下一个元素的迭代器或者指向被删除区间最后一个 元素的下一个元素的迭代器。

An iterator pointing to the new location of the element that followed the last element erased by the function call. This is the container end if the operation erased the last element in the sequence.
当最后一个元素被删除时，其返回值与end()相同。

虽然vector没有push_front()和pop_front()，但这并不意味着vector不能实现从头部插入和从头部删除，insert()和erase()就能分别从头插入和从头删除，只是效率不大高。

// swap()
void swap (vector& x);

swap(): 实现两个类型相同的vector对象中内容的交换。

Exchanges the content of the container by the content of x, which is another vector object of the same type. Sizes may differ.

After the call to this member function, the elements in this container are those which were in x before the call, and the elements of x are those which were in this. All iterators, references and pointers remain valid for the swapped objects.

// clear()
void clear();

clear():将容器内元素清空并把size置为0。
注意： clear()函数并不是将vector对象申请的内存释放，它只起到清空的作用。

// emplace()
template 
iterator emplace (const_iterator position, Args&&... args);
// emplace_back()
template 
  void emplace_back (Args&&... args);

emplace() and emplace_back()都是实现元素的插入，前者插入指定位置，与insert()功能相似，后者插入尾部。

这两个方法是在c++11中定义的，调用这两个函数的插入效率高于insert()和push_back()，因为他们避免了内存的拷贝或移动。

emplace_back avoids the extra copy or move operation required when using push_back.

(7)Allocator

// get_allocator
allocator_type get_allocator() const;

get_allocator:返回vector中allocator的拷贝对象

Returns a copy of the allocator object associated with the vector.

cplusplus.com给出的例子：

// vector::get_allocator
#include 
#include 

int main ()
{
  std::vector myvector;
  int * p;
  unsigned int i;

  // allocate an array with space for 5 elements using vector's allocator:
  p = myvector.get_allocator().allocate(5);

  // construct values in-place on the array:
  for (i=0; i<5; i++) myvector.get_allocator().construct(&p[i],i);

  std::cout << "The allocated array contains:";
  for (i=0; i<5; i++) std::cout << ' ' << p[i];
  std::cout << '\n';

  // destroy and deallocate:
  for (i=0; i<5; i++) myvector.get_allocator().destroy(&p[i]);
  myvector.get_allocator().deallocate(p,5);

  return 0;
}

Output:
The allocated array contains: 0 1 2 3 4

---