详解vector容器

vector是C++中使用非常频繁的一种顺序容器，它为对象提供了连续存储，即内存分布方式与传统的array相同。与array不同的是，vector容器内所包含对象的数量可以动态变化，容器自动管理内存的申请和释放，这给编程带来了极大的便利。

// 所有C++ STL容器都支持的接口
size  // 容器内对象的数量
clear // 清空容器，不改变capaticy
empty // 判断容器是否为空
// vector容器对象访问
operator[]  // 无边界检查，返回对象的reference
at          // 越界throw，返回对象的reference
front       // 第1个对象的reference
back        // 最后1个对象的reference
data        // 容器数据区array起始地址指针，
            // 当empty为true时，data不一定会返回nullptr！
// 迭代器
begin
cbegin
end
cend
rbegin
crbegin
rend
crend
//
max_size   // runtime时可能的最大size，
           // 这个size受到系统内存和STL实现的影响。
reserve    // 扩大capacity，不改变size；
           // 只有传入此接口的值比capacity大的时候，此接口才会发生作用；
           // 此时reallocation，所有的迭代器和引用都会失效。
           // vector容器会自动按指数方式增长capacity，
           // 注意调用reserve的时机和策略。
capacity   // 容器的容量
shrink_to_fit  // 释放容器多余的容量，让size==capacity。
//
push_back  // 在尾部添加对象，copy or move
emplace_back  // 在尾部创建对象，返回对象的ref。
pop_back   // 删除尾部对象，此接口无返回值。 
insert     // 在某个位置插入对象。
emplace    // 在某个位置创建对象。
erase      // 删除某个或某一段对象。
resize     // 强行调整size大小。
           // 如果入参比当前size小，只保留前面入参个数的对象，
           // 如果入参比当前size大，会在末尾创建出足够数量的对象，
           // 如果入参大于capacity，还会reallocation。
swap       // 交换两个vector容器的内容，
           // 此过程没有任何针对对象的copy，move或swap操作，速度很快。
           // std::swap(left,right)与left.swap(right)相同。
assign     // 替换原vector内的对象，就像生成一个新的vector，
           // 只是data的值可能不会变化，
           // 替换前后，对象的type要保持一致。

vector容器capacity的自动增长策略

写了一段测试代码，在Linux环境下用g++编译运行，发现vector容器capacity的自动增加策略是指数型的。

#include <iostream>
#include <vector>
using namespace std;

int main(void) {
    vector<int> a;
    cout << "size: " << a.size() << ", ";
    cout << "capacity: " << a.capacity() << ", ";
    cout << "data: " << a.data() << endl;

    cout << "--------\n";
    for(int i=0; i<33; ++i){
        a.push_back(i);
        cout << "size: " << a.size() << ", ";
        cout << "capacity: " << a.capacity() << ", ";
        cout << "data: " << a.data() << endl;
    }

    a.shrink_to_fit();
    cout << "after shrink_to_fit:" << endl;
    cout << "size: " << a.size() << ", ";
    cout << "capacity: " << a.capacity() << ", ";
    cout << "data: " << a.data() << endl;
    return 0;
}

size: 0, capacity: 0, data: 0
--------
size: 1, capacity: 1, data: 0x1cf32c0
size: 2, capacity: 2, data: 0x1cf32e0
size: 3, capacity: 4, data: 0x1cf32c0
size: 4, capacity: 4, data: 0x1cf32c0
size: 5, capacity: 8, data: 0x1cf3300
size: 6, capacity: 8, data: 0x1cf3300
size: 7, capacity: 8, data: 0x1cf3300
size: 8, capacity: 8, data: 0x1cf3300
size: 9, capacity: 16, data: 0x1cf3330
size: 10, capacity: 16, data: 0x1cf3330
size: 11, capacity: 16, data: 0x1cf3330
size: 12, capacity: 16, data: 0x1cf3330
size: 13, capacity: 16, data: 0x1cf3330
size: 14, capacity: 16, data: 0x1cf3330
size: 15, capacity: 16, data: 0x1cf3330
size: 16, capacity: 16, data: 0x1cf3330
size: 17, capacity: 32, data: 0x1cf3380
size: 18, capacity: 32, data: 0x1cf3380
size: 19, capacity: 32, data: 0x1cf3380
size: 20, capacity: 32, data: 0x1cf3380
size: 21, capacity: 32, data: 0x1cf3380
size: 22, capacity: 32, data: 0x1cf3380
size: 23, capacity: 32, data: 0x1cf3380
size: 24, capacity: 32, data: 0x1cf3380
size: 25, capacity: 32, data: 0x1cf3380
size: 26, capacity: 32, data: 0x1cf3380
size: 27, capacity: 32, data: 0x1cf3380
size: 28, capacity: 32, data: 0x1cf3380
size: 29, capacity: 32, data: 0x1cf3380
size: 30, capacity: 32, data: 0x1cf3380
size: 31, capacity: 32, data: 0x1cf3380
size: 32, capacity: 32, data: 0x1cf3380
size: 33, capacity: 64, data: 0x1cf3410
after shrink_to_fit:
size: 33, capacity: 33, data: 0x1cf3380

vector的括号初始化

由于vector容器支持initialization list。因此，用{}或()初始化有所不同，可编译器判别具体采用哪个constructor。

vector<int> v1(10);        // v1有10个元素，每个数的值都是0
vector<int> v2{10};        // v2有1个元素，值是10
vector<int> v3(10,1);      // v3有10个元素，每个数的值都是1
vector<int> v4{10,1};      // v4有2个元素，值分别是10和1

// since C++20
constexpr vector( std::initializer_list<T> init,
                  const Allocator& alloc = Allocator() );

