CPP STL介绍

STL介绍

STL(Standard Template Library), 标准模板库，是一个具有工业强度的，高效的C++ 程序库。该库包含了诸多在计算机科学领域里所常用的基本数据结构和基本算法。为广大C++程序员们提供了一个可扩展的应用框架，高度体现了软件的可复用性。

STL 六大组件

有容器、迭代器、算法、仿函数、迭代适配器、空间配置器。
容器通过空间配置器取得数据存储空间；算法利用迭代器向容器存取数据；仿函数协助算法完成不同的策略；适配器可以用来修改容器、迭代器或仿函数的接口；

主要需要我们关注的有：

容器(Container): 是一种数据结构，如 list，vector，和deques ，以模板类的方法提供。
迭代器（Iterator）: 提供了访问容器中对象的方法。例如，可以使用一对迭代器指定list或vector中的一定范围的对象。
算法(Algorithm): 用来操作容器中的数据的模板函数。例如，STL用sort()来对一个vector中的数据进行排序，用find()来搜索一个list中的对象，函数本身与他们操作的数据的结构和类型无关，因此他们可以在从简单数组到高度复杂容器的任何数据结构上使用。任何的一个STL算法，都需要获得由一对迭代器所标示的区间，用来表示操作范围。这一对迭代器所标示的区间都是前闭后开区间，例如[first, last)。也就是说实际上，整个区间是从first开始到last-1，迭代器last指的是最后一个元素的下一个位置。在STL中所有区间都是采用前闭后开，这样可以带来很多方便。

常用容器与算法介绍

常用容器

<vector>
vector是一个能够存放任意类型的动态数组。当你不知道需要选取什么容器时就选它吧。vector在储存空间不足时会开辟一个原空间*2大小的空间，并将原数据拷贝到新的空间中。这个操作比较耗时，但是有办法可以弥补这个缺点，在下文会有。

<list>
双向循环链表。不可以随机存储，但是在任何地方插入与删除元素的时间都是常量.

<queue>
队列, 先进先出的数据结构.

<deque>

Deque是一个双端数组，既支持随机存取(像数组一样)，又支持两端的操作(在前后插入，在前后删除)。Deque在头部与尾部添加移除元素时间复杂度为O(1), 在中部则较为费时。
Deque用一段指向数组的指针来管理控制整个数组。

当有必要在deque的前端或尾端增加新空间时，便会分配一段定量连续空间，串接在整个deque的头端或尾端。

<priority_queue>
优先队列，即堆。每次在队尾加入一个元素后，都会进行一些调整，使优先级最高的元素处于队首，也即堆的顶部。

<stack>
栈，后进先出的数据结构。

set, multiset, map, multimap底层都是使用红黑树实现的。

<set>
集合，每个值都是惟一的。

<multiset>
多集，值可以重复，可以记录每个元素出现了多少次。

<map>
键值对，键唯一，一个键对应一个值。

<multimap>
键值对，键唯一，一个键可对应多个值。

常用算法

包含在<algorithm>头文件中

min(), max()
返回最小值，最大值.

sort()
排序算法，将指定区间中的数据排序。
如sort(v.begin(), v.end())会将v这个vector中的元素从小到大排列。
还可以指定一个自己的比较规则作为参数传入sort函数。
sort(v.begin(), v.end(), compare)

reverse()
反转算法, 将指定区间中的数据反转。
reverse(s.begin(), s.end()) 会将s这个字符串反转。

swap()
交换两个对象。

fill()
对一个区间内的每个对象赋值。

unique()
移除一个区间内的重复的对象。

copy()
将一个区间内的数值拷贝到另一个区间中。

replace()
将一个区间内的某个对象替换为另一个对象。

示例程序

vector & algorithm

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void coutvec(vector<int> v)
{
    cout << "Vector 输出:" << endl;
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << " ";
    }
    cout << "\r\n\r\n";
}
int main()
{
    vector<int> v;
    v.reserve(20);
    for(int i = 20; i > 0; i--){
        v.push_back(i);
    }
    coutvec(v); 
    cout << "reverse(v.begin()+10, v.end()+20):" << endl;
    reverse(v.begin()+10, v.begin()+20);
    coutvec(v);
    cout << "sort(v.begin(), v.end()):" <<endl;
    sort(v.begin(), v.end());
    coutvec(v);
    
    cout << "fill(v.begin(), v.begin+5, -1):" <<endl;
    fill(v.begin(), v.begin()+5, -1);
    coutvec(v);
    cout << "copy(v.begin(), v.begin()+5, v.begin()+6):" <<endl;
    copy(v.begin(), v.begin()+5, v.begin()+5);
    coutvec(v);
    cout << "replace(v.begin(), v.begin()+5, -1, 233):" << endl;
    replace(v.begin(), v.begin()+5, -1, 233);
    coutvec(v);
    
    cout << "unique(v.begin(), v.end()):" <<endl;
    std::vector<int>::iterator it;
    it = unique(v.begin(), v.end());
    v.resize(distance(v.begin(), it));
    coutvec(v);
    return 0;
}

Queue & Stack

