C++ STL库的介绍和使用

STL(标准模板库)，是惠普实验室开发的一系列软件的统称。现在主要出现在C++中，但是在引入C++之前该技术已经存在了很长时间了。STL从广义上分为：容器(container) 算法(algorithm) 迭代器(iterator)，容器和算法之间通过迭代器进行无缝衔接。STL几乎所有的代码都采用了模板类或者是模板函数，这相比于创痛的由函数和类组成的库来说提供了更好的代码重用机会。STL标准模板库，在我们C++标准程序库中隶属于STL的占到了80%以上。

STL六大组件

容器：各种数据结构 vector list deque set map等，存放数据
算法：如sort find copy for_each等，操作数据
迭代器：容器和算法的桥梁
仿函数：为算法提供更多的策略
适配器：为算法提供更多的参数接口
空间配置器：管容器和算法的空间

STL六大组件的交互关系：容器通过空间配置器获取数据存储空间，算法通过迭代器获取存储器的内容，仿函数可以协助算法完成不同的策略变化，适配器可以修饰仿函数。

算法的分类

质变算法：运算过程中会更好区间内的数据，如拷贝、替换、删除等

非质变算法：运算过程中不会更改区间内容，如查找、计数、遍历等

迭代器

迭代器是一种抽象的概念，提供一种方法，使之能够依顺序访问某个容器所含的各个元素，而无需暴露该容器的内部表示方式。

迭代器的设计思维是STL的关键所在，STL中心思想是把容器和算法分开，彼此设计独立。

一个简单的例子

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int it)
{
    cout << it << " ";
}
void test()
{
    vector<int> vv;
    vv.push_back(1);
    vv.push_back(2);
    vv.push_back(3);

    // 开始迭代器，指向开始位置
    vector<int>::iterator itBegin = vv.begin();
    // 结束迭代器，指向尾元素的下一个位置
    vector<int>::iterator itEnd = vv.end();
    for(auto it = itBegin; it!= itEnd; it++)
    {
        cout << *it << " ";
    }
    cout << endl;
    // 需要了解，可用vs查看对应的实现源码，可以看到整体实现思路是上面的for
    for_each(itBegin, itEnd, print);
    cout << endl;
}
int main(int argc, char* argv[])
{
    test();
    return 0;
}

容器和自定义类型

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Person
{
public:
    Person(int a, int n): age(a), num(n) {}
    int age;
    int num;
};
void print(const Person &it)
{
    cout << it.age << " " << it.num << endl;
}

void test()
{
    vector<Person> vv;
    vv.push_back(Person(1,1));
    vv.push_back(Person(2,2));
    vv.push_back(Person(3,3));
    for_each(vv.begin(), vv.end(), print);
}
int main(int argc, char* argv[])
{
    test();
    return 0;
}

容器嵌套容器

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print2(int a)
{
    cout << a << " " ;
}
void print(const vector<int> &a)
{
    for_each(a.begin(), a.end(), print2);
}
void test()
{
    vector<int> a;
    a.push_back(1);
    a.push_back(2);
    a.push_back(3);
    vector<int> b;
    b.push_back(4);
    b.push_back(5);
    b.push_back(6);
    vector<int> c;
    c.push_back(7);
    c.push_back(8);
    c.push_back(9);
    vector<vector<int>> aa;
    aa.push_back(a);
    aa.push_back(b);
    aa.push_back(c);
    for_each(aa.begin(), aa.end(), print);
}
int main(int argc, char* argv[])
{
    test();
    return 0;
}

常用容器

string

C风格的字符串太过复杂，难以掌握，不太适合大程序的开发，所以C++标准库定义了一种string类，定义在头文件中。

string和C风格字符串对比：

char是一个指针，string是一个类，string封装了char，管理了这个字符串，是一个char类型的容器。
string封装了很多实用的成员方法，查找find、拷贝copy、删除delete、替换replace、插入insert
不用考虑内存的释放和越界，string管理了char*所分配的内存，每一次string的赋值，取值都由string类负责维护，不用担心复制越界和取值越界等算法

