STL

从本节，我们将介绍C++的STL（Standard Template Library）也就是标准模板库，顾名思义者就是C++提供的封装好的模板函数，并使之标准化，方便程序员调用。那么STL有哪些呢？
STL广义上可以分为三类：algorithm（算法）、container（容器）、iterator（迭代器）,几乎所有的代码都采用了模板类和模板函数的方式，相比于传统的标准库函数，提高了代码重用。C++标准中，STL组织为以下13个头文件
<algorithm>、<deque>、<functional>、<iterator>、<vector>、<list>、<map>、<memory>、<numeric>、<queue>、<set>、<stack>和<utility>
本节主要介绍vector的使用

vector

vector 是序列化的容器，可以理解为是能改动态改变规模大小的数组。
想数组一样，vectors为元素分配了连续紧邻的存储位置，意味着能够像数组一样使用下表进行访问元素，和数组一样方便。但是有一点和数组不同，他们的规模大小可以动态的改变。
本质上讲，vector使用动态分配的数组来存储元素，当新的数据插入时，这种数组可能会需要重新分配地址空间，以改变规模大小，也就是说，重新分配一个大点儿的空间，然后把原来的元素copy过去，再释放原来的空间，这种操作及其耗时，因此不可能没插入一个元素就重新分配一次空间。相反，vector容器会额外的分配一些空间，以备扩增之需，因此vector的容量往往会比实际元素所占用的空间，即size大一点。
因此，从末尾插入数据，只需要常数的时间复杂度，O(1)的时间。
对比与其他的动态序列化容器，像deques，lists，和forward_lists, vectors 在访问元素时十分高效，因为就像访问数组一样，从末尾插入和删除元素也是一样。但是，涉及到从中间位置插入，删除的操作时，vectors就不如其他的容器了。

成员类型

Paste_Image.png

成员函数

Paste_Image.png

Paste_Image.png
这些函数在C++参考网站上都可以查到

下面逐一介绍相关函数
构造函数
C++11标准vector有6种构造函数

Paste_Image.png

默认构造函数
构造一个空的容器，没有任何元素
填充型构造函数
构造含有n个相同元素的构造函数
范围型构造函数
构造一个容器，容器的预算，依次有序的对应着序列[first,last)的每一个元素的值
拷贝构造函数
拷贝已有的vector
移动构造函数
初始化列表构造函数

Example

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

int main(){
    //constructors 
    vector<int> first;//empty vector of ints
    vector<int> second(4, 100);//four ints with value 100
    vector<int> third(second.begin(), second.end());// iterating through second
    vector<int> fourth(third); // a copy of third

    //the iterator constructor can also be used to construct from arrays;
    int myints[] = { 16, 2, 77, 29 };
    vector<int> fifth(myints, myints + sizeof(myints) / sizeof(int));
    cout << "The contents of fifth are:";
    for (vector<int>::iterator it = fifth.begin(); it != fifth.end(); ++it)
        cout << ' ' << *it;
    cout << '\n';

    return 0;
}

Paste_Image.png

Iterators

begin
end
rbegin
rend
cbegin
cend
crbegin
crend
begin返回的是一个指向首元素的iterator，r代表reverse，c代表const。

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

int main(){

    //begin/end
    vector<int> myvector;
    for (int i = 1; i <= 5; i++) myvector.push_back(i);
    cout << "myvecotr contains: ";
    for (vector<int>::iterator it = myvector.begin(); it!=myvector.end(); ++it)
        cout << ' '<<*it;
    cout << endl;


    //rbegin/rend
    cout << "myvector rbegin to rend: ";
    for (vector<int>::reverse_iterator rit = myvector.rbegin(); rit != myvector.rend(); ++rit)
        cout << ' ' << *rit;
    cout << endl;


    //cbegin/cend
    
    cout << "cbegin return a const_iterator of the sequence" << endl;
    for (auto it = myvector.cbegin(); it != myvector.cend(); ++it)
        cout << " " << *it;
    cout << endl;
    return 0;
}

Paste_Image.png

Capacity

