C++ 基础知识四认识STL 上

一、概述
二、容器
三、迭代器
四、算法
五、小结回顾

一、概述

1. 起源 Standard Template Library

Standard Template Library：标准模板库是一个基于泛型的C++类模板库由Alexander Stepanov于1994年开发
其目的是为了提供一致通用和高效的数据结构和算法，同时不限制用户所处理的数据类型和编程范式。STL的原型最初由Andrew Koenig和其它C++专家小组进行设计并在1995年C++标准委员会的推荐下成为C++标准库的一部分。

2. 发展历程

STL的发展经过了一系列的演化过程。最初是由Alexander Stepanov开发的SGI-STL（Silicon Graphics STL）版本，后来被许多厂商和开源社区所采用并发扬光大。出于对SGI拥有版权的限制后来形成了多个同源的STL版本，如STLport、Apache STL等。随着C++标准的不断发展变化，STL自2000年起多次进行了升级，包括C++03的修订版和C++11、C++14、C++17等标准。

3. 组成部分与内部实现原理

STL包含迭代器、容器、算法、仿函数和适配器等五个主要部分。
容器可分为序列式和关联式两种，算法主要是对容器中元素进行操作和处理，仿函数则是封装了自定义函数的类模板。
内部实现主要基于模板和泛型编程，利用C++模板的特性将数据类型和算法进行解耦，使得STL可适用于各种数据类型和编程范式。

下面通过具体的代码实现来验证STL强大能力：

使用vector容器存储元素并使用for循环不断向容器中压入元素
使用transform算法将vector容器中的所有元素都扩大2倍
使用find算法查找vector容器中是否存在元素5若存在则将元素5修改为-5
最终输出查找前后、变换前后的vector容器元素，证明STL提供的容器和算法确实可以在效率和正确性上带来极大的便利。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 声明一个vector容器
    vector<int> vec;
    
    // 将元素压入vector容器
    for (int i = 0; i < 10; i++) {
        vec.push_back(i);
    }
    
    // 原始vector容器元素
    for (auto i : vec) {
        cout << i << " ";
    }
    cout << endl;
    
    // 将vector容器内的所有元素*2
    transform(vec.begin(), vec.end(), vec.begin(), [](int elem) {return elem * 2;});
    
    // 变换后的vector容器元素
    for (auto i : vec) {
        cout << i << " ";
    }
    cout << endl;
    
    // 查找vector容器中元素5的位置
    auto find_it = find(vec.begin(), vec.end(), 5);
    
    // 如果找到，则将元素5修改为-5
    if (find_it != vec.end()) {
        *find_it = -5;
    }
    
    // 查找后的vector容器元素
    for (auto i : vec) {
        cout << i << " ";
    }
    cout << endl;
    
    return 0;
}

4. 优点和局限性

4.1优点

STL采用了统一的模板式的编程方式，具有代码重用可移植性好高效性等优点。而且STL已经成为C++标准库的一部分也具有了代码稳定标准化易维护等特点。

4.2局限

局限性是对于一些复杂的数据结构和算法有时会需要自定义容器和迭代器等部分，并且STL的使用也需要一定的学习门槛和理解成本。

总体来说优点远大于缺点，不仅提高了程序员的开发效率也推动了C++语言的广泛应用

二、容器

1. 定义

C++ STL中的容器是一种存储多个元素的数据结构，每个容器都有自己的特性和使用场景。
按照元素的存储方式可以将其分为以下四种类型：

序列容器（sequence container）
关联容器（associative container）
无序关联容器（unordered associative container）
容器适配器（container adapter）

2. 序列容器

序列容器中的元素按照某个顺序依次被存储，常见的几种序列容器如下：

2.1 vector

容器特性：动态数组支持随机访问
存储结构：连续的内存空间支持在末尾添加元素
元素存取方法：使用下标 [] 或迭代器访问
使用场景：在需要大量的末尾添加元素以及随机访问元素的情况下使用

代码实现如下：

#include <vector>
#include <iostream>

using namespace std;

