Vector容器

简要说明及其定义

vector是stl中最常用的容器之一，和array非常相似，但vector实现的是可以插入删除的动态数组，且会自动调整所占用的内存空间，而array只是静态的，容量固定的数组

vector被称为向量容器，在尾部插入和删除元素效率很高，而下头部或中部插入删除的话效率稍低，定义时需要引用头文件< vector >，如下：

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

以上生成了一个空的vector容器，因为没有元素，所以也并没有分配空间，当添加第一个元素时，vector会自动分配内存

同样也可以在创建的同时指定初始值以及元素个数，比如：

vector<int> value{2,3,4,5,7};

如上，创建了一个有5个元素的vector容器

或者是直接指定元素个数，所有默认初始值都为0,也可以自行赋值

vector<double> values(20,1.0);

如上创建了一个含20个double类型的数据的vector容器，并且设定的初始值都为1.0

另外，圆括号中的两个参数都可以用变量代替，而且存储元素类型相同的vector容器也可以用于创建新的vector容器（复制的方式）：

int num=20;
double value =1.0;
std::vector<double> values(num, value);
vector<char>value1(5, 'c');
vector<char>value2(value1);

在此基础上，如果不想复制其他容器中所有的内容，可以用指针或迭代器来指定初始值的范围：

int array[]={1,2,3};
std::vector<int>values(array, array+2);	//values 将保存{1,2}
std::vector<int>value1{1,2,3,4,5};
std::vector<int>value2(std::begin(value1),std::begin(value1)+3);	//新创建的value2包含{1,2,3}这3个元素

由于vector的类模板也位于命名空间std，所以当默认空间为std时，前面表示作用域的std::可以省略（上述已经省略）


容器提供的成员函数

头文件< vector >中也封装并提供了可供使用的成员函数：

函数成员 函数功能
size() 返回实际元素个数
max_size() 返回元素个数的最大值。这通常是一个很大的值，一般是 2^32-1，所以我们很少会用到这个函数
resize() 改变实际元素的个数
capacity() 返回当前容量
empty() 判断容器中是否有元素，若无元素，则返回 true；反之，返回 false
reserve() 增加容器的容量
shrink _to_fit() 将内存减少到等于当前元素实际所使用的大小
operator[ ] 重载了 [ ] 运算符，可以向访问数组中元素那样，通过下标即可访问甚至修改 vector 容器中的元素
at() 使用经过边界检查的索引访问元素
front() 返回第一个元素的引用
back() 返回最后一个元素的引用
data() 返回指向容器中第一个元素的指针
assign() 用新元素替换原有内容
push_back() 在序列的尾部添加一个元素
pop_back() 移出序列尾部的元素
insert() 在指定的位置插入一个或多个元素
erase() 移出一个元素或一段元素
clear() 移出所有的元素，容器大小变为 0
swap() 交换两个容器的所有元素
emplace() 在指定的位置直接生成一个元素
emplace_back() 在序列尾部生成一个元素

vector容器迭代器

vector容器的迭代器也是随机访问迭代器，并且vector模板类提供的操作迭代器的成员函数也和array一样

成员函数 功能
begin() 返回指向容器中首元素的正向迭代器
end() 返回指向容器”尾元素+1“的正向迭代器，此函数通常和 begin() 搭配使用。
rbegin() 返回指向尾元素的反向迭代器
rend() 返回指向“首元素-1”的反向迭代器，通常和 rbegin() 搭配使用。
cbegin() 和 begin() 功能类似，返回的迭代器类型为常量正向迭代器，不能用于修改元素
cend() 和 end() 功能相同，返回的迭代器类型为常量正向迭代器，不能用于修改元素
crbegin() 和 rbegin() 功能相同，返回的迭代器类型为常量反向迭代器，不能用于修改元素
crend() 和 rend() 功能相同，返回的迭代器类型为常量反向迭代器，不能用于修改元素

此外，c++11新增的begin（）和end（）全局函数也同样适用，和表中的两个同名成员函数作用相同

vector迭代器的特点

vector容器可以随存储元素的增加，自行申请更多的存储空间，故而创建一个空的vector容器并不会影响该容器后续的使用

但在初始化空的vector时，不能使用迭代器（没有存储数据的容器是没有分配存储空间的，也就没有指向这个空间的指针），因为对于空的vector容器来说，begin（）和end（）成员函数返回的迭代器是相同的，可以看做指针指向同一个位置

故而，因为创建的vector容器values为空，没有分配存储空间，使用迭代器初始化不成功，如下代码将没有输出

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int>values;
    int val = 1;
    for (auto first = values.begin(); first < values.end(); ++first, val++) {
        *first = val;
        cout << *first;	//初始化的同时输出值
    }
    return 0;
}

对于空的vector容器来说，可以通过调用push_back()或者借助resize()成员函数实现初始化容器的目的

此外，vector容器在申请更多内存时，容器中的所有元素可能会被复制或移动到新的内存地址，会导致之前创建的迭代器失效

