STL系列——vector

 
template < class T, class Alloc = allocator<T> > class vector; // generic template
vector用来表示数组,是大小可以动态改变的序列容器。vector内部使用动态分配的数组来存储元素。当元素增加需要分配更多空间的时候,需要将原始数组中内容拷贝到新的数组,然后销毁原始数组。z再分配是一个比较耗时的过程。为了内存使用和再分配之间的平衡,数组的长度的增长,不同的库有b不同的实现策略。
如gcc(这里使用版本是 gcc 5.2), 第一次分配时,capacity() == size()。如果后面增加内容,假设增加长度len, 原始vector长度为size( ),
若len > size(), 重新分配空间,增长后,capacity() = len + size();
若 len <= size( ) 并且 len + size()> capacity(),重新分配空间,增长后,capacity() = size()*2 ;
若len <= size( ) 并且 len+ size( ) <= capacity( ),不重新分配。

构造函数

default (1)   vector();
              explicit vector (const allocator_type& alloc);
fill (2)      explicit vector (size_type n, const allocator_type& alloc = allocator_type());
              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());

几种使用方法

// 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) );

赋值构造函数

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

迭代器

begin(), end(), rbegin(), rend(), cbegin(), cend(), crbegin(), crend()
当容器为空时,begin() 返回的迭代器不能解引用。(string为空时,begin() 可以解引用)

Capacity

size_type size() const noexcept;
size_type max_size() const;           // return the maximum number of elements that the vector can holds. due to known systems or library implementation limitations.

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

如果n小于当前容器size(), 只保留开头的n个元素;如果n大于容器size(), 通过插入进行扩展。同时如果n 大于当前capacity(), 一个自动空间重分配操作会执行。
size_type capacity() const noexcept;       // 返回当前vector分配的存储空间大小(expressed in terms of elements)
bool empty() const noexcept;
void reserve (size_type n);         // request a change in capacity   当n大于当前capacity时,会导致容器重分配空间;否则没有影响。
void shrink_to_fit();    // 要求容器减小他的capacity到适合他的size,没有强制要求,具体示实现。可能会导致reallocation,但是不会修改vector的size或者内容。

Element Access

// Returns a reference to the element at position n in the vector container.
 reference operator[] (size_type n);
const_reference operator[] (size_type n) const;
// Access element
// Returns a reference to the element at position n in the vector.
reference at (size_type n);
const_reference at (size_type n) const;
//Access first element
//Returns a reference to the first element in the vector.
reference front();
const_reference front() const;
//Access last element
//Returns a reference to the last element in the vector.
 reference back();
const_reference back() const;
// Returns a direct pointer to the memory array used internally by the vector to store its owned elements.
 value_type* data() noexcept;
const value_type* data() const noexcept;

Modifier

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);

range适用于迭代器或者数组
push_back( )、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);

删除指定位置的元素,或者一段区间的元素
返回值为指向删除元素后第一个元素的iterator

void swap (vector& x);

与另一个有相同类型(T, Alloc)的容器的内容进行交换。 包括内容、capacity。其实就是相当于两个指针换了指向的位置,对应的属性(data、size、capacity等)也改变了。

void clear() noexcept;

清除vector里面的内容,将容器大小减小到0。不保证有内存的重新分配。

vector<int>( ).swap(x)

可以强制清空vector x,并重分配空间

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

C++11新特性,Construct and insert element。

The container is extended by inserting a new element at position. This new element is constructed in place using args as the arguments for its construction.
This effectively increases the container size by one.
template <class... Args>
  void emplace_back (Args&&... args);

Construct and insert element at the end

Allocator

allocator_type get_allocator() const noexcept;
// Returns a copy of the allocator object associated with the vector.

例子

// vector::get_allocator
#include <iostream>
#include <vector>
int main ()
{
  std::vector<int> 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;
}

关系操作符

(1) template <class T, class Alloc>
  bool operator== (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
(2) template <class T, class Alloc>
  bool operator!= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
(3) template <class T, class Alloc>
  bool operator<  (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
(4) template <class T, class Alloc>
  bool operator<= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
(5) template <class T, class Alloc>
  bool operator>  (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);
(6) template <class T, class Alloc>
  bool operator>= (const vector<T,Alloc>& lhs, const vector<T,Alloc>& rhs);

== 操作首先比较size,如果相同,然后使用operator==顺序比较,直到第一个不匹配的
<操作则使用operator<进行顺序比较
其他比较操作内部使用 operator == 或者 operator < 操作进行比较

template <class T, class Alloc>
  void swap (vector<T,Alloc>& x, vector<T,Alloc>& y);

交换操作,类似于x.swap(y)

模板特化

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

 

Leave a Reply

Your email address will not be published. Required fields are marked *