size
返回容器中元素的个数
max_size
返回vector所能容纳的最大元素的个数，一般很大
resize
改变vector的元素个数
capacity
返回分配的存储空间所能容纳元素的个数
empty
判断vector是否为空
reserve
请求一个合理调度capacity
shrink_to_fit
缩小capacity到合适的大小

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

int main(){

    vector<int> james;
    for (int i = 1; i <= 20; i++)
        james.push_back(i);

    cout << "size: " << james.size() << endl;
    cout << "max_size: " << james.max_size() << endl;
    cout << "capacity:" << james.capacity() << endl;
    cout << "is empty: " << james.empty() << endl;
    james.resize(10);
    cout << "after resize:" << endl;
    cout << "size: " << james.size() << endl;
    james.reserve(100);
    cout << "after reserve:" << endl;
    cout << "capacity:" << james.capacity() << endl;
    james.shrink_to_fit();
    cout << "after shrink:" << endl;
    cout << "capacity: " << james.capacity() << endl;
}

Paste_Image.png

Element access

operator[]
和数组一样下表访问，
at
访问元素指定的元素
front
访问第一个元素
back
访问最后一个元素
data
访问数据，返回一个指向首元素的指针

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

int main(){
    vector<int> Ooba(10);
    for (unsigned i = 0; i < Ooba.size(); i++){
        Ooba[i] = i;//operator[]
    }
    cout << "Ooba contains elements: ";
    for (auto it = Ooba.begin(); it != Ooba.end(); ++it)
        cout << " " << *it;
    cout << endl;

    //reverse
    vector<int>::size_type sz = Ooba.size();
    for (unsigned i = 0; i <sz / 2; i++){
        int swap = Ooba.at(sz - 1 - i);
        Ooba.at(sz - 1 - i) = Ooba.at(i);
        Ooba.at(i) = swap;
    }
    cout << "after reverse:" << endl;
    for (auto it = Ooba.begin(); it != Ooba.end(); ++it)
        cout << " " << *it;
    cout << endl;
    cout << "首元素：" << Ooba.front() << endl;
    cout << "尾元素：" << Ooba.back() << endl;
    //data
    cout << "data:" << endl;
    int *p = Ooba.data();
    cout << *p << endl;
    cout << *(++p) << endl;
    p[3] = 520;
    for (auto it = Ooba.begin(); it != Ooba.end(); ++it)
        cout << " " << *it;
    cout << endl;
}

Paste_Image.png

Modifiers

assign
给容器赋值
push_back
在末尾添加一个元素
pop_back
在末尾删除一个元素
insert
插入元素
erase
删除指定元素
swap
交换两个容器
clear
清楚容器中的所有元素
emplace
构造并在适当的位置插入元素
emplace_back
构造并在最后插入一个元素

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

int main(){
    vector<int> first;
    first.assign(7, 100);//赋值 7 ints with a value of 100
    vector<int> second;
    second.assign(first.begin() + 1, first.end() - 1);
    cout << "Size of first: " << int(first.size()) << '\n';
    cout << "Size of second: " << int(second.size()) << '\n';

    vector<int> foo;
    foo.push_back(1);
    foo.push_back(2);
    foo.push_back(3);
    foo.pop_back();
    cout << "Size of foo: " << int(foo.size()) << '\n';

    vector<int> myvector(3, 100);
    vector<int>::iterator it;

    it = myvector.begin();
    it = myvector.insert(it, 200);

    myvector.insert(it, 2, 300);

    // "it" no longer valid, get a new one:
    it = myvector.begin();

    vector<int> anothervector(2, 400);
    myvector.insert(it + 2, anothervector.begin(), anothervector.end());

    int myarray[] = { 501, 502, 503 };
    myvector.insert(myvector.begin(), myarray, myarray + 3);

    cout << "myvector contains:";
    for (it = myvector.begin(); it<myvector.end(); it++)
        std::cout << ' ' << *it;
    cout << '\n';
    myvector.erase(myvector.begin(), myvector.begin() + 5);//erase
    cout << "myvector contains:";
    for (it = myvector.begin(); it<myvector.end(); it++)
        std::cout << ' ' << *it;
    cout << '\n';

}