STL概要，初识别STL

STL，即Standard Template Library，标准模板库，是C++标准库的一个重要组成部分。它是一个可复用的封装好的组件库，同时也是一个包罗数据结构与算法的软件框架。STL为C++程序员们提供了一个可扩展的应用框架，高度体现了软件的封装性与可复用性。

STL包含了诸多在计算机科学领域里所常用的数据结构和基本算法，提供了许多通用的模板类和函数，用于实现常用的数据结构和算法。STL的一个重要特点是数据结构和算法的分离，它允许程序员编写通用的代码，即可适用于不同的数据类型，而不必为每种类型编写不同的代码。

STL的六大组件包括容器（Containers）、迭代器（Iterators）、算法（Algorithms）、仿函数（Functors）、适配器（Adapters）和空间配置器（Allocators）。

其中，

1. 容器负责存储和管理数据，每种容器相当于定义好的一个反映数据结构的类（模板类）：如字符串（string）、向量（vector）、列表（list）、双端队列（deque）、栈（stack）、队列（queue）、优先队列（priority_queue）、集合（set）、映射（map）等。
2. 迭代器则用于遍历容器中的元素。
3. 算法是对容器中的数据进行操作的函数，分为质变算法和非质变算法。
4. 仿函数和行为类似于函数的对象，可以作为算法的参数以定制算法的行为。
5. 适配器用于修改容器或迭代器的接口以提供不同的功能。
6. 空间配置器则负责内存的分配和释放。

1.STM容器

容器：存储数据的数据结构类，如vector、deque、list等，C++的string数据结构也是一个封装好的容器。

算法：对容器中的数据进行操作的函数模板，如排序、查找等。

迭代器：提供一种方法来访问容器中的元素。

仿函数：行为类似函数的对象，可以作为算法的参数来定制算法的行为。

适配器：用于修改容器或迭代器的接口，以提供不同的功能。

空间配置器：负责内存分配和释放的组件，通常不需要直接操作。

序列式容器

序列式容器中的元素按照插入顺序进行存储。

Vector容器：又叫动态数组，支持随机访问。

#include <vector>  
#include <iostream>  
  
int main() {  
    std::vector<int> vec = {1, 2, 3, 4, 5};  
    for (const auto& element : vec) {  
        std::cout << element << " ";  
    }  
    return 0;  
}

Deque容器：双端队列，支持在头部和尾部进行插入和删除操作。

#include <deque>  
#include <iostream>  
  
int main() {  
    std::deque<int> deq = {1, 2, 3, 4, 5};  
    deq.push_front(0); // 在头部插入元素  
    deq.push_back(6); // 在尾部插入元素  
    for (const auto& element : deq) {  
        std::cout << element << " ";  
    }  
    return 0;  
}

List容器：双向链表，支持在任意位置进行插入和删除操作。

#include <list>  
#include <iostream>  
  
int main() {  
    std::list<int> lst = {1, 2, 3, 4, 5};  
    lst.push_front(0); // 在头部插入元素  
    lst.push_back(6); // 在尾部插入元素  
    for (const auto& element : lst) {  
        std::cout << element << " ";  
    }  
    return 0;  
}

关联式容器

关联式容器中的元素通过关键字进行存储和访问。关联式容器是非线性的树结构，更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系，也就是说元素在容器中并没有维持元素置入容器时的逻辑顺序。

Set/multiset容器：集合，存储唯一或重复的元素。

#include <set>  
#include <iostream>  
  
int main() {  
    std::set<int> s = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};  
    for (const auto& element : s) {  
        std::cout << element << " ";  
    }  
    return 0;  
}

Map/multimap容器：键值对集合，存储不重复/重复的键及其对应的值。

#include <map>  
#include <iostream>  
  
int main() {  
    std::map<std::string, int> m = {{"Alice", 25}, {"Bob", 30}, {"Charlie", 35}};  
    for (const auto& pair : m) {  
        std::cout << pair.first << ": " << pair.second << std::endl;  
    }  
    return 0;  
}

2算法

质变算法 质变算法会改变容器内元素的内容。

拷贝算法：例如std::copy。

#include <vector>  
#include <algorithm>  
#include <iostream>  
#include <iterator>  
  
int main() {  
    std::vector<int> src = {1, 2, 3, 4, 5};  
    std::vector<int> dst(src.size());  
    std::copy(src.begin(), src.end(), dst.begin());  
    for (const auto& element : dst) {  
        std::cout << element << " ";  
    }  
    return 0;  
}

非质变算法 非质变算法不会改变容器内元素的内容。

查找算法：例如std::find。 继续上面的内容讲解，我们来看非质变算法的一个例子——std::find。

#include <vector>  
#include <algorithm>  
#include <iostream>  
  
