STL容器介绍及基本操作

# 1. STL容器简介

当谈到C++的STL(Standard Template Library)时，容器是一个非常重要的概念。STL容器是一种用来存放数据的数据结构，它们提供了一种高效的方式来存储和访问数据。在C++中，STL容器分为多种类型，每种类型有着不同的特点和用途。

## 1.1 STL容器的定义和作用

STL容器是一种通用的数据结构，它提供了一系列的类模板，可以存储不同类型的数据。STL容器的作用在于提供了一种方便的方式来管理数据，使得程序员可以更加高效地操作数据，而不用关心底层数据结构的实现。

## 1.2 STL容器的分类

STL容器可以分为顺序容器、关联容器和容器适配器等几种类型。顺序容器按照存放数据的顺序来组织数据，关联容器则是根据键值对来组织数据，而容器适配器则提供了一种特殊的接口使得容器可以用作栈、队列或优先队列。

## 1.3 不同STL容器的特点和用途

不同类型的STL容器有着各自独特的特点和适用场景。例如，向量(vector)适用于需要高效随机访问的场景，而列表(list)适用于频繁插入和删除元素的场景。了解每种STL容器的特点和用途将有助于选择合适的容器来完成特定的任务。

# 2. 顺序容器

顺序容器是一种按照元素添加顺序存储数据的STL容器，常见的包括向量（vector）、列表（list）和双端队列（deque）。它们各自有着不同的特点和适用场景，下面将分别介绍它们的基本操作。

### 2.1 向量（vector）的特点和基本操作

向量是一种动态数组，可以动态扩展存储空间，支持随机访问和快速插入删除操作。下面是向量的基本操作示例（使用C++语言示范）：

#include <iostream>
#include <vector>

int main() {
    // 创建一个整型向量
    std::vector<int> vec;

    // 在向量末尾添加元素
    vec.push_back(10);
    vec.push_back(20);
    vec.push_back(30);

    // 遍历向量并输出元素
    for (int i = 0; i < vec.size(); i++) {
        std::cout << vec[i] << " ";
    }

    return 0;
}

上述代码演示了向量的创建、添加元素和遍历操作，输出结果为：10 20 30。

### 2.2 列表（list）的基本操作

列表是一种双向链表，支持快速插入和删除操作，但不支持随机访问。下面是列表的基本操作示例（使用Java语言示范）：

import java.util.LinkedList;

public class ListExample {
    public static void main(String[] args) {
        // 创建一个字符串列表
        LinkedList<String> list = new LinkedList<>();

        // 在列表末尾添加元素
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        // 遍历列表并输出元素
        for (String fruit : list) {
            System.out.print(fruit + " ");
        }
    }
}

上述代码演示了列表的创建、添加元素和遍历操作，输出结果为：Apple Banana Cherry。

### 2.3 双端队列（deque）的介绍与应用

双端队列是一种双向队列，支持在队列两端进行元素的插入和删除操作。它综合了向量和列表的特点，既支持快速随机访问，又支持快速插入删除。下面是双端队列的基本操作示例（使用Python语言示范）：

from collections import deque

# 创建一个双端队列
d = deque()

# 在队列两端添加元素
d.append(10)
d.appendleft(5)
d.append(20)

# 遍历队列并输出元素
for element in d:
    print(element, end=" ")

上述代码演示了双端队列的创建、添加元素和遍历操作，输出结果为：5 10 20。

通过学习顺序容器，读者可以更好地理解和应用STL容器，为实际开发提供更多选择和便利。

# 3. 关联容器

在STL中，关联容器主要包括集合（set）、映射（map）、多重集合（multiset）、多重映射（multimap）、无序集合（unordered_set）和无序映射（unordered_map）等几种类型。这些容器以其独特的数据结构和特点而被广泛应用。

#### 3.1 集合（set）和映射（map）的介绍

- **集合（set）**是一种元素不重复、有序的容器，其中的元素按照一定的排序规则进行排列。可以使用集合来快速查找、插入和删除元素，时间复杂度为O(log n)。

   // Java 示例：演示集合的基本操作
   import java.util.*;

   public class SetExample {
       public static void main(String[] args) {
           // 创建集合
           Set<Integer> set = new TreeSet<>();

           // 添加元素
           set.add(3);
           set.add(1);
           set.add(2);

           // 输出集合
           System.out.println("Set: " + set);

           // 遍历集合
           for (Integer num : set) {
               System.out.println(num);
           }
       }
   }

**代码总结：** 上述代码演示了Java中集合的基本操作，包括创建集合、添加元素、输出集合和遍历集合。