int main() {
    // 定义一个vector容器
    vector<int> vec;
    
    // 在vector末尾添加元素
    vec.push_back(1); // 序列号 1
    vec.push_back(2); // 序列号 2
    vec.push_back(3); // 序列号 3
    
    // 输出vector中的元素
    for (auto i : vec) {
        cout << i << " ";
    }
    cout << endl;
    
    return 0;
}

2.2 deque

容器特性：双端队列支持随机访问和在队头和队尾添加和删除元素
存储结构：连续的内存块支持在末尾和头部添加元素
元素存取方法：使用 [] 或者迭代器访问。
使用场景：当需要在队头队尾添加和删除元素的时候使用。

代码实现如下：

#include <deque>
#include <iostream>

using namespace std;

int main() {
    // 定义一个deque容器
    deque<int> dq;
    
    // 在deque末尾和头部添加元素
    dq.push_back(1); // 序列号 1
    dq.push_front(0); // 序列号 2
    dq.push_back(2); // 序列号 3
    
    // 输出deque中的元素
    for (auto i : dq) {
        cout << i << " ";
    }
    cout << endl;
    
    return 0;
}

2.3 list

容器特性：双向链表不支持随机访问
存储结构：双向链表支持在任意位置添加或删除元素
元素存取方法：只支持前向迭代器访问
使用场景：当需要在任意位置添加或删除元素的时候使用

代码实现如下：

#include <list>
#include <iostream>

using namespace std;

int main() {
    // 定义一个list容器
    list<int> lst;
    
    // 在list中添加元素
    lst.push_back(1); // 序列号 1
    lst.push_back(2); // 序列号 2
    lst.push_front(0); // 序列号 3
    
    // 输出list中的元素
    for (auto i : lst) {
        cout << i << " ";
    }
    cout << endl;
    
    // 在指定位置插入元素
    lst.insert(++lst.begin(), 3); // 序列号 4
    
    // 输出list中的元素
    for (auto i : lst) {
        cout << i << " ";
    }
    cout << endl;
    
    // 删除指定位置的元素
    lst.erase(++lst.begin()); // 序列号 5
    
    // 2.3.7 输出 list 中的元素
    for (auto i : lst) {
        cout << i << " ";
    }
    cout << endl;
    
    return 0;
}

2.4 forward_list

容器特性：单向链表不支持反向遍历
存储结构：单向链表支持在任意位置添加或删除元素
元素存取方法：只支持前向迭代器访问
使用场景：当需要在任意位置添加或删除元素，而且只需要单向遍历容器的时候使用

代码实现如下：

#include <forward_list>
#include <iostream>

using namespace std;

int main() {
    // 定义一个forward_list容器
    forward_list<int> flst;
    
    // 在forward_list中添加元素
    flst.push_front(1); // 序列号 1
    flst.push_front(2); // 序列号 2
    flst.push_front(3); // 序列号 3
    
    // 输出forward_list中的元素
    for (auto i : flst) {
        cout << i << " ";
    }
    cout << endl;
    
    // 在指定位置插入元素
    auto it = ++flst.before_begin(); // 获取第一个元素的迭代器
    flst.insert_after(it, 4); // 序列号 4
    
    // 输出forward_list中的元素
    for (auto i : flst) {
        cout << i << " ";
    }
    cout << endl;
    
    // 删除指定位置的元素
    it = flst.begin(); // 获取第一个元素的迭代器
    flst.erase_after(it); // 序列号 5
    
    // 输出forward_list中的元素
    for (auto i : flst) {
        cout << i << " ";
    }
    cout << endl;
    
    return 0;
}

3. 关联容器

关联容器中的元素是按照某种方式进行排序的，因此支持基于排序的元素存储和访问。
常见的几种关联容器有：

3.1 set 与 multiset

容器特性：基于红黑树的关联容器，元素按照从小到大的顺序进行排序，每个元素值都必须唯一，multiset可以存储多个相同元素
存储结构：内部使用红黑树进行实现，支持查找、插入、删除元素
元素存取方法：只能通过迭代器访问，不支持随机访问
使用场景：当需要存储唯一元素，而且需要按照从小到大的顺序进行排序的场景

