E

EdwardWong

V1

2022/11/25阅读:45主题:姹紫

STL序列式容器之vector

vector容器和array容器非常相似,都可以看作是对C++普通数组的升级版,不同的是array实现的是静态数组(容量固定的数组),而vector实现的是一个动态数组,既可以进行元素的插入和删除​。

vector容器(向量容器)会动态调整所占用的内存空间​,该容器擅长在尾部插入或删除元素,在O(1)的时间内可以完成;而在容器头部或其他位置插入或删除元素,则花费的时间为O(n)

vector容器以类模板vector<T>的形式定义在<vector>头文件中,并位于std命名空间中​。 在创建容器之前,需要在代码中包含​以下内容:

#include<vector>
using namespace std;

创建vector容器的几种方式

创建空的vector容器

std::vector<double> values;

因为容器中没有元素,所以没有为其分配空间,当添加第一个元素(例如push_back()函数)时,vector会自动分配内存。

在创建好空容器后,还可以调用reserve()成员函数来增加容器的容量

values.reserve(20);

这样就设置了容器的内存分配,即至少可以容纳20个元素,注意如果vector容器在执行此语句之前已经大于或者等于20个元素时,这条语句什么也不做,另外,**reserve()不会影响已存储的元素,也不会生成任何元素,即values容器此时仍然没有任何元素**。

如果调用reserve()来增加容器容量,之前创建好的任何迭代器可能会失效,这是因为为了增加容器的容量,vector<T>容器的元素可能已经被复制或移动到新的内存地址,后续使用这些迭代器时,最好重新生成一下。

在创建的同时指定初始值及元素个数

std::vector<int> primes{2,3,5,7,11,13,17,19} 这样就创建了一个含有8个素数的vector容器。

创建vector容器时,也可以指定元素个数

std::vector<double> values(20);

这样values容器就有20个元素,他们的默认初始值都为0

注意()与{}的区别,()表示元素的个数,{}表示vector容器中的元素

std::vector<double> values(20,1.0);

第二个参数指定了所有元素的初始值,因此这20个元素的值都是1.0

通过其他vector容器创建新的vector容器

std::vector<char> value1(5,'c');

std::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},是左闭右开空间。

vector容器包含的成员函数

