Container

一、Container

1. Sequential Container

• vector

  连续存储结构，每个元素在内存上是连续的；支持高效的随机访问和在尾端插入/删除操作，但其他位置的插入/删除操作效率低下；相当于一个数组，但是与数组的区别为：内存空间的扩展。vector支持不指定vector大小的存储，但是数组的扩展需要程序员自己写。

  vector的内存分配实现原理：

  STL内部实现时，首先分配一个非常大的内存空间预备进行存储，即capacity()函数返回的大小，当超过此分配的空间时再整体重新放分配一块内存存储(VS6.0是两倍，VS2005是1.5倍)，所以 这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。

  扩充空间（不论多大）都应该这样做：

  （1）配置一块新空间

  （2）将旧元素一一搬往新址

  （3）把原来的空间释放还给系统

  注：vector 的数据安排以及操作方式，与array 非常相似。两者的唯一差别在于空间的利用的灵活性。Array 的扩充空间要程序员自己来写。

  插入	删除	访问
  push_back O(1)	pop_back O(1)	O(1)
  insert O(n)	erase O(n)

• deque

  连续存储结构，即其每个元素在内存上也是连续的，类似于vector，不同之处在于， deque提供了两级数组结构， 第一级完全类似于vector，代表实际容器；另一级维护容器的首位地址。这样，deque除了具有vector的所有功能外， 还支持高效的首/尾端插入/删除操作。

  deque是在功能上合并了vector和list。

  优点：

  1. 随机访问方便，即支持[ ]操作符和vector.at()

  2. 在内部方便的进行插入和删除操作

  3. 可在两端进行push、pop

  缺点：占用内存多

  使用区别：

  （1）如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector

  （2）如果你需要大量的插入和删除，而不关心随机存取，则应使用list

  （3）如果你需要随机存取，而且关心两端数据的插入和删除，则应使用deque

  插入	删除	访问
  push_front O(1)	pop_front O(1)	O(1)
  push_back O(1)	pop_back O(1)
  insert O(n)	erase O(n)

• list

  非连续存储结构，具有双链表结构，每个元素维护一对前向和后向指针，因此支持前向/后向遍历。 支持高效的随机插入/删除操作，但随机访问效率低下，且由于需要额外维护指针 ，开销也比较大。每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。

  优点：

  1. 不使用连续内存完成动态操作。

  2. 在内部方便的进行插入和删除操作

  3. 可在两端进行push、pop

  缺点：

  1. 不能进行内部的随机访问，即不支持[ ]操作符和vector.at()

  2. 相对于verctor占用内存多

  使用区别：

  （1）如果你需要高效的随即存取，而不在乎插入和删除的效率，使用vector

  （2）如果你需要大量的插入和删除，而不关心随机存取，则应使用list

  （3）如果你需要随机存取，而且关心两端数据的插入和删除，则应使用deque |插入|删除|访问| |--|--|--| |push_front O(1)|pop_front O(1)|O(n)| |push_back O(1)|pop_back O(1)|| |insert O(1)|erase O(1)||

1.1 初始化

vector<int> numbers;

vector<int> numbers(10, 1);