代码实现如下：

#include <set>
#include <iostream>

using namespace std;

int main() {
    // 定义一个 set 容器
    set<int> iset;
    
    // 向set中添加元素
    iset.insert(1); // 序列号 1
    iset.insert(3); // 序列号 2
    iset.insert(2); // 序列号 3
    
    // 输出set中的元素
    for (auto i : iset) {
        cout << i << " ";
    }
    cout << endl;
    
    // 在set中查找元素
    auto it = iset.find(2);
    if (it != iset.end()) {
        cout << "2 is found in set" << endl;
    }
    
    // 删除set中的元素
    iset.erase(2); // 序列号 4
    
    // 输出set中的元素
    for (auto i : iset) {
        cout << i << " ";
    }
    cout << endl;
    
    return 0;
}

3.2 map 与 multimap

容器特性：基于红黑树的关联容器，存储元素为键值对(key-value pair)，每个键值对的键都必须唯一，map只能存储一个键值对，multimap可以存储多个相同的键值对
存储结构：内部使用红黑树进行实现，支持查找、插入、删除元素
元素存取方法：只能通过迭代器访问，不支持随机访问
使用场景：当需要存储唯一键值对，而且需要按照键进行排序的场景

代码实现如下：

#include <map>
#include <iostream>

using namespace std;

int main() {
    // 定义一个map容器
    map<int, string> imap;
    
    // 向map中添加键值对
    imap.insert(pair<int, string>(3, "three")); // 序列号 1
    imap.insert(make_pair(1, "one")); // 序列号 2
    imap.insert(map<int, string>::value_type(2, "two")); // 序列号 3
    
    // 输出map中的元素
    for (auto i : imap) {
        cout << i.first << ":" << i.second << " ";
    }
    cout << endl;
    
    // 在map中查找元素
    auto it = imap.find(2);
    if (it != imap.end()) {
        cout << "2 is found in map, " << it->second << endl;
    }
    
    // 删除map中的元素
    imap.erase(1); // 序列号 4
    
    // 输出map中的元素
    for (auto i : imap) {
        cout << i.first << ":" << i.second << " ";
    }
    cout << endl;
    
    return 0;
}

4. 无序关联容器

无序关联容器中的元素是按照哈希表存储的，因此支持常数时间的查找、插入和删除操作。
常见的几种无序关联容器有：

4.1 unordered_set 与 unordered_multiset

容器特性：基于哈希表的关联容器，元素无顺序，每个元素值都必须唯一，unordered_multiset可以存储多个相同元素
存储结构：内部使用哈希表进行实现，支持常数时间的查找、插入、删除元素
元素存取方法：只能通过迭代器访问，不支持随机访问
使用场景：当需要存储唯一元素，而且不需要按照顺序进行排序的场景

代码实现如下：

#include <unordered_set>
#include <iostream>

using namespace std;

int main() {
    // 定义一个unordered_set容器
    unordered_set<int> iset;
    
    // 向unordered_set中添加元素
    iset.insert(1); // 序列号 1
    iset.insert(3); // 序列号 2
    iset.insert(2); // 序列号 3
    
    // 输出unordered_set中的元素
    for (auto i : iset) {
        cout << i << " ";
    }
    cout << endl;
    
    // 在unordered_set中查找元素
    auto it = iset.find(2);
    if (it != iset.end()) {
        cout << "2 is found in unordered_set" << endl;
    }
    
    // 删除unordered_set中的元素
    iset.erase(2); // 序列号 4
    
    // 输出unordered_set中的元素
    for (auto i : iset) {
        cout << i << " ";
    }
    cout << endl;
    
    return 0;
}

4.2 unordered_mapun 与 ordered_multimap

容器特性：基于哈希表的关联容器，存储元素为键值对(key-value pair)，每个键值对的键都必须唯一，unordered_map只能存储一个键值对，unordered_multimap可以存储多个相同的键值对
存储结构：内部使用哈希表进行实现，支持常数时间的查找、插入、删除元素
元素存取方法：只能通过迭代器访问，不支持随机访问
使用场景：当需要存储唯一键值对，而且不需要按照键进行排序的场景

