STL库：C++数据结构与算法

一、STL概述

C++ STL（Standard Template Library）是C++标准库的重要组成部分，它是一组通用的模板类和函数，实现了大量的常用数据结构和算法，为我们提供了高效、可靠和安全的工具，简化了程序设计和开发。STL库中包含了以下容器：

• 容器（Containers）
• 迭代器（Iterators）
• 算法（Algorithms）
• 函数对象（Function Objects）
• 适配器（Adapters）

STL库的设计理念是以泛型编程为基础，将数据类型和算法分开设计，使得数据结构和算法可以独立地发展和变换，从而实现代码的可重用性和可扩展性。

二、容器

容器是用于存储和管理数据的类模板，它们定义了一系列与数据操作有关的成员函数，可以快速地对数据进行插入、删除、查找等操作。常用的STL容器有以下几种：

1. vector

vector是一种动态数组，可以根据需要自动调整容量，实现高效的随机访问和插入/删除操作。例如：

#include <iostream>
#include <vector>
using namespace std;
int main() {
  vector<int> v;
  v.push_back(1);
  v.push_back(2);
  v.push_back(3);
  for (int i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
  }
  return 0;
}

输出结果为：1 2 3

2. list

list是一种双向链表，可以在任何位置进行插入和删除操作，但不支持随机访问。例如：

#include <iostream>
#include <list>
using namespace std;
int main() {
  list<int> l;
  l.push_back(1);
  l.push_back(2);
  l.push_back(3);
  for (auto iter = l.begin(); iter != l.end(); iter++) {
    cout << *iter << " ";
  }
  return 0;
}

输出结果为：1 2 3

3. map

map是一种关联容器，可以将键值对（Key-Value）组合存储，支持按照键值进行查找和删除等操作。例如：

#include <iostream>
#include <map>
using namespace std;
int main() {
  map<string, int> m;
  m["apple"] = 1;
  m["banana"] = 2;
  m["orange"] = 3;
  for (auto iter = m.begin(); iter != m.end(); iter++) {
    cout << iter->first << " " << iter->second << endl;
  }
  return 0;
}

输出结果为：

apple 1
banana 2
orange 3

三、迭代器

迭代器是一种通用的数据访问方式，可以方便地遍历STL容器中的元素，常用的迭代器类型有以下几种：

1. Input Iterator

Input Iterator是一个只读的迭代器，它可以对容器中的数据进行遍历和读取，例如：

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

输出结果为：1 2 3

2. Output Iterator

Output Iterator是一个只写的迭代器，它可以向容器中写入数据，例如：

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

输出结果为：2 4 6

3. Forward Iterator

Forward Iterator是一种单向的迭代器，它支持递增和取值操作，例如：

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

输出结果为：1 2 3

4. Bidirectional Iterator

Bidirectional Iterator是一种双向的迭代器，它可以向前和向后遍历容器中的元素，例如：

#include <iostream>
#include <list>
using namespace std;
int main() {
  list<int> l = {1, 2, 3};
  for (auto iter = l.rbegin(); iter != l.rend(); iter++) {
    cout << *iter << " ";
  }
  return 0;
}

输出结果为：3 2 1

5. Random Access Iterator

Random Access Iterator是一种随机访问的迭代器，可以快速定位到容器中的任意位置，并进行读写操作，例如：

#include <iostream>
#include <vector>
using namespace std;
int main() {
  vector<int> v = {1, 2, 3};
  cout << v[1] << endl; // 输出 2
  v[1] = 4;
  for (auto iter = v.begin(); iter != v.end(); iter++) {
    cout << *iter << " ";
  }
  return 0;
}

输出结果为：1 4 3

四、算法

算法是STL库中非常重要的一部分，提供了大量的常用算法，包括查找、排序、遍历、合并等操作。

1. 查找

STL库中提供了多种查找算法，包括二分查找、线性查找、查找最大/最小值等。

例如，使用二分查找算法：（前提是数据序列已经排好序）

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
  int a[] = {1, 2, 3, 4, 5};
  cout << binary_search(a, a + 5, 4) << endl; // 输出 1
  return 0;
}

2. 排序

STL库中提供了多种排序算法，包括快速排序、归并排序、堆排序等，其中最常用的是快速排序。

例如，使用快速排序算法：（vector会使用快排）

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

输出结果为：1 2 3 4 5

3. 遍历

STL库中提供了多种遍历算法，包括for_each、transform等，这些算法可以对容器中的元素进行操作并输出。

例如，使用for_each算法将vector中的每个元素乘以2并输出：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void print(int n) {
  cout << n * 2 << " ";
}
int main() {
  vector<int> v = {1, 2, 3};
  for_each(v.begin(), v.end(), print);
  return 0;
}

输出结果为：2 4 6

4. 合并

STL库中提供了多种合并算法，包括merge、set_union等，这些算法可以将多个有序的序列合并成一个有序的序列。

例如，使用merge算法将两个vector合并成一个有序的序列并输出：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
  vector<int> v1 = {1, 3, 5};
  vector<int> v2 = {2, 4, 6};
  vector<int> v3(v1.size() + v2.size());
  merge(v1.begin(), v1.end(), v2.begin(), v2.end(), v3.begin());
  for (auto iter = v3.begin(); iter != v3.end(); iter++) {
    cout << *iter << " ";
  }
  return 0;
}

输出结果为：1 2 3 4 5 6

五、函数对象

函数对象是STL库中的一种概念，是一种重载了运算符()的类，可以像函数一样进行调用，可以用于算法中的比较、计算等操作。

1. 比较函数对象

比较函数对象是一种用于比较两个元素大小的函数对象，常用于sort、max_element等算法中。

例如，比较函数对象的实现：

struct cmp {
  bool operator()(int a, int b) const {
    return a < b;
  }
};

使用比较函数对象对vector进行排序：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct cmp {
  bool operator()(int a, int b) const {
    return a < b;
  }
};
int main() {
  vector<int> v = {3, 1, 4, 2, 5};
  sort(v.begin(), v.end(), cmp());
  for (auto iter = v.begin(); iter != v.end(); iter++) {
    cout << *iter << " ";
  }
  return 0;
}

输出结果为：1 2 3 4 5

2. 计算函数对象

计算函数对象是一种用于计算表达式的函数对象，常用于accumulate等算法中。

例如，计算函数对象的实现：

struct plus_functor {
  int operator()(int a, int b) const {
    return a + b;
  }
};