如下，values 容器在增加容量之后，元素的存储地址发生了改变，此时再使用先前创建的迭代器，显然是错误的

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int>values{1,2,3};
    cout << "values 容器首个元素的地址：" << values.data() << endl;
    auto first = values.begin();
    auto end = values.end();
    values.reserve(20);	//增加 values 的容量
    cout << "values 容器首个元素的地址：" << values.data() << endl;
    while (first != end) {
        cout << *first;
        ++first;
    }
    return 0;
}

程序将在输出以下结果后崩溃：

values 容器首个元素的地址：0096DFE8

values 容器首个元素的地址：00965560

为了保险起见，每当 vector 容器的容量发生变化时，我们都要对之前创建的迭代器重新初始化一遍，修改的部分代码如下：

cout << "values 容器首个元素的地址：" << values.data() << endl;
first = values.begin();
end = values.end();
while (first != end) {
    cout << *first ;
    ++first;
}

运行结果：

values 容器首个元素的地址：0164DBE8

values 容器首个元素的地址：01645560

123

访问vector容器

单个元素

vector容器同样可以使用容器名[i]【因为有[]运算符重载，但该重载为了提高效率，同样没有设置边界检查操作】和at（）成员函数的方式获取容器中的元素的值，亦或是data（）成员函数【用于返回指向首个元素的指针】

除此之外，vector容器还提供两个成员函数，front（）可以返回第一个元素的引用，back（）返回最后一个元素的引用

多个元素

vector依旧有提供size（）成员函数作为循环结束的条件帮助完成容器遍历

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> values{1,2,3,4,5};
    //从下标 0 一直遍历到 size()-1 处
    for (int i = 0; i < values.size(); i++) {
        cout << values[i] << " ";
    }
    return 0;
}

注：size（）成员函数返回的是实际存储元素的个数，而capacity（）成员函数返回的是vector容器的总容积，两者有所差别

或者使用for(auto &c:s)完成基于范围的循环，配合begin（）成员函数和end（）成员函数成对使用也可以完成用vector迭代器对vector容器的遍历：

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> values{1,2,3,4,5};
    for (auto&& value : values)
        cout << value << " ";
    for (auto first=values.begin(); first<values.end(); ++first) 
    {
        cout << *first << " ";
    }
    return 0;
}

增加容器中的元素

从容器尾部添加

能够用于给容器添加元素的函数，在vector容器提供的成员函数中有两个，分别是push_back()和emplace_back()函数

push_back()和emplace_back()函数都是在vector容器尾部添加一个元素，用法如下：

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> values{};
    values.push_back(1);
    values.emplace_back(2);		//上下两行代码实现的效果相同
    for (int i = 0; i < values.size(); i++) {
        cout << values[i] << " ";
    }
    return 0;
}

如上，push_back()和emplace_back()函数的使用方法完全一样，看上去就像是直接替代而已

两者的区别在于底层实现的机制不同，push_back()会先随便创建一个元素m，然后将元素的值拷贝或移动到容器的元素n中，会多一个将元素m复制给n，然后析构m的过程，而emplace_back()则是直接在容器尾部创建元素n，故而后者的效率比前者高，但考虑到兼顾c++11标准以前的版本，前者也依然保留使用

从容器中间插入

在vector容器中的指定位置插入元素可以调用成员函数insert()和emplace()

insert()有四种语法格式：

语法格式 用法说明
insert（pos，elem） 在迭代器pos指定的位置之前插入一个新元素elem，返回表示新元素插入位置的迭代器
insert（pos，n，elem） 在迭代器pos指定的位置之前插入n个元素elem，并返回表示第一个新元素插入位置的迭代器
insert（pos，first，last） 在迭代器pos指定的位置之前，插入其他容器（不限于vector中位于[first，last）区域的所有元素，并返回第一个新元素插入位置的迭代器
insert（pos，initlist） 在迭代器pos指定的位置之前，插入初始化列表中的所有元素，并返回表示第一个新插入元素位置的迭代器

相较insert（），emplace（）是c++11标准新增加的成员函数，用于在vector中指定位置之前插入一个新的元素，函数声明如下：

iterator emplace(const_iterator pos,args……);

pos为指定插入位置的迭代器，args对应新插入元素构造函数的多个参数，返回值为新插入元素位置的迭代器

同push_back()和emplace_back()函数的关系一样，insert()和emplace()函数插入单个元素时效果是一样的，但emplace()是直接在指定位置构造元素，而不需要移动，所以效率比insert()高，但无法兼顾c++11标准前的编译器

删除容器中的元素

对于访问、添加、插入元素来说，都只能借助vector模板类提供的成员函数，但删除vector容器元素还可以借助一些全局函数

函数 功能
pop_back() 删除 vector 容器中最后一个元素，该容器的size减1，capacity不变
erase(pos) 删除 vector 容器中 pos 迭代器指定位置处的元素，并返回指向被删除元素下一个位置元素的迭代器【会将删除位置后续的元素陆续前移】，该容器的size减1，capacity不变
swap(begin)、pop_back() 先调用 swap()函数【需要引入头文件algorithm或者utility】交换要删除的目标元素和容器最后一个元素的位置，然后使用 pop_back() 删除该目标元素，容器中元素顺序会被打乱
erase(begin,end) 删除 vector 容器中位于迭代器 [begin,end)指定区域内的所有元素，并返回指向被删除的下一个位置元素的迭代器【会将删除位置后续的元素陆续前移】，该容器的size减1，capacity不变
remove() 删除容器中所有和指定元素值相等的元素【需要引用头文件algorithm】，并返回指向最后一个元素下一个位置的迭代器，由于该容器的size和capacity均不变，所以遍历需要借助remove()返回的迭代器，否则可能溢出
clear() 删除 vector 容器中所有的元素，使其变成空的 vector 容器。该容器的size减为0，capacity不变

remove()函数删除掉容器中多个指定元素后，容器大小和容量都没有改变，其剩余位置还保留了之前存储的元素，这些无用的元素可以用erase()删除，故此，remove()用于删除容器中指定元素时，常和 erase() 成员函数搭配使用,如下:

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
    vector<int>demo{ 1,3,3,4,3,5 };
    auto iter = std::remove(demo.begin(), demo.end(), 3);	//交换要删除元素和最后一个元素的位置
    demo.erase(iter, demo.end());
    cout << "size is :" << demo.size() << endl;
    cout << "capacity is :" << demo.capacity() << endl;
    for (int i = 0; i < demo.size();i++) {
        cout << demo[i] << " ";	//输出剩余的元素
    }
    return 0;
}

