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';
}
Paste_Image.png
vector 标准模板类给我们提供了许多接口，经常使用，熟能生巧。
