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

向量(Vector)是一个封装了动态大小数组的顺序容器(Sequence container)。跟任意其它类型容器一样,它能够存放各种类型的对象。可以简单的认为,向量是一个能够存放任意类型的动态数组。

A vector is a sequence container that supports random access iterators.

C++编程语言国际标准:ISO/IEC 14882:2011

容性特性

顺序序列

顺序容器中的元素按照严格的线性顺序排序。可以通过元素在序列中的位置访问对应的元素。

动态数组

支持对序列中的任意元素进行快速直接访问,甚至可以通过指针算述进行该操作。操供了在序列末尾相对快速地添加/删除元素的操作。

能够感知内存分配器的(Allocator-aware)

容器使用一个内存分配器对象来动态地处理它的存储需求。

  • T

    存储在容器中的元素的数据类型。

    必须保证在执行移动操作时不会抛出异常,因为在重分配时,实现者(标准库内部)可以进行优化使仅仅移动元素而不是拷贝所有。

    在类模板内部,使用其别名为 value_type 的成员类型。

    Alloc

    容器内部用来管理内存分配及释放的内存分配器的类型。

    这个参数是可选的,它的默认值是 std::allocator<T>,这个是一个最简单的非值依赖的(Value-independent)内存分配器。在类模板内部,使用其别名为 allocator_type 的成员类型。

  • 在向量中,所有元素都是连续存储的。也就是说,不仅可以通过迭代器(Iterators)访问各个元素,也可以通过指向元素的指针加上偏移来访问。还意味着,当向任意函数传递向量的一个元素的指针时,这个指针可以直接被认为指向了一个数组中的某个元素。

    The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size().

    C++编程语言国际标准:ISO/IEC 14882:2011

    向量内部的存储调整是自动处理的,按需扩展或压缩。通常,相比静态数组(Static arrays),向量将会占用更多的存储空间,因为额外的内存将被未来增长的部分所使用。就因为这点,当插入元素时,向量不需要太频繁地重分配(Reallocate)内存。当前最大容量可以通过函数 capacity() 查询。额外的内存可以通过调用 shrink_to_fit() 函数返还给操作系统。

    Storage management is handled automatically, though hints can be given to improve efficiency.

    C++编程语言国际标准:ISO/IEC 14882:2011

    当增加向量对象中的序列的长度时,如果超出当前存储容量上限,就会发生内存重分配(Reallocation),即内部将会重新分配一个数组,然后按顺序逐个拷贝元素。其它的插入及删除操作将会修改序列中部分元素的内存地址。在上述所有情况下,指向序列中被修改部分的迭代器或引用将会失效。当未发生内存重分配,仅指向插入或删除点之前元素的迭代器或引用才会保持有效性。

    标准库可以执行不同的增长策略来平衡内存的使用量与重分配所耗的性能。但不管哪种情况下,重分配内存的大小必须以指数方式增长,只有这样,才能将在向量末尾逐个插入元素所需的时间复杂度整体分摊(Amortized)为一个恒定值。

    内存重分配就性能而言是一个高代价操作。如果在使用向量前知道元素的数量,可以通过 reserve() 消除内存重分配。

    向量支持在序列末尾恒定耗时的插入及删除元素。而在向量的中间插入或删除元素则需要线性的时间。在只涉及向序列起始或未尾插入及删除元素操作时,std::deque​ 容器的性能将会高出很多。当涉及向序列中的任意位置进行插入及删除操作时,std::list 容器的性能将会高出很多。

    In addition, it supports (amortized) constant time insert and erase operations at the end; insert and erase in the middle take linear time.

    C++编程语言国际标准:ISO/IEC 14882:2011

    常用操作的算法复杂度(性能相关)如下:

    • 随机访问,时间复杂度为 O(1)
    • 在未尾插入或删除元素,整体分摊的时间复杂度为 O(1)
    • 其它位置插入或删除元素,与当前位置至向量末尾的距离有关,时间复杂度 O(n)​​
  • 成员类型 定义
    value_type 第一个模板参数 T
    allocator_type 第二个模板参数 Alloc
    size_type 无符号整数类型(通常为 size_t
    difference_type 有符号整数类型(通常为 ptrdiff_t
    reference Allocator::reference 已弃用
    value_type& C++11
    const_reference Allocator::const_reference 已弃用
    const value_type& C++11
    pointer Allocator::pointer 已弃用
    std::allocator_traits<Allocator>::pointer C++11
    const_pointer Allocator::const_pointer 已弃用
    std::allocator_traits<Allocator>::const_pointer C++11
    iterator 随机访问迭代器
    const_iterator 常量随机访问迭代器
    reverse_iterator std::reverse_iterator<iterator>
    const_reverse_iterator std::reverse_iterator<const_iterator>
  • (constructor) 创建 vector
    (destructor) 释放 vector
    operator= 值赋操作

    ​Iterators:

    begin 返回指向容器起始位置的迭代器(iterator
    end 返回指向容器末尾位置的迭代器
    rbegin 返回指向容器逆序起始位置的逆序迭代器(reverse_iterator
    rend 返回指向容器逆序末尾位置的逆序迭代器
    cbegin C++11 返回指向容器起始位置的常迭代器(const_iterator
    cend C++11 返回指向容器末尾位置的常迭代器
    crbegin C++11 返回指向容器逆序起始位置的常逆序迭代器(const_reverse_iterator
    crend C++11 返回指向容器逆序末尾位置的常逆序迭代器

    Capacity:

    size 返回有效元素个数
    max_size 返回 vector 支持的最大元素个数
    resize 改变有效元素的个数
    capacity 返回当前可使用的最大元素内存块数(即存储容量)
    empty 判断是否为空
    reserve 请求改变存储容量
    shrink_to_fit C++11 请求移除未使用的存储空间

    Element access:

    operator[] 访问元素
    at 访问元素
    front 访问第一个元素
    back 访问最后一个元素
    data C++11 返回当前向量内部数组的指针

    Modifiers:

    assign 将新的内容赋值给容器
    push_back 在末尾增加一个元素
    pop_back 删除最后一个元素
    insert 插入元素
    erase 删除元素
    swap 交换内容
    clear 清空内容
    emplace C++11 构造及插入一个元素
    emplace_back C++11 在容器末尾构造及插入一个元素

    Allocator:

    get_allocator 获得内存分配器
  • operator==、operator!=、operator<、operator<=、operator>、operator>= 

    关系操作符
    std::swap 交换两个向量的内容
  • std::vector<bool> 类是 std::vector 类模板以 bool 类型为元素类型的特例化。
  • <algorithm> 头文件中包含大量与 vector 相关的算法,常使用的有

    搜索算法std::adjacent_findstd::count
    std::count_ifstd::find
    std::find_ifstd::find_end
    std::find_first_ofstd::search
    std::search_nstd::equal
    std::mismatch
    分类排序std::sortstd::partial_sort
    std::stable_sort
    二分查找(Binary search)std::lower_boundstd::upper_bound
    std::equal_rangestd::binary_search
    集合(Set)操作std::includesstd::set_difference
    std::set_intersectionstd::set_union
    std::set_symmetric_difference
    堆(Heap)操作std::make_heapstd::push_heap
    std::pop_heapstd::sort_heap
    最大与最小std::min_elementstd::max_element
    字典序比较std::lexicographical_compare
    排列生成器std::next_permutation
    std::prev_permutation
    第n个元素std::nth_element
    其它操作std::all_ofstd::any_ofstd::none_of
    std::for_eachstd::copystd::copy_if
    std::copy_nstd::copy_backward
    std::movestd::move_backward
    std::swap_rangesstd::iter_swap
    std::transformstd::replace
    std::replace_ifstd::replace_copy
    std::replace_copy_ifstd::fill
    std::fill_nstd::generate
    std::generate_nstd::remove
    std::remove_ifstd::unique
    std::unique_copystd::reverse
    ​std::reverse_copystd::rotate
    std::rotate_copystd::random_shuffle
    std::shufflestd::partition
    std::is_partitionedstd::stable_partition
    std::partition_copystd::merge

    具体内容详见各个功能函数,还可以参考 vector 与算法 主题,该主题包含大量的代码示例

  • 注意!以下代码仅用于快速了解 vector,具体代码示例请查看各个成员函数或上章节提到的 vector与算法 主题。

    综合

    下面这个例子展示了大量与vector及标准库算法(Standard Library algorithms)相关的内容:随机移动、排序、找出最大元素、用擦除-移除(Erase-remove)语义删除元素等。

    #include <iostream>
    #include <vector>
    #include <algorithm> // sort, max_element, random_shuffle, remove_if, lower_bound 
    #include <functional> // greater, bind2nd
    
    // 用在此处是为了方便简洁, 在实际编程中慎用
    using namespace std;
     
    int main()
    {
        int arr[4] = {1, 2, 3, 4};
        // 用上述数组初始化向量
        vector<int> foo(arr, arr+4);
    
        // 插入更多的元素
        foo.push_back(5);
        foo.push_back(6);
        foo.push_back(7);
        foo.push_back(8);
    
        // 此时的向量内容为 {1, 2, 3, 4, 5, 6, 7, 8}
     
        // 随机移动元素
        random_shuffle( foo.begin(), foo.end() );
     
        // 定位最大的元素, O(n)
        vector<int>::const_iterator largest = 
            max_element( foo.begin(), foo.end() );
     
        cout << "当前最大元素是: " << *largest << "\n";
        cout << "它的索引位置是: " << largest - foo.begin() << "\n";
     
        // 排序元素
        sort( foo.begin(), foo.end() );
     
        // 用二分查找法找出向量中值为5的元素
        vector<int>::const_iterator five = 
            lower_bound( foo.begin(), foo.end(), 5 );
     
        cout << "值为5的元素的索引位置是: " << five - foo.begin() << "\n";
     
        // 删除所有值大于4的元素
        foo.erase( remove_if(foo.begin(), foo.end(), 
            bind2nd(greater<int>(), 4) ), foo.end() );
     
        // 打印所有剩余元素的值
        for(vector<int>::const_iterator it = foo.begin(); it != foo.end(); ++it)
        {
            cout << *it << " ";
        }
     
    	cout << "\n";
        return 0;
    }

    输出

    当前最大元素是: 8
    它的索引位置是: 6
    值为5的元素的索引位置是: 4
    1 2 3 4
    ​​

    字符串排序

    展示了三种访问 vector 中数据的方法。

    #include <iostream>
    #include <vector>
    #include <string>
     
    // 用在此处是为了方便简洁, 在实际编程中慎用
    using namespace std;
     
    int main()
    {
        vector<string> foo;
     
        foo.push_back("The number is 10");
        foo.push_back("The number is 20");
        foo.push_back("The number is 30");
     
        cout << "Loop by index:" << endl;
     
     
        for(vector<string>::size_type i=0; i < foo.size(); i++)
        {
            cout << foo[i] << endl;
        }
     
        cout << "Constant Iterator:" << endl;
     
        vector<string>::const_iterator cii;
        for(cii=foo.begin(); cii!=foo.end(); cii++)
        {
            cout << *cii << endl;
        }
     
        cout << "Reverse Iterator:" << endl;
     
        vector<string>::reverse_iterator rii;
        for(rii=foo.rbegin(); rii!=foo.rend(); ++rii)
        {
            cout << *rii << endl;
        }
     
        cout << "简单输出:" << endl;
     
        cout << foo.size() << endl;
        cout << foo[2] << endl;
     
        swap(foo[0], foo[2]);
        cout << foo[2] << endl;
    }

    输出

    Loop by index:
    The number is 10
    The number is 20
    The number is 30
    Constant Iterator:
    The number is 10
    The number is 20
    The number is 30
    Reverse Iterator:
    The number is 30
    The number is 20
    The number is 10
    简单输出:
    3
    The number is 30
    The number is 10

    vector 表示二维数组

    注意! vector< vector<int> > foo; 如果您使用的编译器版本较老,请务必在两个‘>'之间加一个空格,这是一个bug,最新编译器已经没有该问题。

    #include <iostream>
    #include <vector>
    
    // 用在此处是为了方便简洁, 在实际编程中慎用
    using namespace std;
    
    int main()
    {
        vector< vector<int> > foo; // Declare two dimensional array
        vector<int> A, B;
        vector< vector<int> >::iterator iter_ii;
        vector<int>::iterator iter_jj;
    
        A.push_back(10);
        A.push_back(20);
        A.push_back(30);
        B.push_back(100);
        B.push_back(200);
        B.push_back(300);
    
        foo.push_back(A);
        foo.push_back(B);
    
        cout << "使用迭代器打印二维向量:" << endl;
    
        for(iter_ii=foo.begin(); iter_ii!=foo.end(); iter_ii++)
        {
            for(iter_jj=(*iter_ii).begin(); iter_jj!=(*iter_ii).end(); iter_jj++)
            {
                cout << *iter_jj << endl;
            }
        }
    }

    输出:

    使用迭代器打印二维向量:
    10
    20
    30
    100
    200
    300

    对向量中的每个元素调用其成员函数

    相关函数有:

    std::for_eachstd::mem_fun
    std::mem_fun_refstd::bind2nd
    #include <iostream>
    #include <vector>
    #include <string>
    #include <algorithm>
    #include <functional>
    #include <sstream>
    
    namespace ClassFoo{
    using namespace std;
    class Person {
    private:
        std::string name;
        static int n;
    public:
        Person() {
            std::stringstream ss;
            std::string snum;
            ss << n++;
            ss >> snum;
            name = "foo" + snum;
        }
        void print () const {
            std::cout << name << std::endl;
        }
        void printWithPrefix (std::string prefix) const {
            std::cout << prefix << name << std::endl;
        }
    };
    
    int Person::n = 0;
    
    void foo (const std::vector<Person>& coll)
    {
        // 对每个元素对象调用成员函数 print()
        for_each (coll.begin(), coll.end(), mem_fun_ref(&Person::print));
    
        // 对每个元素对象调用成员函数 printWithPrefix()
        // - "person: " 作为参数传递给成员函数
        for_each (coll.begin(), coll.end(),
            bind2nd(mem_fun_ref(&Person::printWithPrefix),"person: "));
    }
    
    void ptrfoo (const std::vector<Person*>& coll)
    {
        // 对每个指针指向的元素对象调用成员函数 print()
        for_each (coll.begin(), coll.end(),
            mem_fun(&Person::print));
    
        // 对每个指针指向的元素对象调用成员函数 printWithPrefix()
        // - "person: " 作为参数传递给成员函数
        for_each (coll.begin(), coll.end(),
            bind2nd(mem_fun(&Person::printWithPrefix),"person: "));
    }
    
    }
    int main()
    {
        std::cout << "当向量的元素是对象时:" << std::endl;
        std::vector<ClassFoo::Person> coll(5);
        ClassFoo::foo(coll);
    
        std::cout << "当向量的元素是指向对象的指针时:" << std::endl;
        std::vector<ClassFoo::Person*> coll2;
        coll2.push_back(new ClassFoo::Person);
        coll2.push_back(new ClassFoo::Person);
        coll2.push_back(new ClassFoo::Person);
        coll2.push_back(new ClassFoo::Person);
        coll2.push_back(new ClassFoo::Person);
        ClassFoo::ptrfoo(coll2);
    }

    输出

    当向量的元素是对象时:
    foo0
    foo1
    foo2
    foo3
    foo4
    person: foo0
    person: foo1
    person: foo2
    person: foo3
    person: foo4
    当向量的元素是指向对象的指针时:
    foo5
    foo6
    foo7
    foo8
    foo9
    person: foo5
    person: foo6
    person: foo7
    person: foo8
    person: foo9

    一个有用的宏

    类似 C++11 标准中新增的初始化列表构造函数。

    #define CLASSFOO_VECTOR(type, name, ...) \
    static const type name##_a[] = __VA_ARGS__; \
    std::vector<type> name(name##_a, name##_a + sizeof(name##_a) / sizeof(*name##_a))

    可以这样使用:

    CLASSFOO_VECTOR(int,foo,{1,2,3,4,5,6,7});