C++中的STL：一些常用的STL容器和算法

本是古典何须时尚 2023-10-13 14:36 49阅读 0赞

#### 文章目录 ####

*  对组（Pair）
 *  向量（Vectors）
 *  列表（Lists）
 *  栈（Stack）
 *  队列（Queue）
 *  集合（Sets）
 *  映射（Maps）
 *   *  Multimap
     *  Unordered Map

STL（Standard Template Library）是C++中一个强大的库，用于处理数据结构。它提供了一系列预定义的工具，如算法、容器和迭代器，可以轻松地在程序中使用。

STL的主要目标是提供一种灵活和高效的处理数据结构和算法的方式。它通过提供具有明确规则和模板的现成工具来实现这一目标。这意味着您可以在不担心性能问题的情况下，使用这些工具处理不同类型的数据。

STL分为四个主要部分：算法、容器、函数和迭代器。算法是执行常见任务（如排序、搜索和操作项目集合）的函数。容器是数据结构，如向量、链表、集合、映射和队列，可以高效地存储和管理元素。迭代器作为助手，让您遍历容器中的元素并对其进行修改。

简而言之，STL是C++中一个有用的库，提供了处理数据结构的工具。它通过提供预定义的函数和数据结构，帮助您节省时间并编写高效的代码。

一个包含所有标准函数、算法和容器的头文件是：

#include <bits/stdc++.h>

STL容器是C++中预定义的数据结构，提供了高效的存储和管理元素的方式。常见的容器包括向量、列表、集合、映射和队列。它们提供了用于常见操作的现成实现，并可以轻松地集成到你的程序中，以实现有效的数据管理。

常见的STL容器有：

## 对组（Pair） ##

`pair`是C++中一个强大的工具，允许你将两个不同类型的值组合成一个实体。当你需要关联两个相关的信息时，通常会使用`pair`。

#include<iostream>
    #include<utility>
    using namespace std; 
    
    int main() {
        
        pair<string, int> person;
        person.first = "John";
        person.second = 25;
    
        cout << "Name: " << person.first << endl;
        cout << "Age: " << person.second << endl;
        return 0;
    }

## 向量（Vectors） ##

`vector`是C++中一个多用途、动态的数据结构，提供了一个可调整大小的类似数组的容器。它允许你按顺序存储和操作一组元素。

有多种声明`vector`的方式，包括：

*  `v(5, 100)`：这种语法创建了一个名为`v`的`vector`，初始大小为5个元素，每个元素的值都初始化为100。换句话说，它创建了一个包含五个元素的`vector`，所有元素的值都设置为100。
 *  `v(5)`：这种语法创建了一个名为`v`的`vector`，初始大小为5个元素，但没有指定具体的初始值。根据元素的类型，默认初始化元素。例如，如果`vector`的类型是`int`，元素将被初始化为0。
 *  `v()`：这种语法创建一个空的`vector`，没有初始元素。实际上，这是一个没有指定初始大小或值的`vector`声明。当你计划根据程序的需求动态添加元素时，这很有用。

可以通过两种方式访问存储在`vector`中的值：

1.  直接访问值：

#include <iostream>
    #include <vector>
    using namespace std;
    
    int main() {
        
        vector<int> numbers = {
        1, 2, 3, 4, 5};
        for (auto it : numbers)
            cout << it << " ";
    
        return 0;
    }

1.  通过迭代器访问：

#include <iostream>
    #include <vector>
    using namespace std;
    
    int main() {
        
        vector<int> numbers = {
        1, 2, 3, 4, 5};
        for (auto it = numbers.begin(); it != numbers.end(); ++it)
            cout << *it << " ";
    
        return 0;
    }

## 列表（Lists） ##

列表是C++中的双向链表数据结构。它是一个容器，允许在列表的两端和中间高效地插入和删除元素。列表中的每个元素都与指向前一个元素和后一个元素的指针一起存储。

