[STL]vector

vector文档介绍

1. vector是表示可变大小数组的序列容器。
2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
6. 与其它动态序列容器相比（deques, lists and forward_lists）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起lists和forward_lists统一的迭代器和引用更好。

vector的基本使用

vector底层就是一个动态顺序表

vector的初始化

void test_vector1()
{
    
    vector<int> v1;
    vector<int> v2(10, 8); // 用10个8去初始化
    vector<int> v3(++v2.begin(), --v2.end()); // 用一个连续的迭代器区间去初始化
    vector<int> v4(v3);
    string s("hello world");
    vector<char> v5(s.begin(), s.end()); // 用一个
}

vector的三种遍历方式：

void test_vector2()
{
    
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    // 第一种遍历方式
    for (size_t i = 0; i < v.size(); ++i)
    {
    
        v[i] += 1;
        cout << v[i] << " ";
    }
    cout << endl;
    // 第二种遍历方式
    // 这个迭代器属于这个类模板里面的作用域里面
    vector<int>::iterator it = v.begin();
    while (it != v.end())
    {
    
        *it -= 1;
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    // 第三种遍历方式
    for (auto& e : v)
    {
    
        cout << e << " ";
    }
    cout << endl;
}

vector的扩容

void test_vector3()
{
    
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    cout << v.max_size() << endl;
    // reserve和resize的区别

    v.reserve(100); // 只扩容容量空间capacity
    v.resize(100); // 还会给数据，默认缺省值是0
    v.resize(100, 5); // 扩容+初始化 / 删除数据
    v.resize(2); // 会删除数据，但capacity不会更改

    v[3]; // 用断言检查是否超过size
    v.at(3); // 抛异常，非断言错误
}

补充

void test_vector4()
{
    
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    // assign可以进行赋值
    // 可以把之前的内容覆盖掉
    v.assign(10, 5);
}

assign覆盖之前：
assign覆盖之后：

Ctrl+f是搜索键的快捷键

algorithm算法库

可以在一个迭代器区间内进行查找，C++中所有的迭代器区间都是左闭右开[)

void test_vector4()
{
    
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    vector<int>::iterator ret = find(v.begin(), v.end(), 3); // 返回值也是一个迭代器
    // 如果没有找到返回end的位置，也是右区间
    if (ret != v.end())
    {
    
        cout << "找到了" << endl;
    }
}

头插

void test_vector4()
{
    
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    vector<int>::iterator ret = find(v.begin(), v.end(), 3); // 返回值也是一个迭代器
    // 如果没有找到返回end的位置，也是右区间
    if (ret != v.end())
    {
    
        cout << "找到了" << endl;
        // 想在3前插入30
        v.insert(ret, 30);
    }
    // 头插一个数据
    v.insert(v.begin(), -1);
    for (auto& e : v)
    {
    
        cout << e << " ";
    }
    cout << endl;
}

在这里还可能涉及一个问题：迭代器失效——后续讲解
删除一个值

void test_vector4()
{
    
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    vector<int>::iterator ret = find(v.begin(), v.end(), 3); 
    // 把3删除掉
    vector<int>::iterator pos = find(v.begin(), v.end(), 3);
    // 如果不判断直接删除——可能会出现问题（没有该值）
    if (pos != v.end())
    {
    
        v.erase(pos);
    }
    if (ret != v.end())
    {
    
        cout << "找到了" << endl;
        // 想在3前插入30
        v.insert(ret, 30);
        v.erase(ret); // 能否在这里删除？
        // 不行，因为可能insert之后迭代器会失效
    }
    for (auto& e : v)
    {
    
        cout << e << " ";
    }
    cout << endl;
}

void test_vector5()
{
    
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    v.push_back(4);
    v.clear(); // 将v的所有数据删除掉
    // 但不会清除空间
    for (auto& e : v)
    {
    
        cout << e << " ";
    }
    cout << endl;
}

vector如何增容？

在这里接近于1.5倍增容——向上取整，不是向下取整
比如1*1.5 = 1.5 向上取整结果就是2，向下取整结果就是1

size_t sz;
    std::vector<int> foo;
    sz = foo.capacity();
    std::cout << "making foo grow:\n";
    for (int i = 0; i < 100; ++i) {
    
        foo.push_back(i);
        if (sz != foo.capacity()) {
    
            sz = foo.capacity();
            std::cout << "capacity changed: " << sz << '\n';
        }
    }

二维数组

vector<vector<int>> w;

w[i]访问竖着的第i个位置，取到的是这个值的引用，这个值存的又是一个对象，返回的是一个vector的对象，然后w[i][j]又是一次函数调用，访问第j个位置的值
因此与c语言开辟的二维数组的区别在于：
vector是两次函数调用
c语言中是指针的解引用

void test_vector6()
{
    
    vector<vector<int>> vv;
    vv.resize(5);
}

这时候如何竖着的就开好了，如何让他每一行也初始化好数据？

void test_vector6()
{
    
    vector<vector<int>> vv;
    vv.resize(5);
    for (int i = 0; i < 5; ++i)
    {
    
        vv[i].resize(i + 1); // vv[i]又是一个对象，因此可以调用resize
    }
}

小小的拓展

    int j = int(); // 默认缺省值为0
    int k = int(10);

如何访问这个二维数组每一行的第一个数据和最后一个数据？

void test_vector6()
{
    
    vector<vector<int>> vv;
    vv.resize(5);
    for (int i = 0; i < 5; ++i)
    {
    
        vv[i].resize(i + 1); // vv[i]又是一个对象，因此可以调用resize
        vv[i][0] = vv[i][vv[i].size() - 1] = 1;
        // 等价于
        //vv[i].front() = vv[i].back() = 1;
    }
}

vector的使用场景
动态增长的顺序表，如果是定长的一般还是用数组