代码实现如下：

#include <unordered_map>
#include <iostream>

using namespace std;

int main() {
    // 定义一个unordered_map容器
    unordered_map<int, string> imap;
    
    // 向unordered_map中添加键值对
    imap.insert(pair<int, string>(3, "three")); // 序列号 1
    imap.insert(make_pair(1, "one")); // 序列号 2
    imap.insert(unordered_map<int, string>::value_type(2, "two")); // 序列号 3
    
    // 输出unordered_map中的元素
    for (auto i : imap) {
        cout << i.first << ":" << i.second << " ";
    }
    cout << endl;
    
    // 在unordered_map中查找元素
    auto it = imap.find(2);
    if (it != imap.end()) {
        cout << "2 is found in unordered_map, " << it->second << endl;
    }
    
    // 删除unordered_map中的元素
    imap.erase(1); // 序列号 4
    
    // 输出unordered_map中的元素
    for (auto i : imap) {
        cout << i.first << ":" << i.second << " ";
    }
    cout << endl;
    
    return 0;
}

5. 容器适配器

容器适配器是一种特殊的容器，它们的底层实现可以基于其他容器完成。
常见的几种容器适配器有：

5.1 stack

容器特性：栈，底层实现可以基于vector、deque或list完成
存储结构：可以使用vector、deque或list中的一种作为底层实现
元素存取方法：只支持栈顶元素的访问和删除
使用场景：当需要实现栈结构时，使用stack容器适配器可以非常方便

代码实现如下：

#include <stack>
#include <iostream>

using namespace std;

int main() {
    // 定义一个stack容器
    stack<int> istack;
    
    // 向stack中添加元素
    istack.push(1); // 序列号 1
    istack.push(2); // 序列号 2
    istack.push(3); // 序列号 3
    
    // 输出stack中的元素
    while (!istack.empty()) {
        int i = istack.top();
        cout << i << " ";
        istack.pop();
    }
    cout << endl;
    
    return 0;
}

5.2 queue

容器特性：队列，底层实现可以基于deque或list完成
存储结构：可以使用deque或list作为底层实现
元素存取方法：只支持队首元素和队尾元素的访问和删除
使用场景：当需要实现先进先出的数据结构时，使用queue容器适配器可以非常方便

代码实现如下：

#include <queue>
#include <iostream>

using namespace std;

int main() {
    // 定义一个queue容器
    queue<int> iqueue;
    
    // 向queue中添加元素
    iqueue.push(1); // 序列号 1
    iqueue.push(2); // 序列号 2
    iqueue.push(3); // 序列号 3
    
    // 输出queue中的元素
    while (!iqueue.empty()) {
        int i = iqueue.front();
        cout << i << " ";
        iqueue.pop();
    }
    cout << endl;
    
    return 0;
}

5.3 priority_queue

容器特性：优先队列，底层实现可以基于vector或deque完成
存储结构：可以使用vector或deque作为底层实现
元素存取方法：支持插入和访问优先级最高的元素，不支持删除特定元素
使用场景：当需要根据优先级存储元素时，使用priority_queue容器适配器可以非常方便

代码实现如下：

#include <queue>
#include <iostream>

using namespace std;

int main() {
    // 定义一个priority_queue容器
    priority_queue<int> ipq;
    
    // 向priority_queue中添加元素
    ipq.push(3); // 序列号 1
    ipq.push(1); // 序列号 2
    ipq.push(2); // 序列号 3
    
    // 输出priority_queue中的元素
    while (!ipq.empty()) {
        int i = ipq.top();
        cout << i << " ";
        ipq.pop();
    }
    cout << endl;
    
    return 0;
}

三、迭代器

迭代器是ST中用来操作容器内部元素的一种统一方式，它将容器中元素的访问和操作抽象出来，使得程序员可以使用一种统一的方式操作各种容器元素。

1.1 定义

迭代器是一种模板类型可以定义指向容器元素的指针，通过重载运算符来实现对容器中元素的访问、修改等操作。
迭代器可以分为以下几种：