int arr[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> numbers(arr, arr + 10);

vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

1.2 Traverse

// 2.1、使用下标进行遍历(要求容器必须是支持下标访问的，list不支持下标，所以就不适用)
for(size_t idx = 0; idx != numbers.size(); ++idx)
{
    cout << numbers[idx] << " ";
}
cout << endl;
// 2.2、使用迭代器进行遍历
vector<int>::iterator it;  // 或者使用常量迭代器vector<int>::const_iterator it
for(it = numbers.begin(); it != numbers.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
// 2.3、使用auto加迭代器
auto it = numbers.begin();
for(; it != numbers.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
// 2.4、使用for加上auto进行遍历
for(auto &elem : numbers)
{
cout << elem << " ";
}
cout << endl;

1.3 头部插入删除

push_back
pop_backt

1.4 尾部插入删除

Note: vector is unavailable

push_front
pop_front

1.5 中间插入

//5.1、直接在某个位置插入一个元素
iterator insert( iterator pos, const T& value );
iterator insert( const_iterator pos, const T& value );
numbers.insert(it, 22);
//5.2、直接在某个位置插入count个元素
void insert(iterator pos, size_type count, const T& value)
iterator insert(const_iterator pos, size_type count, const T& value)
numbers.insert(it1, 4, 44);
//5.3、直接在某个位置插入迭代器范围的元素
template<class InputIt> void insert(iterator pos, InputIt first, InputIt
last)
template<class InputIt> iterator insert(const_iterator pos, InputIt first,
InputIt last)
vector<int> vec{51, 52, 53, 54, 55, 56, 57, 58, 59};
numbers.insert(it, vec.begin(), vec.end());
//5.4、插入一个大括号范围的元素
iterator insert(const_iterator pos, std::initializer_list<T> ilist)
numbers.insert(it, std::initialiser_list<int>{1, 2, 3});

insert导致迭代器失效

//在中间插入的时候，迭代器可能会失效，如果在去操作可能发生段错误
//因为push_back每次只会插入一个，所以可以按照统一的形式2 * size()
//但是insert的时候，插入的元素的个数不定的，所以就不能一概而论
//capacity() = n, size() = t, insert的时候，插入的元素个数为m
//1、m < n - t,这个时候就没有扩容，所以直接插入
//2、n - t < m < t,就按照t的2倍去进行扩容，新的空间就是2 * t
//3、n - t < m < n 且m > t,就按照 t + m去进行扩容
//4、m > n时，就按照t + m去进行扩容
void test()
{
    vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};//3、大括号形式
    display(numbers);
    cout << "numbers.size() = " << numbers.size() << endl;
    cout << "numbers.capacity() = " << numbers.capacity() << endl;
    cout << endl << "在容器尾部进行插入: " << endl;
    numbers.push_back(10);
    numbers.push_back(11);
    display(numbers);
    cout << "numbers.size() = " << numbers.size() << endl;
    cout << "numbers.capacity() = " << numbers.capacity() << endl;
    cout << endl << "在容器尾部进行删除: " << endl;
    numbers.pop_back();
    display(numbers);
    cout << endl << "在容器vector中间进行插入: " << endl;
    auto it = numbers.begin();
    ++it;
    ++it;
    numbers.insert(it, 22);
    display(numbers);
    cout << "*it = " << *it << endl;
    cout << "numbers.size() = " << numbers.size() << endl;
    cout << "numbers.capacity() = " << numbers.capacity() << endl;
    numbers.insert(it, 4, 44);//根据插入个数，进行分类扩容
    display(numbers);
    cout << "*it = " << *it << endl;
    cout << "numbers.size() = " << numbers.size() << endl;
    cout << "numbers.capacity() = " << numbers.capacity() << endl;
    //正确办法是重置迭代器的位置
    vector<int> vec{51, 52, 53};
    auto it1 = numbers.begin();
    ++it1;
    ++it1;
    numbers.insert(it1, vec.begin(), vec.end());
    display(numbers);
    cout << "*it1 = " << *it1 << endl;
    cout << "numbers.size() = " << numbers.size() << endl;
    cout << "numbers.capacity() = " << numbers.capacity() << endl;
}

1.6 删除元素

iterator erase(iterator position);
iterator erase(iterator first, iterator last);
//错误的用法：error
vector<int> vec;
for (int i = 0; i < 10; ++i)
{
    vec.push_back(i);
}
//删除不彻底，不能把连续的相同值删除
for (vector<int>::iterator it = vec.begin(); it != vec.end(); ++it)
{
    if(1 == *it) {
        vec.erase(it);
    }
}
//正确的用法：ok
vector<int> vec;
for (int i = 0; i < 10; ++i)
{
    vec.push_back(i);
}
vec.push_back(1);
vec.push_back(1);
vec.push_back(1);
vec.push_back(1);
//因为删除之后元素会移动，直接把迭代器的变化放在else语句中
for (auto it = vec.begin(); it != vec.end();)
{
    if (1 == *it) {
        it = vec.erase(it);
    }
    else {
        ++it;
    }
}