【STL四】序列容器——vector容器

一、简介

• vector 实现的是一个动态数组，即可以进行元素的插入和删除，在此过程中，vector 会动态调整所占用的内存空间，整个过程无需人工干预。

array实现的是一个静态数组。

• vector 常被称为向量容器，因为该容器擅长在尾部插入或删除元素，在常量时间内就可以完成，时间复杂度为O(1)；而对于在容器头部或者中部插入或删除元素，则花费时间要长一些（移动元素需要耗费时间），时间复杂度为线性阶O(n)。

二、头文件

#include<vector>

三、模板类

template<
    class T,
    class Allocator = std::allocator<T>
> class vector;

四、成员函数

1、迭代器

成员函数	功能
begin()	同array容器
end()	同array容器
rbegin()	同array容器
rend()	同array容器
cbegin()	同array容器
cend()	同array容器
crbegin()	同array容器
crend()	同array容器

2、元素访问

成员函数	功能
at(n)	同array容器
operator[]	同array容器
front()	同array容器
back()	同array容器
data()	同array容器

3、容量

成员函数	功能
empty()	同array容器
size()	同array容器
max_size()	同array容器
reserve	增加容器的容量。
capacity	返回当前容量。
shrink_to_fit	将内存减少到等于当前元素实际所使用的大小。

4、修改操作

成员函数	功能
clear()	移出所有的元素，容器大小变为 0。
insert()	在指定的位置插入一个或多个元素。
emplace()	在指定的位置直接生成一个元素。
erase()	移出一个元素或一段元素。
push_back()	在序列的尾部添加一个元素。
emplace_back()	在序列尾部生成一个元素。
pop_back()	移出序列尾部的元素。
resize()	调整容器的大小。
swap()	交换两个容器的所有元素。

五、demo

1、容量reserve、capacity、shrink_to_fit

//array 容器。
#include <iostream>
#include <vector>
#include<string>
using namespace std;
int main()
{
    vector<string>  v{ "one","two","three","four","five" }; 

    cout << "v.size()=" << v.size() << endl;
    cout << "v.capacity()=" << v.capacity() << endl<<endl;

    v.reserve(10);
    
    cout << "after reserve(10)" << endl;
    cout << "v.size()=" << v.size() << endl;
    cout << "v.capacity()=" << v.capacity() << endl<<endl;

    v.shrink_to_fit();

    cout << "after shrink_to_fit()" << endl;
    cout << "v.size()=" << v.size() << endl;
    cout << "v.capacity()=" << v.capacity() << endl << endl;

    return 0;
}

输出

v.size()=5
v.capacity()=5


after reserve(10)
v.size()=5
v.capacity()=10


after shrink_to_fit()
v.size()=5
v.capacity()=5

2、修改操作pop_back()、push_back

//vector 容器。
#include <iostream>
#include <vector>
#include<string>
using namespace std;
int main()
{
    vector<string>  v{ "one","two","three","four","five" }; 

    v.pop_back();
    v.push_back("six");

    for (auto it = v.begin(); it < v.end(); it++)
        cout << *it << " ";
    cout << endl;
}

输出

one two three four six

3、修改操作insert()

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

//vector 容器。
#include <iostream>
#include <vector>
#include<string>
using namespace std;
int main()
{
    vector<string>  v{ "one","two","three","four","five" }; 

    v.insert(v.begin(),"ten");
    
    for (auto it = v.begin(); it < v.end(); it++)
        cout << *it << " ";
    cout << endl;

    v.insert(v.end(), { "ten","ten2" });

    for (auto it = v.begin(); it < v.end(); it++)
        cout << *it << " ";
    cout << endl;

    return 0;
}

输出

ten one two three four five
ten one two three four five ten ten2

4、修改操作emplace()

是 C++ 11 标准新增加的成员函数，用于在 vector 容器指定位置之前插入一个新的元素。

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

• 该函数的语法格式如下：

iterator emplace (const_iterator pos, args…);

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

//vector 容器。
#include <iostream>
#include <vector>
#include<string>
using namespace std;
int main()
{
    vector<string>  v{ "one","two","three","four","five" }; 

    //emplace() 每次只能插入一个 int 类型元素
    v.emplace(v.begin(),"ten");
    
    for (auto it = v.begin(); it < v.end(); it++)
        cout << *it << " ";
    cout << endl;

    return 0;
}

输出

ten one two three four five

5、修改操作erase()、swap()、clear() 、

//vector 容器。
#include <iostream>
#include <vector>
#include<string>
using namespace std;
int main()
{
    vector<string>  v{ "one","two","three","four","five" }; 

    v.erase(v.begin());
    
    for (auto it = v.begin(); it < v.end(); it++)
        cout << *it << " ";
    cout << endl;

    vector<string> w{ "1","12" };
    v.swap(w);

    for (auto it = v.begin(); it < v.end(); it++)
        cout << *it << " ";
    cout << endl;

    v.clear();
    for (auto it = v.begin(); it < v.end(); it++)
        cout << *it << " ";
    cout << endl;
    return 0;
}

输出

two three four five
1 12
,

6、emplace_back()和push_back()的区别

• 该函数是 C++ 11 新增加的，其功能和 push_back() 相同，都是在 vector 容器的尾部添加一个元素。
• emplace_back() 和 push_back() 的区别，就在于底层实现的机制不同。push_back() 向容器尾部添加元素时，首先会创建这个元素，然后再将这个元素拷贝或者移动到容器中（如果是拷贝的话，事后会自行销毁先前创建的这个元素）；而 emplace_back() 在实现时，则是直接在容器尾部创建这个元素，省去了拷贝或移动元素的过程。

7、insert()和emplace()

• 既然 emplace() 和 insert() 都能完成向 vector 容器中插入新元素，那么谁的运行效率更高呢？
  答案是 emplace()。

• 假如，我们通过 insert() 函数向 vector 容器中插入 testDemo 类对象，需要调用类的构造函数和移动构造函数（或拷贝构造函数）；而通过 emplace() 函数实现同样的功能，只需要调用构造函数即可。

同std::list、std::deque

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

输出

insert:
调用构造函数
调用移动构造函数
emplace:
调用构造函数

参考：
1、C++ STL 容器库 中文文档
2、STL教程：C++ STL快速入门
3、https://www.apiref.com/cpp-zh/cpp/header.html
4、https://en.cppreference.com/w/cpp/container