输入迭代器（input iterator）：支持从容器中读取元素，一旦读取，就不能重复读取
输出迭代器（output iterator）：支持向容器中写入元素，一旦写入，就不能重复写入
前向迭代器（forward iterator）：支持读写、前移操作，对容器进行单向遍历
双向迭代器（bidirectional iterator）：支持读写、前移、后移操作，对容器进行双向遍历
随机访问迭代器（random access iterator）：支持读写、前移、后移、加法、减法、下标等操作，对容器进行随机访问

1.2 常见应用

主要应用场景是对容器内部元素进行遍历、访问、操作等。STL中的算法函数和容器的成员函数都可以用迭代器实现，比如STL中的sort函数，要求传入的容器必须是支持随机访问迭代器的。

迭代器的使用方法简单只需要使用迭代器访问容器中的元素即可
展示迭代器的两种基本使用方式如下：

使用cbegin和cend访问vector中的元素，在访问元素时，可以通过解引用的方式访问迭代器指向的元素，也就是 “*iter”
使用begin和end访问和修改vector中的元素，在修改元素时，需要使用指针运算符来对迭代器所指向的元素进行修改，也就是 “*iter = new_value”

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> ivec = { 0, 1, 2, 3, 4, 5 };
    
    // 使用迭代器输出vector中的所有元素
    for (auto iter = ivec.cbegin(); iter != ivec.cend(); ++iter) {
        cout << *iter << " "; // 输出每个元素的值
    }
    cout << endl;
    
    // 使用迭代器修改vector中的元素
    for (auto iter = ivec.begin(); iter != ivec.end(); ++iter) {
        *iter *= 2; // 将每个元素的值都乘以2
    }
    
    // 使用迭代器输出修改后的vector中的所有元素
    for (auto iter = ivec.begin(); iter != ivec.end(); ++iter) {
        cout << *iter << " "; // 输出每个元素的值
    }
    cout << endl;
    
    return 0;
}

1.3 应用技巧

迭代器的应用技巧包括迭代器间的算术运算、逆向迭代器、插入迭代器、流迭代器等。
这些技巧可以大大简化代码的编写提高程序的效率

1.3.1 迭代器间的算术运算

迭代器间的算术运算包括加法和减法，可以通过运算得到目标迭代器在容器中的位置
如下所示：

auto iter = ivec.begin();
auto iter2 = iter + 3; // iter2指向ivec中第4个元素
auto iter3 = iter2 - 2; // iter3指向ivec中第2个元素

注意的：加法和减法操作运用在容器中的迭代器类型必须支持该运算，只有随机访问迭代器支持加减运算

1.3.2 逆向迭代器

逆向迭代器是一种反向遍历容器的迭代器，可以通过rbegin和rend函数来访问
如下所示：

for (auto iter = ivec.rbegin(); iter != ivec.rend(); ++iter) {
    cout << *iter << " ";
}
cout << endl;

注意：逆向迭代器操作和普通迭代器不同，逆向迭代器的++操作实际上是–，–操作实际上是++。并且逆向迭代器只能被随机访问迭代器进行算术运算。

1.3.3 插入迭代器

插入迭代器是一种特殊的迭代器可以在容器中插入元素，有back_inserter、front_inserter和inserter三种类型。
back_inserter 示例如下：

vector<int> ivec = { 0, 1, 2, 3, 4, 5 };
vector<int> new_vec;
copy(ivec.cbegin(), ivec.cend(), back_inserter(new_vec));

1.3.4 流迭代器

流迭代器是一种迭代器类型，可以使用iostream对象来进行输入和输出
如下所示：

#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

int main() {
    vector<int> ivec = { 0, 1, 2, 3, 4, 5 };
    copy(ivec.begin(), ivec.end(), ostream_iterator<int>(cout, " "));
    cout << endl;
    
    return 0;
}

注意：输出迭代器可以通过继承std::iterator类来实现，使得输出操作与容器对象的类型无关

四、算法

1.1 STL中常见算法及其应用场景