从技术上讲，列表被实现为节点序列，其中每个节点包含元素值和两个指针：一个指向前一个节点，另一个指向后一个节点。这种链接结构相对于其他容器类型来说，能够实现高效的插入和删除操作。

列表STL提供了一系列操作来操作列表中的元素。您可以轻松地在列表的开头或结尾添加元素，插入任意位置的元素，删除元素，并使用迭代器遍历列表。

要使用列表STL，您需要包含头文件。

#include <iostream>
    #include <list>
    using namespace std;
    
    int main() {
        
        list<int> numbers;
        numbers.push_back(10);
        numbers.push_front(5);
    
        list<int>::iterator it = numbers.begin();
        ++it;
        numbers.insert(it, 7);
        numbers.pop_back();
    
        for (auto it = numbers.begin(); it != numbers.end(); ++it)
            cout << *it << " ";
        cout << endl;
    
        return 0;
    }

push\_back()函数用于在列表的末尾添加一个元素，push\_front()用于在列表的开头添加一个元素，insert()用于在特定位置插入一个元素。

pop\_back()函数从列表中删除最后一个元素。

与向量相比，列表在处理数据之间的操作时具有更好的时间复杂度。

## 栈（Stack） ##

请点击此处访问有关栈数据结构的博客文章。

## 队列（Queue） ##

队列是C++中的先进先出（FIFO）数据结构。它是一个容器，允许在一端插入元素，在另一端删除元素。最先插入的元素将最先被删除。

从技术上讲，队列被实现为一个容器适配器，这意味着它使用一个底层容器（如deque或list）来存储元素。队列提供了enqueue（插入元素）和dequeue（删除元素）等操作，遵循特定的规则来维护FIFO顺序。

队列STL提供了一系列操作来操作队列中的元素。您可以轻松地将元素添加到队列的后面，从队列的前面删除元素，并访问队列的前后元素。

要使用队列STL，您需要包含头文件。

#include <iostream>
    #include <queue>
    using namespace std;
    
    int main() {
        
        queue<int> numbers;
        numbers.push(10);
        numbers.push(20);
        numbers.push(30);
    
        cout << "队列的前端：" << numbers.front() << endl;
        cout << "队列的后端：" << numbers.back() << endl;
    
        numbers.pop();
        cout << "弹出元素后队列的前端：" << numbers.front() << endl;
    
        return 0;
    }

优先队列（std::priority\_queue numbers）是一种根据优先级存储元素的容器。具有较高优先级的元素将放置在前面，并且优先于具有较低优先级的元素。它使用二叉堆作为其底层数据结构，以高效地检索最高优先级的元素。优先队列通常用于需要按特定顺序处理元素的情况，例如任务调度或事件处理。默认情况下，优先队列按降序（最大堆）对元素进行排序，但可以使用比较函数或运算符重载自定义顺序。

可以使用以下语法实现升序：

priority_queue<int, vector<int>, greater<int>> numbers;

这种顺序也称为“最小堆”。由于它基于二叉堆的原理，push/pop函数的时间复杂度为O(log n)，而普通队列的push/pop函数的时间复杂度为O(1)。

## 集合（Sets） ##

集合是标准模板库中的关联容器，以特定顺序存储唯一元素。它使用平衡二叉搜索树实现，可以高效地进行插入、删除和搜索操作。

集合保持元素的排序顺序，这意味着元素会自动按升序排列。唯一性属性确保集合中每个元素仅出现一次。

基本上，关于集合的主要要记住的事情是它们以排序顺序存储数据，所有元素都是唯一的。

多重集合是一个允许重复元素并将它们保持在排序顺序中的容器。插入、删除和搜索操作的时间复杂度为O(log n)，因为它们涉及遍历二叉搜索树。

无序集合是一个以无特定顺序存储唯一元素的容器。它使用哈希表实现，平均情况下提供常数时间复杂度的插入、删除和搜索操作。无序集合中的元素没有排序，但是唯一。lower\_bound()和upper\_bound()函数不适用于无序集合。

