C++ STL(Standard Template Library)是C++标准库中的一个重要组成部分,提供了丰富的通用数据结构和算法。STL旨在提供高效、可复用和可移植的编程工具,帮助开发人员更轻松地实现各种应用。

STL包含以下几种主要组件:

  1. 容器(Containers):STL提供了多种容器类型,如向量(vector)、链表(list)、栈(stack)、队列(queue)、集合(set)和映射(map)等。这些容器提供不同的数据存储方式和操作方法,使其适用于各种场景。本篇主要介绍的就是STL中的容器。

  2. 算法(Algorithms):STL包含了大量的算法实现,如排序、查找、合并、变换等。这些算法可以直接应用于各种容器,提供了一致且高效的处理数据的方式。

  3. 迭代器(Iterators):迭代器是STL的基本概念,用于遍历和访问容器中的元素。STL提供了多种迭代器类型,如输入迭代器、输出迭代器、前向迭代器、双向迭代器和随机访问迭代器,每种迭代器都有自己的特性和限制。

  4. 函数对象(Function Objects):函数对象是一种行为类似函数的对象,可以被算法使用。STL中提供了一些常用的函数对象,如比较器、谓词和哈希函数等。

  5. 适配器(Adapters):STL还提供了一些容器适配器,如栈适配器(stack)和队列适配器(queue),以提供特定功能的接口和行为。

STL的设计思想是基于泛型编程和模板元编程,使得它能够适应各种数据类型,并提供高度灵活性和可扩展性。通过使用STL,可以简化代码、提高开发效率,并减少错误的可能性。

C++ STL提供了多种容器类型,每种容器都有自己的特点和适用场景。本篇将对STL中的各类容器进行详细讲解:

1.向量(vector):

向量是一种动态数组,可以在尾部高效地插入和删除元素。它支持随机访问,在任意位置进行元素插入和删除可能会导致较高的时间复杂度。

vector是C++ STL中的一种容器,它是一个动态数组(Dynamic Array)类型。下面是对vector的详细解释:

特点:

动态大小:vector可以根据需要动态地调整自身的大小,可以在尾部高效地插入和删除元素。
连续存储:vector中的元素在内存中是连续存储的,这使得随机访问元素变得非常高效。
头文件:

#include <vector>

声明和初始化:

std::vector<Type> vec; // 声明一个空的vector,元素类型为Type
std::vector<Type> vec(size); // 声明一个包含size个默认初始化元素的vector
std::vector<Type> vec(size, value); // 声明一个包含size个value作为初始值的vector
std::vector<Type> vec(other_vec); // 声明一个与other_vec相同的vector

常用操作:
插入和删除元素:
push_back(value): 在vector的尾部插入一个元素。
pop_back(): 删除vector的尾部元素。
insert(iterator, value): 在指定位置前插入一个元素。
erase(iterator): 删除指定位置的元素。
erase(first, last): 删除区间[first, last)内的元素。
访问元素:
vec[index]:通过下标访问vector中的元素。
vec.at(index): 安全地通过下标访问vector中的元素,会进行边界检查。
vec.front(): 返回vector的第一个元素。
vec.back(): 返回vector的最后一个元素。
大小和容量:
vec.size(): 返回vector中元素的个数。
vec.empty(): 判断vector是否为空。
vec.resize(new_size): 修改vector的大小为new_size。
vec.reserve(new_capacity): 修改vector的容量为new_capacity。
清空和重置:
vec.clear(): 清空vector中的所有元素。
vec.swap(other_vec): 交换两个vector的内容。
迭代器: vector提供了迭代器以便对元素进行遍历。常用的迭代器有:
vec.begin(): 返回指向vector第一个元素的迭代器。
vec.end(): 返回指向vector末尾(最后一个元素的下一个)的迭代器。
示例代码:

#include <iostream>
#include <vector>