下面的例子列举了一些简单使用：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 字符串赋值
void test()
{
    string str("5152");
    string str3;
    str3 = str;
    cout << str3 << endl;
    string str2;
    str2 = "hello world";
    cout << str2 << endl;
    string str1;
    str1 = 'H';
    cout << str1 << endl;
    string str4;
    str4.assign(str);
    cout << str4 << endl;
}
// 字符串存取
void test02()
{
    string str = "hello world";
    cout << str[1] << endl;
    cout << str.at(1) << endl;
    str[1] = 'E';
    str[7] = 'O';
    cout << str << endl;
    try{
//        str[100] = 'H';
        str.at(100) = 'H';
    }
    catch (exception &e)
    {
        cout << e.what() << endl;
    }
}
// 字符串拼接
void test03()
{
    string str1 = "hello ";
    string str2 = "world";
    str1+=str2;
    cout << str1 << endl;
    string str3 = "hello ";
    str3+="world";
    cout << str3 << endl;
    str3.append(" mmmm");
    cout << str3 << endl;
    str3.append(" mmmm", 3);
    cout << str3 << endl;
    str3.append(str2, 2, 3);
    cout << str3 << endl;
}
// 字符串查找和替换
void test04()
{
    string str1 = "hello world";
    int a = str1.find('e');
    cout << a << endl;
    a = str1.find('e', 3);
    cout << a << endl;
    a = str1.find("worl");
    cout << a << endl;
    // 表示从0开始替换5个字符，替换成后面的
    str1.replace(0, 5, "mmmmm");
    cout << str1 << endl;
}
// 字符串比较和子串的提取
void test05()
{
    string str1 = "hello world";
    string str2 = "hello";
    int a = str1.compare(str2);
    cout << a << endl;
    a = str1.compare("oooo");
    cout << a << endl;
    a = str1.compare("hello world");
    cout << a << endl;

    string str = str1.substr(0, 8);
    cout << str << endl;
    string str11 = "asd:asdas:asdasdasd:dadssad:dasdsa";
    int pos = 0;
    while(1)
    {
        int ret = str11.find(":", pos);
        if(ret < 0)
        {
            string tmp = str11.substr(pos, str11.size() - pos);
            cout << tmp << endl;
            break;
        }
        string tmp = str11.substr(pos, ret - pos);
        cout << tmp << endl;
        pos = ret + 1;
    }
}
// 字符串的插入和删除
void test06()
{
    string str = "hello world";
    str.insert(5, " hehe");
    cout << str << endl;
    str.erase(5, 5);
    cout << str << endl;
    str.clear();
    cout << str << endl;
}
// 字符串和C风格字符串转换
void test07()
{
    char *aa = "hello world";
    string str = aa;
    const char *cc = str.c_str();
    cout << str << endl;
    cout << cc << endl;
}
int main(int argc, char* argv[])
{
    test07();
    return 0;
}

vector

vector的数据安排以及操作方式与数组相似，两者的唯一差别在于运用的灵活性。数组是静态空间，一旦配置了就不能改变，要更换大一点或者小一点的空间，可以，但是需要自己去做空间分配和数据拷贝，然后释放原先的空间。vector是动态空间，随着元素的加入，它的内部机制会自动扩充空间以容纳新元素。因此vector的运用对于内存的合理利用与利用的灵活性有很大的帮助，我们不必担心空间不足而开辟一块很大的array。

vector的迭代器：随机访问迭代器

随机访问迭代器：迭代器+n可以通过编译器编译，就是随机访问迭代器。

vector的容量(capacity)和大小(size)是有区别的。