C++11标准库还新增加了begin()end()这两个函数,和vector容器包含的begin()end()成员函数不同,标准库提供的函数既可以是容器,也可以是普通数组。当操作对象是容器时,它和容器包含的begin()end()成员函数的功能完全相同;如果操作对象是普通数组,则begin()函数返回的是指向数组第一个元素的指针,同样的,end()`函数返回的是指向数组中最后一个元素之后一个位置的指针。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
//初始化一个空vector容量
vector<char>value;
//向value容器中的尾部依次添加 S、T、L 字符
value.push_back('S');
value.push_back('T');
value.push_back('L');
//调用 size() 成员函数容器中的元素个数
printf("元素个数为:%d\n", value.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;
}

STL vector容器迭代器用法

vector容器和array容器模板类提供的操作迭代器的成员函数也和array容器一样。

C++11新添加的begin()end()全局函数也同样适用于vector容器,即当操作对象是vector对象时,其功能和上表中的begin(),end()成员函数相同。

vector容器迭代器与array容器迭代器基本相同

#include <iostream>
//需要引入 vector 头文件
#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;
}

当然也可以使用全局的begin()end()函数来从容器中获取迭代器,代码如下:

auto first=std::begin(values);

auto end=std::end(values);

vector容器迭代器的独特之处

array容器不同,vector容器可以随着存储元素的增加,自行申请更多的存储空间。因此,在创建vector对象时,我们可以直接创建一个空的vector容器,并不会影响后续使用该容器。

在使用vector迭代器时,需要注意在初始化空的vector容器时,不能使用迭代器

#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;
}

上述代码中,因为values是空容器,其begin()end()函数返回的迭代器是相等的,都指向同一个位置对于空的vector容器来说,可以通过push_back()或者借助resize()成员函数来实现初始化容器的目的

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

#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 的容量
values.reserve(20);
cout << "values 容器首个元素的地址:" << values.data() << endl;
while (first != end) {
cout << *first;
++first;
}
return 0;
}

可以看到,**values容器在增加容量之后,首个元素的存储地址发生了改变,此时在使用先前创建的迭代器显然是错误的**。因此,每当vector容器的容量发生变化时,我们都要对之前创建的迭代器重新初始化一遍。

#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 的容量
values.reserve(20);
cout << "values 容器首个元素的地址:" << values.data() << endl;
first = values.begin();
end = values.end();
while (first != end) {
cout << *first ;
++first;
}
return 0;
}

可以看出,vector经过扩容之后,容器首个元素的地址发生了改变。

vector访问元素的几种方式

访问vector容器的单个元素

vector容器可以支持对指定下标处的元素进行修改,比如:

#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> values{1,2,3,4,5};
//获取容器中首个元素
cout << values[0] << endl;
//修改容器中下标为 0 的元素的值
values[0] = values[1] + values[2] + values[3] + values[4];
cout << values[0] << endl;
return 0;
}

使用下标索引获取元素的方式,需要确保下标n的值不会超过容器的容量,可以通过capacity()获取,否则会出现越界访问的错误。 和array数组一样,vector也提供了at()成员函数,当传给at()的索引会造成越界时,会抛出std::out_of_range异常。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> values{1,2,3,4,5};
//获取容器中首个元素
cout << values.at(0) << endl;
//修改容器中下标为 0 的元素的值
values.at(0) = values.at(1) + values.at(2) + values.at(3) + values.at(4);
cout << values.at(0) << endl;
//下面这条语句会发生 out_of_range 异常
//cout << values.at(5) << endl;
return 0;
}

vector容器提供了front()back()两个成员函数,分别用于返回vector容器中第一个元素最后一个元素的引用,从而可以访问修改容器中的首尾元素。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> values{1,2,3,4,5};
cout << "values 首元素为:" << values.front() << endl;
cout << "values 尾元素为:" << values.back() << endl;
//修改首元素
values.front() = 10;
cout <<"values 新的首元素为:" << values.front() << endl;
//修改尾元素
values.back() = 20;
cout << "values 新的尾元素为:" << values.back() << endl;
return 0;
}

vector容器还提供data()成员函数,该函数的功能是返回指向容器中首个元素的指针,,通过该指针也访问甚至修改容器中的元素。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> values{1,2,3,4,5};
//输出容器中第 3 个元素的值
cout << *(values.data() + 2) << endl;
//修改容器中第 2 个元素的值
*(values.data() + 1) = 10;
cout << *(values.data() + 1) << endl;
return 0;
}

访问vector容器中多个元素

如果想访问vector容器中多个元素,可以借助size()成员函数,该函数可以返回vector容器中实际存储的元素个数。

#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++) {
//注意size()与capacity()的区别,size()是返回目前容器含有的元素,capacity是返回容器的容量。
cout << values[i] << " ";
}
return 0;
}

还可以使用基于范围的范围,此方式将会逐个遍历容器中的元素,比如:

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

还可以使用vector迭代器遍历vector容器,这里以begin()/end()为例:

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

vector容量(capacity)和大小(szie)的区别

vector容器的容量(capacity),指的是在不分配更多内存的情况下,容器可以保存的最多元素个数;而vector容器的大小(size)指的是它实际所包含的元素个数。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
std::vector<int>value{ 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 };
value.reserve(20);
cout << "value 容量是:" << value.capacity() << endl;
cout << "value 大小是:" << value.size() << endl;
return 0;
}

vector容器的大小不能超出它的容量,在大小等于容量的基础上,只要增加一个元素,就必须分配更多的内存。 注意,这里的更多并不是1个,换句话说,当vector容器的大小和容量相等时,如果在向其添加一个元素,vector往往会申请多个存储空间,而不仅仅只申请一个

一旦vector容器的内存被重新分配,则和vector容器中元素相关的所有引用、指针以及迭代器,都可以会失效,最稳妥的方法时重新生成

#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int>value{ 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 };
cout << "value 容量是:" << value.capacity() << endl;
cout << "value 大小是:" << value.size() << endl;
printf("value首地址:%p\n", value.data());
value.push_back(53);
cout << "value 容量是(2):" << value.capacity() << endl;
cout << "value 大小是(2):" << value.size() << endl;
printf("value首地址: %p", value.data());
return 0;
}

可以看到,向已满的vector容器在添加一个元素,整个value容器的存储位置发生了改变,同时vector会一次性申请多个存储空间(具体多申请多少个取决于底层算法的实现)。这样做的好处是,可以很大程度上减少vector申请空间的次数,当后续在添加元素时,就可以节省申请空间耗费的时间。

修改vector容器的容量和大小

可以调用reserve()成员函数来增加容器的容量(但不会改变存储元素的个数),而通过调用成员函数resize()可以改变容器的大小,并且该函数也可能会导致vector容器容量的增加

#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int>value{ 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47 };
cout << "value 容量是:" << value.capacity() << endl;
cout << "value 大小是:" << value.size() << endl;
value.reserve(20);
cout << "value 容量是(2):" << value.capacity() << endl;
cout << "value 大小是(2):" << value.size() << endl;
//将元素个数改变为 21 个,所以会增加 6 个默认初始化的元素
value.resize(21);
//将元素个数改变为 21 个,新增加的 6 个元素默认值为 99。
//value.resize(21,99);
//当需要减小容器的大小时,会移除多余的元素。
//value.resize(20);
cout << "value 容量是(3):" << value.capacity() << endl;
cout << "value 大小是(3):" << value.size() << endl;
return 0;
}

仅通过reserve()成员函数增加value容器的容量,其大小并没有改变,;但通过resize()成员函数改变value容器的大小,它的容量可能会发生变化。 通过resize()成员函数减少容器的大小(多余元素会直接被删除),不会影响容器的容量。

vector容器容量和大小的数据类型

有时我们需要将容器的容量和大小保存在变量中,要知道vector<T>对象的容量和大小类型都是vector<T>::size_type类型,因此,当定义一个变量去保存这些值时,可以如下:

vector<int>::size_type cap=value.capacity();

//也可以替换为auto cap = value.capacity();

vector<int>::size_type size=value.size();

//auto size=value.size();

size_type类型是定义在由vector类模板生成的vector类中,它表示的真实类型和操作系统相关,在32位架构下表示的是unsigned int类型,而在64位架构下表示的是unsigned long类型

vector容器的底层实现机制

STL众多容器中,vector是常用的容器,其底层所采用的数据结构非常简单,就只是一段连续的线性内存空间。vector容器采用3个迭代器来表示

//_Alloc表示内存分配器,此参数几乎不需要我们关心
template<class _Ty, class _Alloc = allocator<_Ty>>

class vector{
...
protected:
pointer _Myfirst;
pointer _Mylast;
pointer _Myend;

}

其中_Myfirst指向的是vector容器对象的起始字节位置, _Mylast指向的当前最后一个元素的末尾字节,_Myend指向整个vector容器所占用内存空间的末尾字节。

将三个迭代器两两结合,可以表达不同的含义:

  • _Myfirst_Mylast可以用来表示vector容器中目前已被使用的内存空间

  • _MYlast_Myend可以用来表示vector容器目前空闲的内存空间

  • _Myfirst_Myend 可以用表示 vector 容器的容量

对于空的vector容器,由于没有任何元素的空间分配,因此_Myfirst,_Mylast,_Myend均为null.

运用上述的迭代器,vector容器可以轻松的实现首尾标识,大小,容器、空容器判断等几乎所有的功能。

template <class _Ty, class _Alloc = allocator<_Ty>>
class vector{
public:
iterator begin() {return _Myfirst;}
iterator end() {return _Mylast;}
size_type size() const {return size_type(end() - begin());}
size_type capacity() const {return size_type(_Myend - begin());}
bool empty() const {return begin() == end();}
reference operator[] (size_type n) {return *(begin() + n);}
reference front() { return *begin();}
reference back() {return *(end()-1);}
...
};

对于上述代码有一个疑问,可以通过size_typee转化迭代器???

vector扩大容量的本质

vector扩容需要经历以下三步:

  1. 完全弃用现有的内存空间,重新申请更大的内存空间

  2. 将旧内存空间的数据按原有顺序移动到新的内存空间中

  3. 最后将旧的内存空间释放。

添加元素push_back()emplace_back()

vector容器中添加元素的唯一方式就是使用它的成员函数,如果不调用成员函数,非成员函数既不能添加也不能删除元素,这意味着vector容器对象必须通过它所允许的函数去访问,迭代器显然不行。

push_back()

该成员函数的功能是在vector容器尾部添加一个元素

#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> values{};
values.push_back(1);
values.push_back(2);
for (int i = 0; i < values.size(); i++) {
cout << values[i] << " ";
}
return 0;
}

emplace_back()

该函数是c++11新增加的,其功能和push_back相同,都是在vector容器的尾部添加一个元素。

#include <iostream>
#include <vector>
using namespace std;
int main()
{
vector<int> values{};
values.emplace_back(1);
values.emplace_back(2);
for (int i = 0; i < values.size(); i++) {
cout << values[i] << " ";
}
return 0;
}

emplace_back()push_back()的区别

emplace_back()push_back()的底层实现机制不同,**push_back()向容器底部添加元素时,首先会创建这个元素,然后在将元素拷贝或移动到容器中,之后在自行销毁先前创建的元素**,而emplace_back()在实现的时候,会直接在容器尾部创建这个元素,省去了拷贝或移动元素的过程。

#include <vector> 
#include <iostream>
using namespace std;
class testDemo
{
public:
testDemo(int num):num(num){
std::cout << "调用构造函数" << endl;
}
testDemo(const testDemo& other) :num(other.num) {
std::cout << "调用拷贝构造函数" << endl;
}
testDemo(testDemo&& other) :num(other.num) {
std::cout << "调用移动构造函数" << endl;
}
private:
int num;
};

int main()
{
cout << "emplace_back:" << endl;
std::vector<testDemo> demo1;
demo1.emplace_back(2);

cout << "push_back:" << endl;
std::vector<testDemo> demo2;
demo2.push_back(2);
}

由此可见,pus_back()需要先创建对象然后在拷贝或移动该对象,而emplace_back()则更加简单。 需要注意的是,push_back()在底层实现时,会优先选择调用移动构造函数,如果没有才会调用拷贝构造函数

插入元素insert()emplace()的区别

insert()

vector容器的指定位置插入一个或多个元素,注意该元素的返回值为iterator

#include <iostream> 
#include <vector>
#include <array>
using namespace std;
int main()
{
std::vector<int> demo{1,2};
//第一种格式用法
demo.insert(demo.begin() + 1, 3);//{1,3,2}

//第二种格式用法//后面添加2个5
demo.insert(demo.end(), 2, 5);//{1,3,2,5,5}

//第三种格式用法 , 不包含test.end()
std::array<int,3>test{ 7,8,9 };
demo.insert(demo.end(), test.begin(), test.end());//{1,3,2,5,5,7,8,9}

//第四种格式用法 //直接加一个列表
demo.insert(demo.end(), { 10,11 });//{1,3,2,5,5,7,8,9,10,11}

for (int i = 0; i < demo.size(); i++) {
cout << demo[i] << " ";
}
return 0;
}

emplace()

emplace()c++11新增加的成员函数,用于在vector容器指定位置之前插入一个新的元素。

emplace()每次只能插入一个元素,而不是多个。

iterator emplace(const_iterator pos,args...)

其中pos为指定插入位置的迭代器; args表示与新插入元素的构造函数相对应的多个参数,该函数会返回新插入元素位置的迭代器。

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

int main()
{
std::vector<int> demo1{1,2};
//emplace() 每次只能插入一个 int 类型元素
demo1.emplace(demo1.begin(), 3);
for (int i = 0; i < demo1.size(); i++) {
cout << demo1[i] << " ";
}
return 0;
}

inplace()emplace()的不同

#include <vector>
#include <iostream>
using namespace std;
class testDemo
{
public:
testDemo(int num) :num(num) {
std::cout << "调用构造函数" << endl;
}
testDemo(const testDemo& other) :num(other.num) {
std::cout << "调用拷贝构造函数" << endl;
}
testDemo(testDemo&& other) :num(other.num) {
std::cout << "调用移动构造函数" << endl;
}

testDemo& operator=(const testDemo& other);
private:
int num;
};
testDemo& testDemo::operator=(const testDemo& other) {
this->num = other.num;
return *this;
}
int main()
{
cout << "insert:" << endl;
std::vector<testDemo> demo2{};
demo2.insert(demo2.begin(), testDemo(1));

cout << "emplace:" << endl;
std::vector<testDemo> demo1{};
demo1.emplace(demo1.begin(), 1);
return 0;
}

inplace()empalce()的区别与上文所述的inplace_back()emplace_back()相同,应优先使用emplace()

vector删除元素的几种方式

对于向vector中访问元素,添加元素或者插入元素,都只能借助vector模板类提供的成员函数,但删除vector容器的元素除外,只能借助本身提供的成员函数,还可以借助一些全局函数。

pop_back()

会改变容器大小,但不会改变容量。

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

int main()
{
vector<int>demo{ 1,2,3,4,5 };
demo.pop_back();
//输出 dmeo 容器新的size
cout << "size is :" << demo.size() << endl;
//输出 demo 容器新的容量
cout << "capacity is :" << demo.capacity() << endl;
for (int i = 0; i < demo.size(); i++) {
cout << demo[i] << " ";
}
return 0;
}

erase()函数

删除容器中指定位置的元素,可以使用erase()成员函数,语法为:

iterator erase(pos);

其中pos为指定被删除元素位置的迭代器,同时该函数会返回一个指向删除元素所在位置下一个位置的迭代器

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

int main()
{
vector<int>demo{ 1,2,3,4,5 };
auto iter = demo.erase(demo.begin() + 1);//删除元素 2
//输出 dmeo 容器新的size
cout << "size is :" << demo.size() << endl;
//输出 demo 容器新的容量
cout << "capacity is :" << demo.capacity() << endl;
for (int i = 0; i < demo.size(); i++) {
cout << demo[i] << " ";
}
//iter迭代器指向元素 3
cout << endl << *iter << endl;
return 0;
}

erase()函数在删除元素时,会将删除位置后续的元素陆续前移,并将容器的大小减一。

swap()函数和pop_back()函数相互结合

可以使用swap()函数和pop_back()函数相互结合的方法,实现删除容器中指定位置元素的目的。

swap()函数在头文件<algorithm><utility>中都有定义,只需要在头文件中引入一个即可。

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

int main()
{
vector<int>demo{ 1,2,3,4,5 };
//交换要删除元素和最后一个元素的位置
swap(*(std::begin(demo)+1),*(std::end(demo)-1));//等同于 swap(demo[1],demo[4])

//交换位置后的demo容器
for (int i = 0; i < demo.size(); i++) {
cout << demo[i] << " ";
}
demo.pop_back();
cout << endl << "size is :" << demo.size() << endl;
cout << "capacity is :" << demo.capacity() << endl;
//输出demo 容器中剩余的元素
for (int i = 0; i < demo.size(); i++) {
cout << demo[i] << " ";
}
return 0;
}

erase()函数还可以删除容器中指定区域内的所有元素,语法如下:

iterator erase(iterator first, iterator last);, 这样删除的不包含last迭代器指向的内容

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

int main()
{
std::vector<int> demo{ 1,2,3,4,5 };
//删除 2、3
auto iter = demo.erase(demo.begin()+1, demo.end() - 2);
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;
}

remove()函数

如果要删除容器中和指定元素相同的所有元素,可以使用remove()函数,该函数定义在<algorithm>头文件中,例如:

#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);
//iter是指向删除指定元素后有用的最后一个元素的下一个迭代器

cout << "size is :" << demo.size() << endl;
cout << "capacity is :" << demo.capacity() << endl;
//输出剩余的元素
for (auto first = demo.begin(); first < iter;++first) {
cout << *first << " ";
}
return 0;
}

remove()函数在执行完毕后,并没有改变容器原来的大小和容量,因此无法使用之前的方法遍历容器,而是需要借助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;
}

clear()函数

clear()用于删除容器中所有的元素,会改变容器大小,但不会改变容器的容量。

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

int main()
{
vector<int>demo{ 1,3,3,4,3,5 };
//交换要删除元素和最后一个元素的位置
demo.clear();
cout << "size is :" << demo.size() << endl;
cout << "capacity is :" << demo.capacity() << endl;
return 0;
}

避免vector容器进行不必要的扩容

vector容器扩容的整个过程和realloc()函数类似,大致分为以下四个步骤:

  1. 分配一块大小是当前vector容量几倍的存储空间。多数STL版本中的vector容器,都会以2的倍数增长。

  2. vector容器存储的所有元素,按照原有次序从旧的存储空间复制到新的存储空间。

  3. 析构掉旧存储空间中存储的所有元素

  4. 释放掉旧的存储空间

vector容器的扩容过程非常耗时,并且对容器进行扩容后,和该容器相关的所有指针、迭代器以及引用都会失效,因此应尽量避免不必要的扩容,可以借助vector模板类中提供的reserve()成员方法。

避免vector容器执行不必要的扩容操作的关键在于,在使用vector容器初期,就要将其设置为足够大的值。换句话说,在vector容器刚刚构造出来的那一刻,就应该借助reserve()成员方法为其扩充足够大的容量。

vector<int>myvector;
for (int i = 1; i <= 1000; i++) {
myvector.push_back(i);
}

在这样的循环过程中,vector容量会进行2~10次自动扩容。

vector<int>myvector;
myvector.reserve(1000);
cout << myvector.capacity();
for (int i = 1; i <= 1000; i++) {
myvector.push_back(i);
}

在实际开发中,并不知道vector容器要存储多少元素,在这种情况下可以先预留处足够大的空间,当所有元素都存储到vector容器中之后,在去除多余的容量。

对于多余容量的处理,可以使用shrink_to_fit()成员方法,也可以使用swap()成员方法去除vector容器多余的容量。

vectorswap()成员方法的使用

vector模板类中提供一个shrink_to_fit的成员方法,可以将vector容器的容量减缩至和实际存储元素的个数相等

除使用shrink_to_fit()成员函数时,还提供了swap()成员方法,该方法的基础功能是交换两个相同类型的vector容器(交换容量和存储的所有元素),但其也用于去除vector容器多余的容量

swap()去除容器中的多余容量

使用swap()去除当前vector容器多余容量时,使用如下语法:

vector<T>(x).swap(x)

其中T为容器存储元素的类型,x为当前要操作的容器。

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

int main()
{
vector<int>myvector;
//手动为 myvector 扩容
myvector.reserve(1000);
cout << "1、当前 myvector 拥有 " << myvector.size() << " 个元素,容量为 " << myvector.capacity() << endl;
//利用 myvector 容器存储 10 个元素
for (int i = 1; i <= 10; i++) {
myvector.push_back(i);
}
//将 myvector 容量缩减至 10
vector<int>(myvector).swap(myvector);
cout << "2、当前 myvector 拥有 " << myvector.size() << " 个元素,容量为 " << myvector.capacity() << endl;
return 0;
}

swap()情况vector容器

vector<T>().swap(x)

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

int main()
{
vector<int>myvector;
//手动为 myvector 扩容
myvector.reserve(1000);
cout << "1、当前 myvector 拥有 " << myvector.size() << " 个元素,容量为 " << myvector.capacity() << endl;
//利用 myvector 容器存储 10 个元素
for (int i = 1; i <= 10; i++) {
myvector.push_back(i);
}
//清空 myvector 容器
vector<int>().swap(myvector);
cout << "2、当前 myvector 拥有 " << myvector.size() << " 个元素,容量为 " << myvector.capacity() << endl;
return 0;
}

swap()删除容器多余元素的的执行过程:

  1. 先执行vector<int>(myvector),此表达式会调用vector模板类中的拷贝构造函数,从而创造出一个临时的vector容器(暂时命名为tempvector)。这个拷贝构造函数会将myvector容器中的所有元素拷贝一份,并存储到tempvector临时容器中。

vector模板类中的拷贝构造函数只会为拷贝的元素分配存储空间,也就是说tempvector临时容器中没有空闲的存储空间。

  1. 借助swap()成员方法对tempvector临时容器和myvector容器进行调换,不仅需要调换容器存储的内容,而且需要交换他们的容量。这样tempvector拥有了myvector容器的元素和容量,myvecotor容器拥有了tempvector容器的元素和容量。

  2. 执行完语句后,临时的tempvector容器会被销毁,其占据的存储空间也被释放。

vector<bool>不是存储bool类型元素的容器

在使用vector容器时,应尽量避免使用该容器存储bool类型的元素,原因有二:

  1. vector<bool>不是一个STL容器

  2. vector<bool>底层存储的不是bool类型值

在实际的开发中,应该选择使用deque<bool>或者biset来替代vector<bool>

deque容器几乎具有vector容器全部的功能(拥有的成员方法也仅差reserve()capacity()),更重要的是,deque容器可以正常存储bool类型元素。

还可以使用biset代替vector<bool>,可以看出一种类似数组的存储结构,只能用来存储bool类型值,且存储机制采用一个比特位来存储一个bool值。

biset的大小在一开始就确定了,不支持插入和删除元素另外biset不是容器,索引也不支持迭代器

分类:

后端

标签:

C++

作者介绍

E
EdwardWong
V1