int main() {
std::vector<int> vec;

// 插入元素
vec.push_back(10);
vec.push_back(20);
vec.push_back(30);

// 访问元素
std::cout << "First element: " << vec[0] << std::endl;
std::cout << "Last element: " << vec.back() << std::endl;

// 遍历元素
for (auto it = vec.begin(); it != vec.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;

// 修改元素
vec[1] = 50;

// 删除元素
vec.pop_back();

// 输出元素个数
std::cout << "Size: " << vec.size() << std::endl;

return 0;
}

vector是一个强大且常用的容器,它提供了高效的动态数组操作和灵活的内存管理。通过使用vector,我们可以方便地操作和管理一组数据。

2.链表(list):

链表是一个双向链表结构,可以在任意位置高效地插入和删除元素。然而,链表不支持随机访问,只能通过遍历来访问元素。

特点:

双向链接:list中的元素以双向链接的方式存储,每个元素都包含指向前一个和后一个元素的指针。
动态大小:list可以根据需要动态地调整自身的大小,可以在任意位置高效地插入和删除元素。
头文件:

#include <list>

声明和初始化:

std::list<Type> lst; // 声明一个空的list,元素类型为Type
std::list<Type> lst(size); // 声明一个包含size个默认初始化元素的list
std::list<Type> lst(size, value); // 声明一个包含size个value作为初始值的list
std::list<Type> lst(other_lst); // 声明一个与other_lst相同的list

常用操作:

插入和删除元素:
push_back(value): 在list的尾部插入一个元素。
push_front(value): 在list的头部插入一个元素。
pop_back(): 删除list的尾部元素。
pop_front(): 删除list的头部元素。
insert(iterator, value): 在指定位置前插入一个元素。
erase(iterator): 删除指定位置的元素。
erase(first, last): 删除区间[first, last)内的元素。
访问元素:
由于list是一个链表结构,不能通过下标直接访问元素。可以使用迭代器进行遍历和访问。
大小和容量:
lst.size(): 返回list中元素的个数。
lst.empty(): 判断list是否为空。
清空和重置:
lst.clear(): 清空list中的所有元素。
lst.swap(other_lst): 交换两个list的内容。
迭代器: list提供了迭代器以便对元素进行遍历。常用的迭代器有:

lst.begin(): 返回指向list第一个元素的迭代器。
lst.end(): 返回指向list末尾(最后一个元素的下一个)的迭代器。
示例代码:

#include <iostream>
#include <list>

int main() {
std::list<int> lst;

// 插入元素
lst.push_back(10);
lst.push_front(20);
lst.push_back(30);

// 遍历元素
for (auto it = lst.begin(); it != lst.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;

// 修改元素
auto it = lst.begin();
++it;
*it = 50;

// 删除元素
lst.pop_front();

// 输出元素个数
std::cout << "Size: " << lst.size() << std::endl;

return 0;
}

list是一个灵活且常用的容器,它适合在任意位置高效地插入和删除元素。由于其双向链表的特性,list可以提供较快的插入和删除操作,并且不需要进行内存的动态分配和复制。通过使用list,您可以方便地操作和管理一组数据,尤其是在插入和删除操作频繁的情况下。

3.双端队列(deque):

双端队列是一种两端都可以高效插入和删除元素的数据结构。它既支持随机访问,也支持在头部和尾部插入和删除操作。它的名称deque是"double-ended queue"的缩写。

双端队列可以在队列的前端和后端同时进行插入和删除操作,因此它既可以作为栈使用,也可以作为队列使用。这使得双端队列非常灵活,并且适用于各种场景。

在实现上,双端队列通常使用动态数组或链表来存储元素。无论是使用数组还是链表,双端队列都可以高效地进行插入和删除操作。

以下是双端队列的基本操作:

  1. push_front(item): 在队列的前端插入一个元素。
  2. push_back(item): 在队列的后端插入一个元素。
  3. pop_front(): 删除并返回队列的第一个元素。
  4. pop_back(): 删除并返回队列的最后一个元素。
  5. front(): 返回队列的第一个元素,但不删除它。
  6. back(): 返回队列的最后一个元素,但不删除它。
  7. size(): 返回队列中元素的个数。
  8. empty(): 检查队列是否为空。

通过双端队列的特性,我们可以灵活地在两端进行插入和删除操作,使其更加适应实际问题的需求。在算法和数据结构中,双端队列是一个非常有用的工具,可以提高程序的效率和可读性。

4.栈(stack):

栈(Stack)是一种基于后进先出(LIFO,Last-In-First-Out)原则的线性数据结构。它可以看作是一种受限制的线性表,只允许在表的一端进行插入和删除操作,该端被称为栈顶(top)。

栈的特点使得它非常适合用于临时存储需要反序处理的数据,比如函数调用、表达式求值、括号匹配等场景。

栈的基本操作包括:

  1. Push:将元素压入栈顶,即将元素插入到栈中。
  2. Pop:从栈顶弹出一个元素,并返回弹出的元素。
  3. Top(或Peek):获取栈顶的元素,但不对栈进行修改。
  4. Size:返回栈中元素的个数。
  5. Empty:检查栈是否为空。

由于栈的特性,只有栈顶元素是可见的,因此在插入和删除元素时不需要移动其他元素,使得操作效率非常高。

栈可以使用数组或链表实现。使用数组实现的栈被称为顺序栈,使用链表实现的栈被称为链式栈。

栈具有一些重要的应用,例如:

  1. 函数调用:函数调用时,需要保存局部变量、返回地址等信息,这些信息通常使用栈来保存。
  2. 表达式求值:中缀表达式转换为后缀表达式,并使用栈进行运算。
  3. 括号匹配:使用栈来检查括号是否匹配。
  4. 浏览器历史记录:浏览器使用栈来实现前进和后退功能。

总而言之,栈是一种非常有用的数据结构,在许多算法和应用中发挥着重要作用。

5.队列(queue):

队列(Queue)是一种基于先进先出(FIFO,First-In-First-Out)原则的线性数据结构。它和栈一样也可以看作是一种受限制的线性表,只允许在表的一端(称为队尾back/rear)插入元素,而在另一端(称为队头front)删除元素。

队列的特点使得它非常适合用于按照顺序处理数据的场景,例如任务调度、消息传递等。

队列的基本操作包括:

  1. Enqueue(或Push):将元素插入到队尾。
  2. Dequeue(或Pop):从队头删除一个元素,并返回被删除的元素。
  3. Front:获取队头的元素,但不对队列进行修改。
  4. Rear(或Back):获取队尾的元素,但不对队列进行修改。
  5. Size:返回队列中元素的个数。
  6. Empty:检查队列是否为空。

由于队列的特性,新元素总是被插入到队尾,而删除元素总是发生在队头,保持了元素的顺序不变。

队列可以使用数组或链表实现。使用数组实现的队列被称为顺序队列,使用链表实现的队列被称为链式队列。

队列具有一些重要的应用,例如:

  1. 算法设计:广度优先搜索(BFS)和树的层次遍历等算法中常用到队列。
  2. 缓存管理:缓存中的数据通常使用队列来管理,保持最新的数据在队尾,而最旧的数据在队头。
  3. 系统调度:任务调度器可以使用队列来管理待执行的任务。

总之,队列是一种常见且重要的数据结构,在许多算法中发挥着关键作用。

6.优先队列(priority_queue):

优先队列是一种按照特定排序规则进行插入和删除操作的数据结构。它内部使用堆实现,可以高效地获取最大或最小值。它的元素按照一定的优先级进行排序。

默认情况下,优先队列中的元素按照从大到小的顺序进行排列,也可以通过自定义比较器来改变排序顺序。 优先队列的常见操作包括:

1. Push:将元素插入到优先队列中。

2. Pop:删除优先队列中的顶部元素。

3. Top:获取优先队列的顶部元素,但不对队列进行修改。

4. Size:返回优先队列中元素的个数。

5. Empty:检查优先队列是否为空。

优先队列的实现通常使用堆(Heap)数据结构。堆是一种完全二叉树,其中每个节点的值都大于或等于其子节点的值(最大堆),或者每个节点的值都小于或等于其子节点的值(最小堆)。

C++的标准库提供了一个名为priority_queue的优先队列容器,位于头文件中。默认情况下,priority_queue使用std::less作为比较器,即按照从大到小的顺序进行排序。也可以使用自定义的比较器来指定元素的排序方式。

以下是使用优先队列的示例代码:

#include <iostream>
#include <queue>

int main() {
// 创建一个最大堆的优先队列
std::priority_queue<int> pq;

// 插入元素
pq.push(30);
pq.push(10);
pq.push(50);

// 访问顶部元素
std::cout << "Top element: " << pq.top() << std::endl;

// 删除顶部元素
pq.pop();

// 遍历并输出队列中的元素
while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
std::cout << std::endl;

return 0;
}

以上代码创建了一个最大堆的优先队列,并演示了插入、访问和删除操作。输出结果为50、30、10,按照从大到小的顺序排列。

总之,C++中的优先队列是一种非常有用的数据结构,可以方便地实现按照优先级排序的功能。

7.集合(set):

集合是一种无序、不可重复的容器,其中的元素按照特定的排序规则进行存储。由于采用红黑树等底层数据结构实现,查找和插入操作都具有较高的效率,std::set是一种基于红黑树(Red-Black Tree)实现的有序容器。它存储唯一的元素,并按照元素的值进行自动排序。

std::set的特点如下:

  1. 唯一性:std::set中不允许重复的元素。每个元素都是唯一的,当插入重复元素时会被忽略。
  2. 自动排序:std::set会根据元素的值进行自动排序,默认使用std::less作为比较函数。可以通过自定义比较函数来改变排序规则。
  3. 动态插入和删除:可以通过insert()函数向std::set中插入元素,通过erase()函数删除元素。
  4. 快速查找:std::set提供了高效的查找操作。find()函数用于判断元素是否存在,lower_bound()和upper_bound()函数用于查找范围。

std::set常用的操作包括:

  1. insert(val):向std::set中插入元素val。
  2. erase(val):从std::set中删除指定元素val。
  3. find(val):查找std::set中是否存在指定元素val,返回指向该元素的迭代器,如果不存在则返回end()迭代器。
  4. lower_bound(val):返回一个迭代器,指向第一个不小于val的元素。
  5. upper_bound(val):返回一个迭代器,指向第一个大于val的元素。
  6. size():返回std::set中元素的数量。
  7. empty():检查std::set是否为空。

以下是使用std::set的示例代码:

#include <iostream>
#include <set>

int main() {
std::set<int> mySet;

// 插入元素
mySet.insert(30);
mySet.insert(10);
mySet.insert(50);

// 遍历并输出std::set中的元素
for (const auto& element : mySet) {
std::cout << element << " ";
}
std::cout << std::endl;

// 查找元素
auto it = mySet.find(20);
if (it != mySet.end()) {
std::cout << "Element found in set" << std::endl;
} else {
std::cout << "Element not found in set" << std::endl;
}

// 删除元素
mySet.erase(10);

// 输出std::set的大小
std::cout << "Size of set: " << mySet.size() << std::endl;

return 0;
}

以上代码演示了插入、查找和删除操作,并输出std::set的元素及大小。

std::set是C++中常用的有序容器,它提供了自动排序和唯一性的特性,适用于需要按值排序并且不允许重复元素的场景。

8.映射(map):

映射是一种键值对存储的容器,其中的元素按照键的排序进行存储。类似于集合,映射也采用红黑树等底层数据结构实现,具有高效的查找和插入操作。

C++中的std::map是一个关联容器,它将键值对存储为有序的集合。每个键值对被称为一个元素,其中键是唯一的,用于索引值。std::map也是使用红黑树数据结构来实现,这种底层数据结构保证了快速的插入、删除和查找操作。

主要特点:

  1. 有序性:std::map按照键的顺序进行排序,默认使用std::less作为比较函数,也可以自定义比较函数。
  2. 唯一性:每个键都是唯一的,相同键的插入操作会被忽略。
  3. 动态插入和删除:可以使用insert()函数向std::map中插入元素,并使用erase()函数删除指定的元素。
  4. 查找操作:通过find()函数可以在std::map中查找指定的键,返回一个指向该键值对的迭代器。
  5. 迭代器与范围遍历:可以使用迭代器来遍历std::map中的键值对,也可以使用范围遍历(range-based for loop)来遍历整个std::map
  6. 元素访问:通过[]运算符可以直接访问指定键对应的值。
  7. 大小和空判断:使用size()函数可以获取std::map中键值对的数量,使用empty()函数可以检查std::map是否为空。

常用操作:

  1. 插入元素:使用insert()函数插入键值对到std::map中。
  2. 删除元素:使用erase()函数删除指定键的键值对。
  3. 查找元素:使用find()函数查找指定键的迭代器,若存在则返回指向该键值对的迭代器,否则返回指向结尾的迭代器。
  4. 访问元素:通过[]运算符访问指定键对应的值。
  5. 迭代器遍历:使用迭代器进行遍历,并通过firstsecond成员来访问键和值。
  6. 范围遍历:使用范围遍历(range-based for loop)遍历整个std::map中的键值对。
  7. 自定义比较器:除了默认的排序方式外,您可以通过传递自定义的比较函数给std::map来定义自己的排序规则。比较函数应该是一个可调用对象,接受两个参数,并返回一个布尔值来表示比较结果。例如,如果您想按照键的降序进行排序,可以使用std::greater作为比较函数。
std::map<int, std::string, std::greater<int>> myMap;
  1. 键值对的操作:通过[]运算符可以直接访问指定键对应的值。如果键不存在,则会插入一个新的键值对,值为默认构造的值类型。需要注意的是,在使用[]运算符访问不存在的键时,会插入一个新的键值对到std::map中。因此,在访问前最好先判断键是否存在,以避免不必要的插入操作。
myMap[1] = "apple"; // 插入键值对 {1, "apple"}
std::cout << myMap[1] << std::endl; // 输出 "apple"
  1. 迭代器遍历:可以使用迭代器来遍历std::map中的键值对。迭代器类似于指针,它指向容器中的某个元素,可以通过解引用操作符*来获取元素本身,或者使用成员访问操作符.来访问键和值。
std::map<int, std::string> myMap;
// 插入元素...

// 使用迭代器遍历并输出std::map中的键值对
for (auto it = myMap.begin(); it != myMap.end(); ++it) {
std::cout << "Key: " << it->first << ", Value: " << it->second << std::endl;
}
  1. 范围遍历:C++11引入了范围遍历(range-based for loop),可以更简洁地遍历整个std::map中的键值对。范围遍历会自动推导出迭代器类型,并以只读方式进行遍历。
std::map<int, std::string> myMap;
// 插入元素...

// 使用范围遍历遍历并输出std::map中的键值对
for (const auto& pair : myMap) {
std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
}
  1. 时间复杂度:std::map上的插入、删除和查找操作的时间复杂度为对数级别O(logN)。由于底层使用红黑树作为数据结构,它能够保持平衡并保证这些操作的高效执行。

示例代码:

#include <iostream>
#include <map>

int main() {
std::map<int, std::string> myMap;

// 插入元素
myMap.insert(std::make_pair(1, "apple"));
myMap.insert(std::make_pair(2, "banana"));
myMap[3] = "cherry";

// 遍历并输出std::map中的键值对
for (const auto& pair : myMap) {
std::cout << "Key: " << pair.first << ", Value: " << pair.second << std::endl;
}

// 查找元素
auto it = myMap.find(2);
if (it != myMap.end()) {
std::cout << "Element found in map: " << it->second << std::endl;
} else {
std::cout << "Element not found in map" << std::endl;
}

// 删除元素
myMap.erase(1);

// 输出std::map的大小
std::cout << "Size of map: " << myMap.size() << std::endl;

return 0;
}

以上代码演示了插入、查找和删除操作,并输出std::map中的键值对及大小。