#include <iostream>
    #include <set>
    #include <unordered_set>
    using namespace std;
    
    int main() {
        
        // Set
        set<int> mySet;
        mySet.insert(30);
        mySet.insert(10);
        mySet.insert(20);
        mySet.insert(10);  // 重复元素被忽略
    
        for (auto it : mySet)
            cout << it << " ";
        cout << endl;
        // Multiset
        multiset<int> myMultiset;
        myMultiset.insert(30);
        myMultiset.insert(10);
        myMultiset.insert(20);
        myMultiset.insert(10);  // 允许重复元素
    
        for (auto it : myMultiset)
            cout << it << " ";
        cout << endl;
        // Unordered Set
        unordered_set<int> myUnorderedSet;
        myUnorderedSet.insert(30);
        myUnorderedSet.insert(10);
        myUnorderedSet.insert(20);
        myUnorderedSet.insert(10);  // 重复元素被忽略
    
        for (auto it : myUnorderedSet)
            cout << it << " ";
        cout << endl;
        return 0;
    }

输出：

10 20 30    
    10 10 20 30 
    20 10 30

## 映射（Maps） ##

Maps是一个关联容器，以键值对的形式存储元素。它允许根据键进行高效的查找、插入和删除元素。每个键在map中是唯一的，并且元素会根据键的升序自动排序。

map<int, int> mpp;

其中第一个int是键，第二个int是值。键是唯一的，并且默认以升序排序。每个值都与唯一的键相关联。map的时间复杂度是O(log n)。

### Multimap ###

multimap是一个关联容器，允许具有相同键的多个元素。它类似于map容器，但不同之处在于它允许重复的键。multimap中的每个元素由一个键值对组成，其中键用于对元素进行排序，值与这些键相关联。

multimap<int, string> myMultimap;
    myMultimap.insert({
        1, "Alice"});
    myMultimap.insert({
        2, "Bob"});
    myMultimap.insert({
        3, "Charlie"});
    myMultimap.insert({
        3, "David"});

### Unordered Map ###

unordered\_map是C++中提供的基于哈希的实现方式来存储键值对的容器。它提供了快速的查找、插入和删除操作，平均时间复杂度为常数。与multimap不同，unordered\_map不根据键来排序元素，而是依赖哈希函数将键映射到唯一的索引。这使得它适用于不重要元素顺序，但需要快速访问值的场景。

unordered_map<int, string> myUnorderedMap;
    myUnorderedMap[1] = "Alice";
    myUnorderedMap[2] = "Bob";
    myUnorderedMap[3] = "Charlie";

示例代码

#include <iostream>
    #include <map>
    #include <unordered_map>
    using namespace std;
    
    int main() {
        
        // Map
        map<int, string> myMap;
        myMap[1] = "Alice";
        myMap[2] = "Bob";
        myMap[3] = "Charlie";
    
        for (auto it : myMap)
            cout << it.first << ": " << it.second << endl;
        
        // Multimap
        multimap<int, string> myMultimap;
        myMultimap.insert({
        1, "Alice"});
        myMultimap.insert({
        2, "Bob"});
        myMultimap.insert({
        3, "Charlie"});
        myMultimap.insert({
        3, "David"});
    
        for (auto it : myMultimap)
            cout << it.first << ": " << it.second << endl;
        
        // Unordered Map
        unordered_map<int, string> myUnorderedMap;
        myUnorderedMap[1] = "Alice";
        myUnorderedMap[2] = "Bob";
        myUnorderedMap[3] = "Charlie";
    
        for (auto it : myUnorderedMap)
            cout << it.first << ": " << it.second << endl;
        
        return 0;
    }

输出结果

1: Alice
    2: Bob  
    3: Charlie
    1: Alice
    2: Bob
    3: Charlie
    3: David
    3: Charlie
    2: Bob
    1: Alice