vector知识

Vector

做CF1574D的勾八题时候并不会用trie树，于是点开了tourist的代码开始研究，发现字里行间写满了vector，就搞一搞vector的知识，cpp primer和primer plus都看的费劲，随便整点把

基础知识

vector可以理解为变长数组，它的内部实现基于倍增思想。按照下列思路可以大致实现一个vector：设n，m为vector的实际长度和最大长度。向vector加入元素前，若n=m，则在内存中申请2m的连续空间，并把内容转移到新的地址上，同时释放旧的空间，在执行插入。从vector中删除元素后，若n<=m4，则释放一半的空间
vector支持随机访问，对于任意的下标 (0 leq i < n)

#include <bits/stdc++.h>
using namespace std;

vector <int> a, b, c;

void init() {
    int n;
    a.resize(n, -1);
    b.resize(n, 0);
    c.resize(n, numeric_limits<int>::max());
    // numeric_litmits<int>::max()为编译器支持的int类型的最大数据
}

int main() {
    vector <int> tmp = {1, 2, 3, 4, 5}; //c++98应该不支持{...}声明
    for (int i = 0; i < 10; i++) {
        tmp.push_back(i);
    }
    
    // vector可以用以下这三种方式遍历
    vector <int>::iterator it;
    for (it = tmp.begin(); it != tmp.end(); it++) {
        cerr << *it << ' ';
    }
    cerr << '
';
    
    for (int i = 0; i < tmp.size(); i++) { // 使用小于号的原因：c++大部分容器都是左闭右开的
        cerr << a[i] << ' ';
    }
    cerr << '
';
    
    for (auto it : tmp) {
        cerr << tmp[it] << ' ';
    }
    cerr << '
';
    
    vector <int> arr(10, -1); // initialize an array of 10 -1
    arr.resize(5, 0); // resize the vector
    cout << arr.size() << ' ' << typeid(arr.size()).name() << endl;
    for (int i = 0; i < (int)arr.size(); i++) {
        cout << arr[i] << ' ';
    }

    /* arr.erase(arr.begin() + 3, arr.end()); delete all the element after the third element */
    sort (arr.begin(), arr.end());
    cerr << (int)(unique(arr.begin(), arr.end())-arr.begin()) << '
';
    arr.erase(unique(arr.begin(), arr.end()), arr.end());
    return 0;
}