输出结果为：

size is :3
capacity is :6
1 4 5

容器扩容问题

vector容器本身是动态存储的，而多数stl版本中vector容器的自动扩容后容量都会提高到原来的两倍，然后将存储的所有元素按序复制到新的存储空间中，并析构以前存储的元素，释放旧的存储空间，由此可知，整个过程是十分耗时的

故而，虽然vector容器在增添新元素且容量不足时会自动扩容，但考虑到程序效率，还是应该在创建后用reverse()函数设定元素容量为足够大，尽可能避免在原有存储空间已满的情况下还添加新元素，以免vector容器进行不必要的扩容

vector< bool >

vector< bool >并不是存储bool类型的vector容器，和普通vector< T >模板的底层实现是不一样的，被特殊处理过，存储单位是bit而不是常用的byte

由于其特殊性，vector< bool >不能支持一些容器该有的基本操作，一般来说尽可能避免使用vector< bool >，取而代之的是，可以使用deque< bool >来取代，两者功能基本相同

总结

  • vector<数据类型> 容器名{每个元素的值}；
  • vector<数据类型> 容器名(数据个数，初始值)；【参数可省】
  • vector<数据类型> 容器名(另一个vector容器)；
  • vector<数据类型> 容器名(首地址，尾地址)；

  • begin（）/end（）：返回“开头/结尾+1”处的元素的正向迭代器

  • 前加r：返回“开头-1/结尾”的反向迭代器——rbegin（）/rend（）

  • 前加c：返回const类型的元素迭代器——cbegin()/cend(),crbegin()/crend()

  • 初始化空的vector时，不可以使用迭代器
  • 在申请更多内存时，容器中元素存储地址可能被更新，造成之前创建的迭代器失效

对于单个元素：

  • 用容器名[i]的方式——直接访问，性能最高
  • 使用at()函数——可避免越界
  • 使用front()和back()函数——返回第一个/最后一个元素的引用
  • 使用data()函数获得指向第一个元素的指针——用*（a+i）读取第i个元素

对于多个元素：

  • 使用size（）函数作为条件循环获取
  • 使用for（auto &c:s）这一特殊格式的for循环完成遍历赋值，只读时不加“&”引用符
  • 增添元素：insert()、push_front()、push_back
  • 对应的emplace系列：emplace()、emplace_front()、emplace_back()
  • 删除元素：
    • pop_back()【删除最后一个元素】
    • erase()【删除一部分，后续前移】
    • clear()【清空容器】
    • remove()【删除和指定值相等的元素】
  • vector容器虽然能够自动扩容，但耗时较多，应该用reverse（）函数修改容量而避免不必要的自动扩容
  • vector< bool >不是存储bool类型的vector容器，不支持基本操作，可以使用deque< bool >替代

代码实例

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<char>value;	//初始化一个空vector容量
    value.push_back('S');
    value.push_back('T');
    value.push_back('L');	//向value容器中的尾部依次添加 S、T、L 字符
    printf("元素个数为：%d\n", value.size());//调用 size() 成员函数容器中的元素个数
    for (auto i = value.begin(); i < value.end(); i++) 	//使用迭代器遍历容器
    {
        cout << *i << " ";
    }
    cout << endl;	
    value.insert(value.begin(), 'C');	//向容器开头插入字符
    cout << "首个元素为：" << value.at(0) << endl;
    return 0;
}

输出结果为：

元素个数为：3

S T L

首个元素为：C

#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int>values{1,2,3,4,5};
    auto first = values.begin();
    auto end = values.end();
    while (first != end)
    {
        cout << *first << " ";
        ++first;
    }
    return 0;
}

输出结果为：

1 2 3 4 5