C++ STL 教程学习笔记
本文旨在介绍C++ STL的常用数据结构与算法，帮助读者更好的掌握C++编程语言。
STL概述
STL（Standard Template Library）是C++标准程序库中的一部分，提供了一系列常用数据结构与算法，包括但不限于容器（Container）、迭代器（Iterator）和算法（Algorithm）。STL的设计使用了模板（Template），能够为不同的数据类型提供相同的接口，使得用户可以集中精力于算法的实现，而无需手动编写底层数据结构。
容器（Container）
顺序容器
vector
vector是STL中最常用的容器之一，它是一个动态数组，元素在内存上连续存储，支持随机访问。vector的优点在于能够根据需要自动扩展或收缩容量，能够高效地进行随机访问，适合于大量元素的快速操作。
c++Copy Code#include <iostream>
#include <vector>
using namespace std;
int main()
{
// 创建一个空的vector
vector<int> v1;
// 在尾部插入元素
v1.push_back(1);
v1.push_back(2);
v1.push_back(3);
// 使用下标随机访问元素
cout << v1[0] << endl;
// 使用迭代器遍历元素
for (auto it = v1.begin(); it != v1.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
return 0;
}
list
list是另一种常用的顺序容器，它是一个双向链表，支持快速插入和删除元素，但不支持随机访问。list的优点在于能够高效地进行插入和删除操作，适合于需要频繁修改的场景。
c++Copy Code#include <iostream>
#include <list>
using namespace std;
int main()
{
// 创建一个空的list
list<int> l1;
// 在尾部插入元素
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
// 在头部插入元素
l1.push_front(0);
// 使用迭代器遍历元素
for (auto it = l1.begin(); it != l1.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
// 删除尾部元素
l1.pop_back();
// 删除头部元素
l1.pop_front();
// 使用迭代器遍历元素
for (auto it = l1.begin(); it != l1.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
return 0;
}
关联容器
map
map是一种键值对容器，支持快速查找和修改元素，按键进行排序。map的优点在于能够高效地进行查找和修改操作，适合于需要频繁查询的场景。
c++Copy Code#include <iostream>
#include <map>
using namespace std;
int main()
{
// 创建一个空的map
map<string, int> m1;
// 插入元素
m1["one"] = 1;
m1["two"] = 2;
m1["three"] = 3;
// 使用迭代器遍历元素
for (auto it = m1.begin(); it != m1.end(); ++it)
{
cout << it->first << " " << it->second << endl;
}
// 查询元素
cout << m1["one"] << endl;
// 修改元素
m1["one"] = 10;
// 使用迭代器遍历元素
for (auto it = m1.begin(); it != m1.end(); ++it)
{
cout << it->first << " " << it->second << endl;
}
return 0;
}
set
set是一种集合容器，支持快速查找和插入元素，按元素值进行排序。set的优点在于能够高效地进行查找和插入操作，且元素唯一，适合于需要去重和排序的场景。
c++Copy Code#include <iostream>
#include <set>
using namespace std;
int main()
{
// 创建一个空的set
set<int> s1;
// 插入元素
s1.insert(1);
s1.insert(2);
s1.insert(3);
// 使用迭代器遍历元素
for (auto it = s1.begin(); it != s1.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
// 查询元素
if (s1.find(2) != s1.end())
cout << "found" << endl;
// 删除元素
s1.erase(2);
// 使用迭代器遍历元素
for (auto it = s1.begin(); it != s1.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
return 0;
}
迭代器（Iterator）
迭代器是一种抽象的概念，类似于指针，可以用于访问容器中的元素。STL中提供了五种迭代器，分别为输入迭代器（Input Iterator）、输出迭代器（Output Iterator）、前向迭代器（Forward Iterator）、双向迭代器（Bidirectional Iterator）和随机访问迭代器（Random Access Iterator）。不同类型的迭代器支持的操作也不同，但都具有类似于指针的行为，能够进行解引用、自增等操作。
c++Copy Code#include<iostream>
#include<vector>
using namespace std;
int main()
{
vector<int> v{1,2,3};
// 使用迭代器遍历元素
for(auto it = v.begin(); it != v.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
return 0;
}
算法（Algorithm）
STL中提供了许多常用算法，如查找、排序、复制等等。这些算法能够为不同类型的容器提供相同的接口，使得用户无需考虑底层实现，而只需要关注算法本身。
c++Copy Code#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(int a, int b)
{
return a > b;
}
int main()
{
vector<int> v{3, 2, 1, 4, 5};
// 排序
sort(v.begin(), v.end());
// 使用迭代器遍历元素
for (auto it = v.begin(); it != v.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
// 查找
if (binary_search(v.begin(), v.end(), 2))
cout << "found" << endl;
// 求和
int sum = accumulate(v.begin(), v.end(), 0);
cout << "sum: " << sum << endl;
// 反转
reverse(v.begin(), v.end());
// 自定义比较函数排序
sort(v.begin(), v.end(), cmp);
// 使用迭代器遍历元素
for (auto it = v.begin(); it != v.end(); ++it)
{
cout << *it << " ";
}
cout << endl;
return 0;
}
小结
本文介绍了C++ STL中常用的数据结构与算法，包括顺序容器、关联容器、迭代器和算法。通过阅读本文，读者可以更好地使用STL提供的现成工具，快速实现各种算法。
参考资料