int main() {  
    std::vector<int> vec = {1, 2, 3, 4, 5};  
    auto it = std::find(vec.begin(), vec.end(), 3); // 查找值为3的元素  
    if (it != vec.end()) {  
        std::cout << "Found: " << *it << std::endl;  
    } else {  
        std::cout << "Not found" << std::endl;  
    }  
    return 0;  
}

在这个例子中，std::find算法在vec容器中查找值为3的元素，并返回一个迭代器指向找到的元素。如果找不到，则返回end()迭代器。

3.迭代器与遍历

迭代器提供了一种方法来遍历容器中的元素。上面的算法例子中已经展示了如何使用冒号遍历，当然数组可以用[]遍历，STL提供的新的遍历方法：使用迭代器。迭代器类似于指针，但提供了更安全的访问方式。STL提供了不同类型的迭代器，如输入迭代器、输出迭代器、前向迭代器、双向迭代器、随机访问迭代器等，每种类型支持不同的操作集。它使得程序员能够遍历容器（如vector、map、set等）中的元素，同时隐藏了底层数据结构的实现细节。迭代器就像是指向容器中元素的指针或引用，但它比指针更加类型安全，并且可以处理不同类型的容器。 语法是T<类>::iterator 迭代器指针名字 =。 begin()这个接口返回一个指向容器第一个元素的迭代器。end()这个接口返回一个指向容器“尾后”位置的迭代器。注意，这不是容器的最后一个元素，而是最后一个元素再之后的位置。对于空容器，begin() 返回的迭代器与 end() 返回的迭代器是相等的。

下面是对vector、map和set使用迭代器进行遍历的示例代码：

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 使用迭代器遍历vector
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 使用基于范围的for循环遍历vector（C++11及以后）
    for (int val : vec) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

#include <iostream>
#include <map>

int main() {
    std::map<std::string, int> myMap = {{"apple", 1}, {"banana", 2}, {"cherry", 3}};

    // 使用迭代器遍历map
    for (std::map<std::string, int>::iterator it = myMap.begin(); it != myMap.end(); ++it) {
        std::cout << it->first << ": " << it->second << std::endl;
    }

    // 使用基于范围的for循环遍历map（C++11及以后）
    for (const auto& kv : myMap) {
        std::cout << kv.first << ": " << kv.second << std::endl;
    }

    return 0;
}

#include <iostream>
#include <set>

int main() {
    std::set<int> mySet = {1, 3, 5, 7, 9};

    // 使用迭代器遍历set
    for (std::set<int>::iterator it = mySet.begin(); it != mySet.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 使用基于范围的for循环遍历set（C++11及以后）
    for (int val : mySet) {
        std::cout << val << " ";
    }
    std::cout << std::endl;

    return 0;
}

在上面的代码中，可以看到对于vector、map和set，我们都可以使用传统的迭代器进行遍历，也可以使用C++11及以后版本的基于范围的for循环进行遍历。基于范围的for循环更加简洁，易于理解。但需要注意的是，基于范围的for循环在遍历map时，返回的是键值对（key-value pair），而不是单独的键或值。 注意map和set不支持用数组符号[]来遍历和索引。

4.仿函数

仿函数是行为类似于函数的对象。它们可以像函数一样被调用，并可以作为算法的参数，以定制算法的行为，一般配合 algorithm 使用。例如，std::less<T>是一个仿函数，用于比较两个对象是否一个小于另一个。

#include <vector>  
#include <algorithm>  
#include <iostream>  
  
struct IsEven {  
    bool operator()(int n) const {  
        return n % 2 == 0;  
    }  
};  
  
int main() {  
    std::vector<int> vec = {1, 2, 3, 4, 5};  
    vec.erase(std::remove_if(vec.begin(), vec.end(), IsEven()), vec.end());  
    for (const auto& element : vec) {  
        std::cout << element << " ";  
    }  
    return 0;  
}

在这个例子中，我们定义了一个仿函数IsEven，它接受一个整数并检查它是否为偶数。然后，我们使用std::remove_if算法和IsEven仿函数来移除vec中所有的偶数。

5.适配器

适配器用于修改容器或迭代器的接口，以提供不同的功能。例如，std::stack和std::queue就是基于std::deque或std::list等容器的适配器，它们提供了栈和队列的接口。

#include <stack>  
#include <iostream>  
  
int main() {  
    std::stack<int> stk;  
    stk.push(1);  
    stk.push(2);  
    stk.push(3);  
    while (!stk.empty()) {  
        std::cout << stk.top() << " ";  
        stk.pop();  
    }  
    return 0;  
}

在这个例子中，我们使用了std::stack适配器来创建一个栈，并使用其提供的push、pop和top等方法来操作栈。

6.空间适配器

空间配置器负责内存的分配和释放。在STL中，它通常被封装起来，不需要直接操作。空间配置器允许STL库更高效地管理内存，特别是在大量小对象的情况下。