企业网站的域名是该企业的什么,济南川芎网站建设,长沙营销型网站开发,网站推广品牌文章目录 标准模板库 STL容器算法迭代器仿函数/函数对象适配器分配器示例 标准模板库 STL
C 的标准模板库#xff08;Standard Template Library#xff0c;STL#xff09;旨在通过模板化的设计#xff0c;提供一种通用的编程模式#xff0c;使程序员能方便地实现和扩展各… 文章目录 标准模板库 STL容器算法迭代器仿函数/函数对象适配器分配器示例 标准模板库 STL
C 的标准模板库Standard Template LibrarySTL旨在通过模板化的设计提供一种通用的编程模式使程序员能方便地实现和扩展各种数据结构和算法提高程序的开发效率和执行效率。STL 的设计遵循泛型编程的原则其组件可以处理各种类型的数据。
STL 中的组件包括容器containers、迭代器iterators、算法algorithms、仿函数/函数对象function objects、适配器adaptors 和分配器allocators。他们的关系如图所示 容器负责存储数据算法用于执行数据处理操作迭代器为算法提供数据访问机制仿函数用于定义算法的行为策略适配器用于修改和扩展接口而分配器用于管理内存资源
容器
容器是一组模板类内部封装了数据的存储和访问机制对外部提供了统一的接口。在STL中容器被分为两大类序列式容器Sequence Containers和关联式容器Associative Containers。
序列式容器用于存储具有严格线性关系的元素序列。它们以线性方式存储元素可以动态地添加、删除和访问元素。序列式容器主要有以下几种
std::vector动态数组可以存储相同类型的元素。支持随机访问元素但在数组中间插入或删除元素可能会导致大量的元素移动。std::deque双端队列具有在两端添加和删除元素的高效性。与std::vector类似但支持更高效的头部插入和删除。std::list双向链表元素在内存中不是连续存储的。在链表的任何位置添加或删除元素都非常高效但随机访问元素效率较低。std::forward_listC11起单向链表与std::list类似但只支持向前迭代。std::arrayC11起固定大小的数组不支持动态大小调整。提供与原生数组类似的性能但具有STL容器的接口。std::string虽然std::string主要用于处理字符串但它在内部实际上是一个特化的std::basic_string模板因此也可以被视为一种序列式容器。
关联式容器存储的元素具有键值对key-value pair的关联关系。关联式容器内部通常使用红黑树对于有序的容器或哈希表对于无序的容器来实现以支持高效的查找、插入和删除操作。关联式容器主要有以下几种
std::set集合包含唯一的元素元素在容器中按升序排列。std::multiset多重集合允许存储重复的元素元素在容器中按升序排列。std::map映射存储键值对其中键key是唯一的并且按键的升序存储。std::multimap多重映射允许存储具有相同键的多个键值对并且按键的升序存储。std::unordered_setC11起无序集合与std::set类似但元素的顺序不保证。它使用哈希表来实现因此插入、删除和查找操作的平均时间复杂度都是O(1)。std::unordered_multisetC11起无序多重集合与std::multiset类似但元素的顺序不保证。std::unordered_mapC11起无序映射与std::map类似但元素的顺序不保证。它使用哈希表来实现因此操作效率更高。std::unordered_multimapC11起无序多重映射与std::multimap类似但元素的顺序不保证。
算法
算法是处理数据的函数或函数模板它们不存储数据而是对数据进行操作。算法通过迭代器从容器中获取数据并执行相应的操作。STL算法的头文件主要包括algorithm、numeric和functional。以下是一些常用的STL算法
遍历算法
for_each对容器中的每个元素执行指定的操作。
查找算法
find在容器中查找等于指定值的元素。find_if在容器中查找满足特定条件的第一个元素。adjacent_find查找相邻的重复元素或满足特定条件的相邻元素对。binary_search在已排序的范围内查找指定元素。count计算容器中等于指定值的元素个数。count_if计算容器中满足特定条件的元素个数。
排序算法
sort对容器中的元素进行排序。random_shuffle随机打乱容器中的元素顺序注意C17开始已被弃用推荐使用其他方式实现随机排序。merge合并两个已排序的范围。reverse反转容器中的元素顺序。
拷贝和替换算法
copy从一个位置拷贝元素到另一个位置。replace替换容器中等于指定值的元素。replace_if替换容器中满足特定条件的元素。swap交换两个元素的值。
算术生成算法
accumulate计算容器中元素的累积和或其他二元操作的累积结果。fill用指定值填充容器中的元素。
集合算法
set_intersection计算两个已排序集合的交集。set_union计算两个已排序集合的并集。set_difference计算两个已排序集合的差集第一个集合中存在但第二个集合中不存在的元素。
迭代器
迭代器是访问容器中元素的指针或类似指针的对象。 迭代器允许算法间接访问和操作容器中的元素。 容器可以通过返回迭代器的方式向算法暴露其内部元素。
仿函数/函数对象
仿函数/函数对象是一个行为类似于函数的对象可以被调用并且可以在泛型编程中用作函数参数用于定义算法的行为策略 (允许我们为算法提供自定义的比较、判断或操作规则)。 在C中仿函数可以通过函数指针、函数对象重载了函数调用运算符operator()的对象、以及C11引入的lambda表达式来定义。
适配器
适配器用于修改或扩展已有组件的接口使它们能够更好地适应不同的使用场景。 STL中主要包括容器适配器,迭代器适配器和仿函数适配器。
容器适配器 提供了一种机制用于修改或扩展容器的行为。STL提供了三种容器适配器stack栈、queue队列和priority_queue优先队列其中stack和queue分别提供了栈和队列的数据结构而priority_queue则允许元素根据优先级进行排序。
迭代器适配器Iterator Adapters 提供了一种机制可以将非迭代器对象转换为迭代器对象或者改变迭代器的行为。STL中的迭代器适配器包括back_insert_iterator、front_insert_iterator和insert_iterator等。这些适配器分别提供了在容器的末尾、开头或任意位置插入元素的功能。
函数对象适配器 STL中的函数函数适配器包括bind、mem_fun和mem_fun_ref等。这些适配器可以将成员函数、函数指针或其他可调用对象转换为函数对象以便与STL算法一起使用。
分配器
分配器在容器的创建和销毁过程中起着关键作用它们负责为容器分配和回收内存资源。 STL容器默认使用标准分配器std::allocator但也可以自定义分配器来满足特定的内存管理需求。
示例
下面是一个STL的使用示例它使用了std::vector容器、迭代器、std::find_if算法、lambda函数函数对象、默认的std::allocator隐式使用以及std::stack容器适配器
#include iostream
#include vector
#include algorithm
#include stackint main() {// 容器: 使用vector容器存储整数std::vectorint numbers {1, 5, 8, 3, 9, 2};// 迭代器: 使用迭代器指针遍历vector // 1. 获取vector的begin()和end()迭代器 // 2. 使用迭代器 it 遍历容器中的元素直到达到end()迭代器 for (std::vectorint::iterator it numbers .begin(); it ! numbers .end(); it) { std::cout *it ; } std::cout std::endl;// 函数对象: 使用lambda表达式检查一个整数是否大于5auto is_greater_than_five [](int num) { return num 5; };// 算法: 使用find_if查找第一个大于5的数, it也为迭代器指向结果的指针auto it std::find_if(numbers.begin(), numbers.end(), is_greater_than_five);if (it ! numbers.end()) {std::cout Found a number greater than 5: *it std::endl;} else {std::cout No number greater than 5 found. std::endl;}// 容器适配器: 使用stack适配器基于vectorstd::stackint, std::vectorint numStack;// 将vector中的元素压入stack中这里为了演示只压入找到的那个大于5的数if (it ! numbers.end()) {numStack.push(*it);}// 弹出stack中的元素并打印while (!numStack.empty()) {std::cout Popped from stack: numStack.top() std::endl;numStack.pop();}// 分配器: vector默认使用std::allocator而stack适配器也使用其底层容器的分配器return 0;
}1 5 8 3 9 2
Found a number greater than 5: 8
Popped from stack: 8