- **映射（map）**是一种键值对的容器，可以通过键快速查找对应的值，键是唯一的，值可以重复。可以用映射来实现字典、数据库等数据结构，时间复杂度为O(log n)。

   # Python 示例：演示映射的基本操作
   map_dict = {'name': 'Alice', 'age': 25, 'city': 'New York'}

   # 访问元素
   print("Name:", map_dict['name'])
   print("Age:", map_dict['age'])

   # 修改元素
   map_dict['age'] = 26
   print("Updated Age:", map_dict['age'])

   # 删除元素
   del map_dict['city']
   print("Map after deletion:", map_dict)

**代码总结：** 以上代码展示了Python中映射的基本操作，包括访问元素、修改元素和删除元素。

#### 3.2 多重集合（multiset）和多重映射（multimap）的应用

- **多重集合（multiset）**和**多重映射（multimap）**允许元素重复，但仍保持排序。在需要允许重复元素的情况下，可以使用这两种容器。

#### 3.3 无序集合（unordered_set）和无序映射（unordered_map）的操作

- **无序集合（unordered_set）**和**无序映射（unordered_map）**是基于哈希表实现的容器，元素的存储顺序不固定。在对存储顺序要求不高的场景下，可以选择这两种容器来提高查找效率。

关联容器在不同场景下具有不同的优势，选择适合的容器能够提高代码效率和性能。在实际开发中，根据需求合理选择关联容器是十分重要的。

# 4. 容器适配器

容器适配器是STL中一种特殊的容器，它们基于顺序容器或其他底层容器实现，并提供了特定功能的接口。本章将介绍几种常用的容器适配器及它们的基本操作。

#### 4.1 栈（Stack）的基本操作

栈是一种后进先出（LIFO）的数据结构，只允许在栈顶进行插入和删除操作。在STL中，栈是基于某个底层容器（例如vector, deque）实现的，提供了push、pop、top等操作。下面是一个Java示例：

import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        // 在栈顶插入元素
        stack.push(1);
        stack.push(2);
        stack.push(3);

        // 输出栈顶元素并删除
        System.out.println(stack.pop()); // 输出：3

        // 获取栈顶元素但不删除
        System.out.println(stack.peek()); // 输出：2
    }
}

**代码总结：**
- 使用Stack类实现栈数据结构。
- push方法向栈顶插入元素，pop方法返回并删除栈顶元素，peek方法返回但不删除栈顶元素。

**结果说明：** 上述代码实现了栈的基本操作，并成功添加、删除、获取栈顶元素。

#### 4.2 队列（Queue）的使用方法

队列是一种先进先出（FIFO）的数据结构，在STL中，队列也是基于底层容器实现的，提供了push、pop、front等操作。下面是一个Go示例：

package main

import "fmt"

func main() {
    queue := []int{}

    // 在队尾插入元素
    queue = append(queue, 1)
    queue = append(queue, 2)
    queue = append(queue, 3)

    // 弹出队首元素
    front := queue[0]
    queue = queue[1:]
    fmt.Println(front) // 输出：1

    // 获取队首元素
    fmt.Println(queue[0]) // 输出：2
}

**代码总结：**
- 使用切片实现队列数据结构。
- append方法向队列尾部插入元素，通过切片操作实现从队首弹出元素。

**结果说明：** 以上代码展示了队列的基本操作，成功插入元素、弹出队首元素并获取队首元素。

#### 4.3 优先队列（Priority Queue）的特点和操作

优先队列是一种按照元素优先级排序的队列，每次弹出的元素是优先级最高的。在STL中，优先队列通常基于堆（heap）实现，提供了push、pop、top等操作。以下为JavaScript示例：

class PriorityQueue {
    constructor() {
        this.heap = [];
    }

    push(value) {
        this.heap.push(value);
        this.heap.sort((a, b) => b - a); // 根据元素大小降序排序
    }

    pop() {
        return this.heap.pop();
    }

    top() {
        return this.heap[this.heap.length - 1];
    }
}

// 使用优先队列
const pq = new PriorityQueue();
pq.push(3);
pq.push(1);
pq.push(2);

console.log(pq.pop()); // 输出：1
console.log(pq.top()); // 输出：3

**代码总结：**
- 使用数组实现优先队列数据结构，通过数组排序实现按优先级弹出元素。
- push方法向优先队列插入元素，pop方法弹出优先级最高的元素，top方法获取优先级最高的元素。

**结果说明：** 上述代码展示了优先队列的基本操作，成功实现按优先级弹出元素和获取优先级最高的元素。

# 5. 迭代器