capacity：是空间能容纳元素的最大个数
size：是空间中实际存放的个数

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(const vector<int> &aa)
{
    for(auto it = aa.begin(); it != aa.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
    fflush(stdout);
}
void test()
{
    vector<int> v;
    for(int i = 0; i < 100; ++i)
    {
        v.push_back(i);
    }
    cout << v.size() << endl;
    cout << v.capacity() << endl;
}
// 另寻空间的次数
void test02()
{
    int count = 0;
    vector<int> v;
    int *p = nullptr;
    for(int i = 0; i < 1000; ++i)
    {
        v.push_back(i);
        if(p!= &v[0])
        {
            count++;
            p = &v[0];
        }
    }
    cout << count << endl;
}
// vector的构造、赋值和交换
void test03()
{
    vector<int> v(10, 5);
    print(v);
    vector<int> v1(v.begin() + 2, v.end() -2);
    print(v1);
    vector<int> v2(v);
    print(v2);
    vector<int> v3;
    v3.assign(v.begin() + 1, v.end() - 1);
    print(v3);
    vector<int> v4;
    v4 = v3;
    print(v4);
    vector<int> v5;
    v5.assign(5, 10);
    print(v5);
    vector<int> v6(6, 20);
    print(v6);
    v5.swap(v6);
    print(v5);
    print(v6);
}
// vector大小操作
void test04()
{
    vector<int> v(10, 5);
    if(v.empty())
    {
        cout << "v is empty" << endl;
    }
    else
    {
        cout << v.capacity() << endl;
        cout << v.size() << endl;
    }
    print(v);
    v.resize(16);
    print(v);
    v.resize(1024, 5);
    print(v);
    v.resize(2);
    print(v);
    cout << v.capacity() << endl;
    cout << v.size() << endl;
    // 使用swap收缩容量空间，通过交换函数重新申请大小
    vector<int>(v).swap(v);
    cout << v.capacity() << endl;
    cout << v.size() << endl;
    vector<int> vv(10, 5);
    cout << "vv:" << vv.capacity() << endl;
    cout << "vv:" << vv.size() << endl;
    // 空间预留
    vv.reserve(50);
    cout << "vv:" << vv.capacity() << endl;
    cout << "vv:" << vv.size() << endl;
}
// vector的数据操作
void test05()
{
    vector<int> v;
    for(int i = 0; i < 6; i++)
    {
        v.push_back(i);
    }
    cout << v[5] << endl;
    cout << v.at(5) << endl;
    cout << v.front() << endl;
    cout << v.back() << endl;
    v.insert(v.begin() + 3, 2, 100);
    print(v);
    v.pop_back();
    print(v);
    v.erase(v.begin()+1,v.begin()+3);
    print(v);
    v.erase(v.begin());
    print(v);
    v.clear();
    print(v);
}
int main(int argc, char* argv[])
{
    test05();
    return 0;
}

注意： resize只能修改size，不能修改容量。

deque

vector容器时一段连续的内存空间，dequeue则是一种双向开口的联系线性空间。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作。vector也可以在头尾进行插入操作，但是vector的头部插入操作效率奇差，不可以被接受。

deque容器是由一段一段的定量连续空间构成的，一旦有必要在deque前端或者是尾端增加新的空间，便配置一段连续定量的空间，串接在deque的头端或者是尾端。deque最大的工作就是维护这些分段连续的空间的整体性的假象，并提供随机访问接口，避免了重新配置空间，复制，释放的轮回，代价就是复杂的迭代器架构。

#include <iostream>
#include <algorithm>
#include <deque>
using namespace std;
void print(const deque<int> &aa)
{
    for(auto it = aa.begin(); it != aa.end(); it++)
    {
        cout << *it << " ";
    }
    cout << endl;
    fflush(stdout);
}
// 初始化和赋值
void test()
{
    deque<int> v(5, 10);
    print(v);
    deque<int> v1;
    v1.assign(v.begin()+1, v.end()-1);
    print(v1);
    deque<int> v2 = v;
    print(v2);
    v2.swap(v1);
    print(v1);
    print(v2);
}
// 插入和存取
void test02()
{
    deque<int> v(5, 10);
    v.resize(10,3);
    print(v);
    v.resize(3);
    print(v);
    v.push_front(6);
    print(v);
    v.push_back(6);
    print(v);
    v.pop_front();
    print(v);
    v.pop_back();
    print(v);
    cout << v[1] << endl;
    cout << v.at(1) << endl;
    cout << v.size() << endl;
    cout << v.empty() << endl;
    v.clear();
    cout << v.empty() << endl;
}
int main(int argc, char* argv[])
{
    test02();
    return 0;
}

stack

stack是一种先进后出的数据结构，它只有一个出口。stack允许新增元素，移除元素，取得栈顶元素，但是除了顶端外，没有任何办法存取stack元素。换言之，stack不允许有遍历行为。有元素推入栈的操作称为push，将元素推出栈的操作称为pop。

stack没有迭代器。

#include <iostream>
#include <algorithm>
#include <stack>
using namespace std;
void test()
{
    stack<int> ss;
    ss.push(1);
    ss.push(2);
    ss.push(3);
    ss.push(4);
    ss.push(5);
    cout << ss.top() << endl;
    ss.pop();
    cout << ss.top() << endl;
    ss.pop();
    cout << ss.top() << endl;
    ss.pop();
    cout << ss.top() << endl;
    ss.pop();
    cout << ss.top() << endl;
    ss.pop();
}
int main(int argc, char* argv[])
{
    test();
    return 0;
}

queue

队列是一种先进先出的数据结构，他有一个出口一个入口，queue容器允许从一端新增元素，从另外一端移除元素。

队列没有迭代器。

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
void test()
{
    queue<int> qq;
    qq.push(1);
    qq.push(2);
    qq.push(3);
    qq.push(4);
    qq.push(5);
    cout << qq.size() << endl;
    cout << qq.empty() << endl;
    cout << qq.front() << endl;
    qq.pop();
    cout << qq.front() << endl;
    qq.pop();
    cout << qq.front() << endl;
    qq.pop();
    cout << qq.front() << endl;
    qq.pop();
    cout << qq.front() << endl;
    qq.pop();
    cout << qq.empty() << endl;
}
int main(int argc, char* argv[])
{
    test();
    return 0;
}

list

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。链表由一系列节点组成，节点在运行时动态生成。每个节点包括两个部分：一个是存储数据元素的数据域，一个是存储下一个节点地址的指针域。相较于vector的连续线性空间，list就显得负责许多，它的每次插入或者是删除一个元素，就是配置或者释放一个元素的空间。因此，list对于空间的运用具有绝对的精准，一点也不浪费，而且，对于任何位置的元素插入或者是删除，list永远是常数时间。list和vector是两个最长被使用的容器。list是一个双向链表。

链表采用的是动态存储分配，不会造成内存浪费和溢出，链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量的元素。俩表灵活但是空间和时间额外耗费比较大。

list的迭代器是双向访问迭代器

#include <iostream>
#include <algorithm>
#include <list>
#include <vector>
using namespace std;
void print(const list<int> &ll)
{
    for(auto & a : ll)
    {
        cout << a << " ";
    }
    cout << endl;
    fflush(stdout);
}
class Person
{
public:
    Person(int a) : age(a){}
    bool operator<(const Person &right)
    {
        return this->age < right.age;
    }
    int age;
};
class Compare
{
public:
    bool operator()(const Person &left, const Person &right)
    {
        return left.age < right.age;
    }
};
bool operator==(const Person &left, const Person &right)
{
    return left.age == right.age;
}
bool compare(const Person &left, const Person &right)
{
    return left.age > right.age;
}
void print(const list<Person> &ll)
{
    for(auto & a : ll)
    {
        cout << a.age << " ";
    }
    cout << endl;
    fflush(stdout);
}
void print(const vector<Person> &ll)
{
    for(auto & a : ll)
    {
        cout << a.age << " ";
    }
    cout << endl;
    fflush(stdout);
}
void test()
{
    list<int> ll;
    ll.push_back(10);
    ll.push_back(20);
    ll.push_back(30);
    ll.push_back(40);
    print(ll);
    auto it = find(ll.begin(), ll.end(), 20);
    ll.insert(++it, 3 ,100);
    print(ll);
    ll.reverse();
    print(ll);
    ll.sort();
    print(ll);
}
void test01()
{
    list<Person> ll;
    ll.push_back(10);
    ll.push_back(20);
    ll.push_back(30);
    ll.push_back(40);
    print(ll);
    ll.remove(Person(20));
    print(ll);
    ll.sort();
    print(ll);
    ll.sort(compare);
    print(ll);
}
void test02()
{
    vector<Person> ll;
    ll.push_back(20);
    ll.push_back(10);
    ll.push_back(30);
    ll.push_back(40);
    sort(ll.begin(), ll.end(), compare);
    print(ll);
    sort(ll.begin(), ll.end(), Compare());
    print(ll);
    sort(ll.begin(), ll.end(), [&](const Person &left, const Person &right) -> bool {
        return left.age > right.age;
    });
    print(ll);
}
int main(int argc, char* argv[])
{
    test02();
    return 0;
}

注意： list删除自定义数据，必须重载==运算符，否则无法匹配是否相等。

C++ STL库的介绍和使用（下）：https://developer.aliyun.com/article/1459455

C++ STL库的介绍和使用（上）