STL中提供了许多常见的算法实现，包括查找、排序、变序、合并等。这些算法适用于大部分容器类型如vector、list、set、map

1.1.1 查找

find：在指定区间查找特定元素，返回指向该元素的迭代器。
binary_search：在有序区间查找特定元素，返回bool类型结果。
count：在指定区间计数特定元素的个数。

应用场景：常用于查找、比较操作

1.1.2 排序

sort：排序指定区间的元素。
stable_sort：排序指定区间的元素，保持稳定性。
partial_sort：部分排序，将指定区间元素排在前面，其余元素排序用默认比较函数处理。

应用场景：常用于排序操作

1.1.3 变序

reverse：将指定区间的元素反转。
rotate：让指定区间的元素旋转。
shuffle：调用随机数引擎并按照指定方式随机重排区间内的元素。

应用场景：常用于计算机图形学、游戏开发

1.1.4 合并

merge：将两个已经排好序的序列合并成一个排序的序列。
merge_backward：将两个已经排好序的序列合并成一个排序的序列，但合并后的元素保持原序列的稳定性。

应用场景：常见于归并排序

1.1.5 算术操作

accumulate：计算指定区间元素的总和。
inner_product：计算指定区间两个元素序列的内积。
adjacent_difference：计算相邻元素之间的差值。
partial_sum：由相邻元素的和序列输出指定序列部分和。

应用场景：常用于数学计算、统计分析等

1.2 复杂度分析与优化

大多数STL算法的复杂度都处于时间复杂度为O(nlogn)的级别，因此在处理大量数据时，时间复杂度的优化尤为重要。
下面介绍几种常见的算法复杂度分析：

1.2.1 排序算法

排序算法的复杂度主要取决于比较次数，因此需要尽可能减少比较次数以提高排序效率。常见的排序算法包括快速排序、归并排序和堆排序，其中快速排序相对来说效率更高，但在极端情况下会出现O(n²)的最坏情况。

1.2.2 查找算法

查找算法的时间复杂度与数据结构有关，常见的查找算法有线性查找、二分法查找、哈希表查找等等。其中二分法查找适用于已经排序的序列，时间复杂度为O(logn)；哈希表查找适用于无序序列时间复杂度可达到O(1)。

1.2.3 变序算法

变序算法的性能优化方法主要是减少数据访问次数，例如在计算机图形学中常用的octree空间索引算法，通过将数据存储在八叉树结构中可以实现高效的空间数据查询。

1.3 基于范型编程的算法设计

范型编程是一种基于模板和泛型的编程思想，可以有效地提高代码复用性和可扩展性。STL正是基于此思想设计的，因此STL的大多数算法都是基于范型编程的。

基于范型编程的算法设计主要体现在：使用模板参数代替实际数值类型，可以适用于多种不同数据类型的处理；使用STL的迭代器实现容器的访问和操作，可以适用于多种不同容器类型的处理。

例如在STL中sort函数使用迭代器实现对任意容器的排序操作
代码如下：

template <class RandomAccessIterator>
void sort(RandomAccessIterator first, RandomAccessIterator last);

其中RandomAccessIterator是随机访问迭代器，可以适用于多种不同容器类型的处理。
使用sort函数进行排序的代码示例：

#include <algorithm>
#include <vector>
#include <iostream>

using namespace std;

int main() {
    vector<int> v = {1, 2, 7, 4, 5, 6, 3, 8, 9, 0};

    std::sort(v.begin(), v.end());

    for (auto i : v) {
        cout << i << " "; // 输出排序后的结果
    }
    cout << endl;

    return 0;
}

五、小结回顾

本文主要介绍了Standard Template Library 中的三个核心组件：容器、迭代器和算法。容器是用于存储和管理数据的对象，包括vector、list、set、map等。而迭代器是容器的访问方式用于遍历容器中的元素。最后介绍了STL算法的基本分类、应用场景以及复杂度分析，STL是C++编程中重要掌握部分其知识对于提高程序开发效率和编程能力至关重要，让我们下篇文章继续学习。

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/144176.html