迭代器（Iterator）是C++标准模板库（STL）中用来遍历容器中元素的一种对象。通过迭代器，我们可以访问容器中的元素并对其进行操作，实现了对容器的统一访问接口。在STL中，迭代器被广泛应用于各种算法中，从而实现了对容器的操作。

### 5.1 迭代器的定义和分类

迭代器可以分为五种不同的类型，根据其所支持的操作分为输入迭代器（Input Iterator）、输出迭代器（Output Iterator）、前向迭代器（Forward Iterator）、双向迭代器（Bidirectional Iterator）和随机访问迭代器（Random Access Iterator）。不同类型的迭代器支持的操作也略有不同。

在使用迭代器时，我们可以通过`begin()`和`end()`方法获取容器的起始迭代器和终止迭代器，以便进行遍历操作。

# 示例代码：使用迭代器遍历列表
my_list = [1, 2, 3, 4, 5]

# 使用迭代器遍历列表
iterator = iter(my_list)
while True:
    try:
        print(next(iterator))
    except StopIteration:
        break

### 5.2 迭代器的基本操作和应用场景

迭代器的基本操作包括`*`取值操作、`++`迭代操作等。在实际应用中，我们经常会使用迭代器结合算法来完成对容器的遍历、查找、排序等操作。

// 示例代码：使用迭代器查找元素
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;

public class Main {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(1);
        numbers.add(2);
        numbers.add(3);
        numbers.add(4);
        ListIterator<Integer> iterator = numbers.listIterator();
        while (iterator.hasNext()) {
            int num = iterator.next();
            if (num == 3) {
                System.out.println("找到了元素3！");
                break;
            }
        }
    }
}

通过迭代器，我们可以实现对容器的灵活操作，而不必关心容器的内部实现细节。迭代器的使用可以大大简化我们对容器的操作，并提高代码的可读性和可维护性。

# 6. STL容器高级操作

在这一章节中，我们将学习如何进行STL容器的高级操作，包括容器间的交换和拷贝、容器的排序和查找算法、以及如何自定义容器的比较函数。

### 6.1 容器间的交换和拷贝

在STL中，我们可以通过`std::swap`函数来实现两个容器的元素交换。例如，在C++中，我们可以这样交换两个vector：

#include <iostream>
#include <vector>

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

    std::swap(vec1, vec2);

    // 输出交换后的结果
    for (int num : vec1) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    for (int num : vec2) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

在上面的代码中，我们使用`std::swap`函数来交换了两个vector的内容，最终输出的结果是：

4 5 6 
1 2 3 

除了`std::swap`外，我们还可以使用`std::copy`函数来实现容器的拷贝。以下是一个示例：

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

int main() {
    std::vector<int> vec1 = {1, 2, 3};
    std::vector<int> vec2(3);

    std::copy(vec1.begin(), vec1.end(), vec2.begin());

    // 输出拷贝后的结果
    for (int num : vec2) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

上面的代码将vec1的内容拷贝到vec2中，并输出结果：

1 2 3 

### 6.2 容器的排序和查找算法

在STL中，我们可以使用`std::sort`函数对容器进行排序，也可以使用`std::find`函数在容器中查找特定元素。以下是一个示例：

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

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

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

    // 输出排序后的结果
    for (int num : vec) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // 查找元素5
    auto it = std::find(vec.begin(), vec.end(), 5);

    if (it != vec.end()) {
        std::cout << "Element 5 found at index: " << it - vec.begin() << std::endl;
    } else {
        std::cout << "Element 5 not found" << std::endl;
    }

    return 0;
}

上面的代码首先对vector进行排序，然后查找元素5，并输出结果：

1 1 2 3 4 5 5 6 9 
Element 5 found at index: 5

### 6.3 自定义容器比较函数

有时候，我们可能需要在容器中存储自定义类型的数据，并对其进行比较。我们可以通过自定义比较函数或者重载比较运算符来实现。以下是一个示例：

#include <iostream>
#include <set>

class Person {
public:
    std::string name;
    int age;

    Person(std::string name, int age) : name(name), age(age) {}

    bool operator<(const Person& rhs) const {
        return age < rhs.age;
    }
};

int main() {
    std::set<Person> personSet;
    personSet.insert(Person("Alice", 25));
    personSet.insert(Person("Bob", 30));
    personSet.insert(Person("Charlie", 20));

    for (const Person& person : personSet) {
        std::cout << person.name << " " << person.age << std::endl;
    }

    return 0;
}

在上面的代码中，我们定义了一个Person类，并重载了小于运算符，按照年龄从小到大排序。最终输出的结果是：

Charlie 20
Alice 25
Bob 30

通过以上示例，我们可以灵活运用STL容器提供的高级操作，对容器进行更加复杂的处理和管理。