Cpp浅析系列-STL之vector

前言

能够在运行时高效地存放各种类型的动态数组vector！

CPP

Vector定义

#include <Vector> 
using namespace std;
 
void init() {
 
    //空对象
    vector<int> v1;
 
    //元素个数为5，每个int元素都为0
    vector<int> v2(5);
 
    //元素个数为5，每个int元素都为3
    vector<int> v3(5, 3);
 
    //手动赋初值，共五个元素，元素值为指定的内容
    vector<int> v4{1, 2, 3, 4, 5};
}

Vector常规操作

C++中文在线手册：https://zh.cppreference.com/

访问Vector中的任意元素或从末尾添加元素的时间复杂度是O(1)，而查找特定值的元素所处的位置或是在Vector中插入元素则是线性时间复杂度，即O(n)。

增加元素

下标插入

Vector是动态数组，是支持随机访问的，也就是直接用下标取值。

但是如果是直接用下标赋值，当下标超出了容器的超出了容量，会无法插入，而且此时是不会报错。

/*
 * 声明了一个对象，初始是两个元素，容量为2
 * 当直接修改下标没有超过容量，会直接修改元素
 * 当直接修改下标查过了容量，会没有变化，因为容器内不存在超过容量的元素，被认为是无效操作。
 * */
void add1(){
    vector<int> demo{1, 2};
    demo[1]=3;//{1,3}
    demo[10]=3;//{1,3}
}

所以建议使用自带的插入函数。

insert插入

允许多个元素的插入，使用迭代器指定位置。

注意：是在迭代器 pos 位置之前插入！

注意：因为需要调用类的构造函数和移动构造函数，所以较慢，但是适用性很棒！

void add2(){
    vector<int> demo{1, 2};
    //在第一个元素后面插入3
    demo.insert(demo.begin() + 1, 3);//{1,3,2}
 
    //在末尾插入2个5
    demo.insert(demo.end(), 2, 5);//{1,3,2,5,5}
 
    //插入其他容器的部分序列
    set<int> setTemp{7, 8, 9};
    demo.insert(demo.end(), ++setTemp.begin(), --setTemp.end()); //{1,3,2,5,5,8}
 
    //插入初始化列表
    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] << " ";
    }
}

emplace插入

注意是每次只能插入一个，而且是只有构造函数，效率高！

void add3() {
    vector<int> demo{1, 2};
 
    demo.emplace(demo.begin(), 3);//{3,1,2}
 
    for (int i = 0; i < demo.size(); i++) {
        cout << demo[i] << " ";
    }
}

push_back插入

vector底层是用数组实现的，每次执行push_back操作，在底层实现时，是会判断当前元素的个数是否等于容量大小，如果没有就直接插入，否则就要扩容了。

void add4() {
    vector<int> demo{1, 2};
 
    demo.push_back(3);//{3,1,2}
 
    for (int i = 0; i < demo.size(); i++) {
        cout << demo[i] << " ";
    }
}

换句话说，扩容时是要重新分配大小的，先free掉原来的存储空间，后重新malloc。非常耗费时间！

void
vector<_Tp, _Allocator>::push_back(const_reference __x)
{
    if (this->__end_ != this->__end_cap())
    {
        __construct_one_at_end(__x);
    }
    else
        __push_back_slow_path(__x);
}

遍历元素

下标遍历1

/*
 * 直接for循环，用下标取元素即可
 * */
void search1() {
    vector<int> demo{1, 2};
 
    for (int i = 0; i < demo.size(); i++) {
        cout << demo[i] << " ";
    }
}

下标遍历2

/*
 * 直接用下标取值，超过容量会报错
 * */
void search3() {
    vector<int> demo{1, 2};
 
    cout <<demo.at(1);
    // cout <<demo.at(1);// 会报错
    cout << endl;
}

迭代器遍历

/*
 * 直接用迭代器，注意const_iterator还是iterator
 * */
void search2() {
    vector<int> demo{1, 2};
 
    // 如果参数为const vector<int> 需要用const_iterator
    // vector<int>::const_iterator iter=v.begin();
    for (vector<int>::iterator it = demo.begin(); it != demo.end(); ++it) {
        cout << (*it) << " ";
    }
    cout << endl;
}
 

删除元素

/*
 * 删除有两种方式，
 * clear一个是直接清空
 * erase是删除指定迭代器范围内的数字
 * pop_back是删除最后一个
 * */
void del() {
    vector<int> demo{1, 2, 3, 4, 5};
    //清空
    demo.clear();//{}
    if (demo.empty()) {//判断Vector为空则返回true
        demo.insert(demo.end(), {6, 7, 8, 9, 10, 11});//{ 6, 7, 8, 9, 10, 11 }
 
        //删除第一个元素
        demo.erase(demo.begin());//{7, 8, 9, 10, 11 }
 
        //删除前三个
        demo.erase(demo.begin(), demo.begin() + 3); //{ 10, 11 }
 
        //删除最后一个
        demo.pop_back();//{10}
    }
 
    for (int i = 0; i < demo.size(); i++) {
        cout << demo[i] << " ";
    }
}

原理

内存扩展方式

当调用插入函数，却发现空间不够的时候，会进行扩容：

1. 寻找原来的capacity的两倍空间；

2. 将原数据复制过去；

3. 释放原空间三部曲。

每次配置新空间时都有留下一些数据空间，可以保证常数的时间复杂度

三大特性

• 严格的线性顺序排序。

• 支持动态内存分配

• 支持随机访问元素，并操供了在尾部添加和删除操作

size和capacity的区别

size则代表了对象内元素的个数

capacity代表了能够存放多少个元素的阀值。

一旦超过阀值capacity，容器会花费大量时间重新配置内部的存储器，并导致vector元素相关的所有reference、pointers、iterator都会失效。

感谢

示例文件

gitee：https://gitee.com/JunKuangKuang/KeenCPPTest-all/blob/ac9971df11109470fbaf708ba2977ca593d92292/STL/vector/vector_test.cpp

github.com：https://github.com/JunKuangKuang/KeenCPPTest-all/blob/main/STL/vector/vector_test.cpp

感谢

感谢现在的好奇，为了能成为更好的自己。

离线下载链接

vector 类中的 push_back( ) 函数

C++ STL vector插入元素