#include <iostream>
#include <queue>
#include <stack>
using namespace std;
int main()
{
    cout << "Queue:" <<endl;
    queue<int> q;
    for(int i = 1; i <= 10; i++) {
        q.push(i);
    }
    while(!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << "\r\n\r\n" << endl;
    cout << "Stack:" <<endl;
    stack<int> s;
    for(int i = 1; i <= 10; i++) {
        s.push(i);
    }
    while(!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
}

Map & Multimap

#include <iostream>
#include <map>
#include <string>
using namespace std;
int main()
{
    cout << "Map:" <<endl;
    map<char, string> m;
    m['a'] = "apple";
    m['b'] = "banana";
    m['c'] = "cheery";
    
    std::map<char, string>::iterator it;
    for(it = m.begin(); it != m.end(); ++it) {
        cout << it->first << "=>" << it->second << endl;
    }
    cout << "\r\n\r\n" << endl;
    cout << "MultiMap:" <<endl;
    multimap<char, string> mm;
    mm.insert(make_pair('a', "apple"));
    mm.insert(make_pair('a', "avocado"));
    mm.insert(make_pair('b', "banana"));
    mm.insert(make_pair('b', "berry"));
    mm.insert(make_pair('b', "blueberry"));
    mm.insert(make_pair('c', "cherry"));
    mm.insert(make_pair('c', "core"));
    mm.insert(make_pair('c', "chestnut"));
    mm.insert(make_pair('c', "cumquat"));
    multimap<char, string>::iterator itlow, ithigh;
    itlow = mm.lower_bound('a');
    ithigh = mm.upper_bound('c');
    for(it = itlow; it!=ithigh; ++it){
        cout << (*it).first << "=>" << (*it).second << endl;
    }
    return 0;
}

STL的选取

是否需要在容器任意位置插入新元素？
如果需要，就选择序列容器(vector, string, deque, list)，避免关联容器(set, multiset, map, multimap)
你是否关心容器中的元素是如何排序的？
若不关心最好选择hash容器如hashset, hashmap等，因为效率会更高。
采用hash算法处理过的容器在查找元素时效率比普通容器更高
当容器发生元素插入与删除时，若需要尽力避免原来元素的腾挪，则应选择采用节点存储元素的容器(如list)，避免采用数组存储的元素如(vector)。
若十分关心容器的查找速度，则考虑的优先级为：hash容器，排序的vector, 标准关联容器。

… …

使用技巧

用empty()而非size()来检查容器是否为空

对于所有容器，empty()都使用常数时间，而对于某些容器，size()需要耗费线性时间。

当在容器中存放指针时，注意在销毁容器前先销毁指针

因为简单地delete容器并不能delete掉内部的那些指针。

删除

如果你想删除某个值的元素，不同容器需要采用不同的方法。

如果采用连续内存容器，最好使用earse-remove方法.

1	v.erase(remove(v.begin(), v.end(), 1), c.end());

对于list, 最有效的是直接使用list的remove成员函数。
1
c.remove(1);
对于关联容器，最有效的方法是使用erase
1
c.erase(1);

如果你不只像删除某个值的元素，而是想删除下面这个函数返回false的函数。

1	bool shouldremove(val x)

对于序列容器(vector, list, deque, string), 只需要将remove 换为remove_if()

//c为vector, list, deque, string
c.erase(remove_if(c.begin(), c.end(), shouldremove), c.end());
//c为list
c.remove_if(shouldremove);

对于关联容器，最好采用这种方法

Container<int> c;
//遍历整个容器中的元素.
for(Container::iterator i = c.begin(); i != end(); /*nothing*/){
    if(shouldremove(*i)){
        c.earse(i);
    }
    i++;
}

Vector 减少不必要的重新分配

vector的扩张可以分为下面几个步骤:

分配一块大小为当前容量2倍的空间。
把容器的所有元素从旧的内存拷贝到新的内存中。
析构掉旧内存中的对象。
释放旧的内存。
这个过程是十分耗时的。

在想一下，如果你这样创建一个包含1到1000的vector, 你可能会这样做:

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

在这个过程中，最坏情况下会有10次内存重新分配。（1000 约等于 2的10次方）.

如何避免这种情况呢？
vector提供了一个reserve函数，这个函数可以将容器的容量(capacity)强迫变为某个数值。

1
2
3

capacity:一个容器最大可以存放多少个元素，即size最大是多少。
size:当前容器有多少元素。
当vector在插入一个元素时，会比较size和capacity, 当两者一样大时，代表容量已经被用完，开始重新分配空间。

如果我们在一开始就将vector的capacity设置为某个足够大的数值，就不会出现多次重新分配的情况，也就提升了效率。
如，上述程序这样写就不会出现重新分配的情况了:

vector<int> v;
v.reserve(1000);
for(int i = 0; i <= 1000; i++) {
    v.push_back(i);
}

注：这条策略同样适用于string.

当对效率敏感时，应注意map.insert 与 map::operator[]

当增加一对新元素时，使用map的insert函数。
当进行元素更新时，使用map的[]操作符。

因为当进行“增加”操作时，operator[]会有三个函数调用：构造临时对象，撤销临时对象和对对象复制，而insert不会有；而对于更新操作，insert需要构造和析构对象，而operator[] 采用的对象引用，不会有这样的效率损耗.

排序

若需对vector, string, deque, 或 array容器进行全排序，你可选择sort或stable_sort；
若只需对vector, string, deque, 或 array容器中取得top n的元素，部分排序partial_sort是首选.
若对于vector, string, deque, 或array容器，你需要找到第n个位置的元素或者你需要得到top n且不关系top n中的内部顺序，nth_element是最理想的；
若你需要从标准序列容器或者array中把满足某个条件或者不满足某个条件的元素分开，你最好使用partition或stable_partition；
若使用的list容器，你可以直接使用partition和stable_partition算法，你可以使用list::sort代替sort和stable_sort排序。若你需要得到partial_sort或nth_element的排序效果，你必须间接使用。正如上面介绍的有几种方式可以选择。

容器的成员函数优先于算法

若一个容器的成员函数与一个算法功能一致，则优先选择成员函数。因为成员函数是专门为这个容器编写的，因此与容器结合地更紧密，效率一般会更高。

推荐查询函数用法的网站 -> Cplusplus reference

本文地址： http://Humbertzhang.github.io/2017/12/11/CPP容器/

@Humbert's Blog