C++ STL：标准库中的容器类和算法

一、STL简介

STL（Standard Template Library）是C++标准库的一部分，是一种基于模板的泛型编程技术，提供了一系列高效、可重用、通用的算法、容器和函数对象。STL以一种通用且可扩展的方式提供了许多数据结构和算法。STL的设计遵循了泛型编程的原则，可以轻松地扩展或修改数据结构与算法，使得程序员可以快速地开发高质量、高效率的程序。

二、STL组成

STL主要由三个部分组成：容器、算法和迭代器。

1. 容器

容器是存储数据的对象，也称为数据结构。STL库提供了多种不同类型的容器，适合于不同的应用场景，包括：

• 序列容器（如vector、deque和list）：存储线性数据，按照插入顺序排列。
• 关联容器（如set、map和multimap）：存储按照一定规则排序的数据。
• 容器适配器（如stack、queue和priority_queue）：是实现特定数据结构的一种容器。

//示例代码：vector容器使用
#include 
#include 
   
using namespace std;

int main(){
    // 定义一个整型vector，名为vec
    vector
     vec;
    vec.push_back(10); // 在vec的尾部插入10
    vec.push_back(20); // 在vec的尾部插入20
    vec.push_back(30); // 在vec的尾部插入30

    // 输出vec的所有元素
    for(auto i : vec){
        cout << i << " ";
    }
    return 0;
}

    
   
  

2. 算法

算法是STL的核心部分，提供了一系列通用的算法，包括搜索、排序、遍历、拷贝、替换等。这些算法都是基于迭代器实现的，使得很容易将它们与任意容器结合使用。

• 常用算法：sort、find、count等。

//示例代码：使用sort算法对vector进行排序
#include 
#include 
   
#include 
    
using namespace std;

int main(){
    vector
      vec = {5, 3, 6, 2, 7, 1, 4};

    // 打印排序前的vector
    cout << "before sorting: ";
    for (auto i : vec) {
        cout << i << " ";
    }
    cout << endl;

    // 对vector进行排序
    sort(vec.begin(), vec.end());

    // 打印排序后的vector
    cout << "after sorting: ";
    for (auto i : vec) {
        cout << i << " ";
    }
    cout << endl;

    return 0;
}

     
    
   
  

3. 迭代器

迭代器是一种抽象的访问和遍历容器（或其他数据序列）中的元素的对象。迭代器提供了一种通用的方法来遍历容器内的元素，容器的具体实现方式对用户是透明的。在STL中，迭代器被视为通用的接口，可以应用于所有容器类型，甚至是用户自定义的容器类型或数据结构。

• 迭代器分类：输入迭代器、输出迭代器、正向迭代器、双向迭代器、随机访问迭代器。

//示例代码：迭代器遍历vector
#include 
#include 
   
using namespace std;

int main(){
    vector
     vec{1, 2, 3, 4, 5};

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

    return 0;
}

     
    
   
  

三、C++11中新增容器

C++11标准中新增了多种容器类型，包括了更多的序列容器和关联容器，有些容器实现类似于现有的容器，但还有一些提供了新的功能和更好的性能：

• array：固定大小的数组。
• forward_list：单向链表，相比于list，占用更少的内存，但某些操作可能更慢。
• unordered_set和unordered_map：无序的关联容器，通过哈希表实现，具有快速查询的特点，但可能牺牲一定的空间。

//示例代码：使用unordered_map容器存储键值对
#include 
#include 
   
using namespace std;

int main(){
    // 创建一个空的unordered_map
    unordered_map
     mymap;

    // 向unordered_map中插入元素
    mymap.emplace("apple", 1);
    mymap.emplace("orange", 2);
    mymap.emplace("banana", 3);

    // 遍历unordered_map中的元素
    for (auto& kv : mymap) {
        cout << kv.first << ": " << kv.second << '\n';
    }

    return 0;
}

    
   
  

四、STL的优点和缺点

1. 优点

• STL提供了大量的通用算法和容器，可大大减少程序员的开发量，提高开发效率。
• STL使用模板技术，使得算法和容器的实现与数据类型的无关，可重用性和可扩展性极高。
• STL的迭代器机制提供了一种通用的遍历方式，使得任何容器类型都可以进行遍历。

2. 缺点

• STL提供的通用算法和容器并不一定是最高效的，程序员需要针对具体情况选择合适的数据结构和算法。
• STL的语法相对比较复杂，使用起来需要一定的学习成本。
• STL在处理大量数据时，可能出现内存占用较高的情况。