但是，编译器也有一个fallback机制，即当初始化列表中的值与元素类型不匹配的时候：

vector<string> v6("hi");        // error
vector<string> v7{10};          // v7有10个元素，都是空string对象
vector<string> v8{10,"hi"};     // v8有10个元素，值都是"hi"

size和capacity很不一样

增加capacity的方式，不会增加size，访问元素需要有size！下面有问题的代码示例：

#include <vector>
#include <iostream>
using namespace std;


struct idx_num{
    int num;
    int idx;
};


int main(){
    vector<idx_num> inum;
    inum.reserve(8);

    // false initialization
    for(int i{}; i<8; ++i){
        inum[i].num = i*i;
        inum[i].idx = i;
    }

    // size is zero! :(
    cout << inum.size() << endl;

    // iteration ok
    for(int i{}; i<8; ++i)
        cout << inum[i].num << "[" << inum[i].idx << "]" << " ";
    cout << endl;

    return 0;
}

0
0[0] 1[1] 4[2] 9[3] 16[4] 25[5] 36[6] 49[7]

用reserve预留空间后，代码进行了错误的初始化，虽然输出的值都是对的，但是vector对象的size始终是0！这是把vector当成了传统的array使用了。可以将reserve替换成resize，这样size就正常了，后续代码就可以使用inum.size()来获取长度。

push_back和emplace_back的区别

// since C++20
constexpr void push_back( const T& value );
constexpr void push_back( T&& value );

template< class... Args >
constexpr reference emplace_back( Args&&... args );

因此，在某些情况下，使用emplace_back会有一些性能上的好处。如果对象没有可以使用的constructor，就只能走push_back。

#include <vector>
#include <iostream>
using namespace std;


struct xyz{
    int a;
    int b;
    xyz(int a, int b): a{a},b{b} {}
};


int main(){
    vector<xyz> x;

    // emplace_back needs to call ctor!
    for(int i{}; i<8; ++i)
        //x.push_back(xyz{i,i*i});  // ok
        //x.push_back({i,i*i});     // ok
        x.emplace_back(i, i*i);     // call constructor

    cout << x.size() << endl;

    for(size_t i{}; i<x.size(); ++i)
        cout << x[i].a << " " << x[i].b << endl;

    return 0;
}

快速swap

交换两个相同类型的vector，调用swap接口，是非常快的。这个swap，其实就是将两个vector容器的metadata做了一些修改，内部数据都没有任何变化。

#include <vector>
#include <iostream>
using namespace std;


void print_vector(vector<int> &a){
    for(size_t i{}; i<a.size(); ++i)
        cout << a[i] << " ";
    cout << endl;
}


int main(){
    vector<int> x {1,2,3,4};
    vector<int> y {5,6,7,8};

    cout << "x.data(): " << x.data() << endl;
    cout << "y.data(): " << y.data() << endl;
    //x.swap(y);
    std::swap(x,y);

    print_vector(x);
    print_vector(y);
    cout << "x.data(): " << x.data() << endl;
    cout << "y.data(): " << y.data() << endl;

    return 0;
}

x.data(): 0xb5deb0
y.data(): 0xb5ded0
5 6 7 8
1 2 3 4
x.data(): 0xb5ded0
y.data(): 0xb5deb0

copy和move

vector容器所体现出来的copy和move规则，应该适用所有标准C++容器。

#include <vector>
#include <iostream>
using namespace std;

void print_vector(vector<int> &a){
    for(size_t i{}; i<a.size(); ++i)
        cout << a[i] << " ";
    cout << endl;
}

int main(){
    vector<int> x {1,2,3,4};
    vector<int> y {x};  // copy constructor
    vector<int> z {5,6,7,8,9,0};
    z = x;              // copy assignment, clear original data
    vector<int> m {5,6,7,8,9,0};
    m = std::move(x);   // move assignment, clear original data

    print_vector(x);
    print_vector(y);
    print_vector(z);
    print_vector(m);
    cout << "x.data(): " << x.data() << endl;
    cout << "y.data(): " << y.data() << endl;
    cout << "z.data(): " << z.data() << endl;
    cout << "m.data(): " << m.data() << endl;

    return 0;
}

1 2 3 4
1 2 3 4
1 2 3 4
x.data(): 0
y.data(): 0x1adfed0
z.data(): 0x1adfef0
m.data(): 0x1adfeb0

实际上，以上代码两处的copy，都是调用对象的copy constructor/assignment。下面这个示例更清楚：

#include <vector>
#include <iostream>
using namespace std;

struct xyz{
    int a;
    xyz(int a):a{a} {}
    xyz(const xyz &x){
        cout << "copy constructor.." << x.a << endl;
        a = x.a;
    }
    xyz& operator =(const xyz &x){
        if(this == &x)
            return *this;
        cout << "assign constructor.." << x.a << endl;
        a = x.a;
        return *this;
    }
};

int main(){
    vector<xyz> x;
    x.reserve(4);
    x.emplace_back(1);
    x.emplace_back(2);
    x.emplace_back(3);
    x.emplace_back(4);

    cout << "create y:\n";
    vector<xyz> y {x};
    cout << "create z:\n";
    vector<xyz> z {5,6,7,8,9,0};
    cout << "assign z:\n";
    z = x;

    cout << "read z:\n";
    for(size_t i{}; i<z.size(); ++i)
        cout << z[i].a << " ";
    cout << endl;

    return 0;
}

create y:
copy constructor..1
copy constructor..2
copy constructor..3
copy constructor..4
create z:
copy constructor..5
copy constructor..6
copy constructor..7
copy constructor..8
copy constructor..9
copy constructor..0
assign z:
assign constructor..1
assign constructor..2
assign constructor..3
assign constructor..4
read z:
1 2 3 4