前言:
眼前看官们对“多重集合的排列数”大约比较关注,朋友们都需要知道一些“多重集合的排列数”的相关知识。那么小编同时在网络上网罗了一些关于“多重集合的排列数””的相关文章,希望咱们能喜欢,小伙伴们一起来了解一下吧!标准模板库 STL
C++ 的标准模板库(Standard Template Library,STL)旨在通过模板化的设计,提供一种通用的编程模式,使程序员能方便地实现和扩展各种数据结构和算法,提高程序的开发效率和执行效率。STL 的设计遵循泛型编程的原则,其组件可以处理各种类型的数据。
STL 中的组件包括容器(containers)、迭代器(iterators)、算法(algorithms)、仿函数/函数对象(function objects)、适配器(adaptors) 和分配器(allocators)。他们的关系如图所示:
容器负责存储数据,算法用于执行数据处理操作,迭代器为算法提供数据访问机制,仿函数用于定义算法的行为策略,适配器用于修改和扩展接口,而分配器用于管理内存资源,
容器
容器是一组模板类,内部封装了数据的存储和访问机制,对外部提供了统一的接口。在STL中,容器被分为两大类:序列式容器(Sequence Containers)和关联式容器(Associative Containers)。
序列式容器用于存储具有严格线性关系的元素序列。它们以线性方式存储元素,可以动态地添加、删除和访问元素。序列式容器主要有以下几种:
std::vector:动态数组,可以存储相同类型的元素。支持随机访问元素,但在数组中间插入或删除元素可能会导致大量的元素移动。std::deque:双端队列,具有在两端添加和删除元素的高效性。与std::vector类似,但支持更高效的头部插入和删除。std::list:双向链表,元素在内存中不是连续存储的。在链表的任何位置添加或删除元素都非常高效,但随机访问元素效率较低。std::forward_list(C++11起):单向链表,与std::list类似,但只支持向前迭代。std::array(C++11起):固定大小的数组,不支持动态大小调整。提供与原生数组类似的性能,但具有STL容器的接口。std::string:虽然std::string主要用于处理字符串,但它在内部实际上是一个特化的std::basic_string模板,因此也可以被视为一种序列式容器。
关联式容器存储的元素具有键值对(key-value pair)的关联关系。关联式容器内部通常使用红黑树(对于有序的容器)或哈希表(对于无序的容器)来实现,以支持高效的查找、插入和删除操作。关联式容器主要有以下几种:
std::set:集合,包含唯一的元素,元素在容器中按升序排列。std::multiset:多重集合,允许存储重复的元素,元素在容器中按升序排列。std::map:映射,存储键值对,其中键(key)是唯一的,并且按键的升序存储。std::multimap:多重映射,允许存储具有相同键的多个键值对,并且按键的升序存储。std::unordered_set(C++11起):无序集合,与std::set类似,但元素的顺序不保证。它使用哈希表来实现,因此插入、删除和查找操作的平均时间复杂度都是O(1)。std::unordered_multiset(C++11起):无序多重集合,与std::multiset类似,但元素的顺序不保证。std::unordered_map(C++11起):无序映射,与std::map类似,但元素的顺序不保证。它使用哈希表来实现,因此操作效率更高。std::unordered_multimap(C++11起):无序多重映射,与std::multimap类似,但元素的顺序不保证。算法
算法是处理数据的函数或函数模板,它们不存储数据,而是对数据进行操作。算法通过迭代器从容器中获取数据,并执行相应的操作。STL算法的头文件主要包括<algorithm>、<numeric>和<functional>。以下是一些常用的STL算法:
遍历算法:
for_each:对容器中的每个元素执行指定的操作。
查找算法:
find:在容器中查找等于指定值的元素。find_if:在容器中查找满足特定条件的第一个元素。adjacent_find:查找相邻的重复元素或满足特定条件的相邻元素对。binary_search:在已排序的范围内查找指定元素。count:计算容器中等于指定值的元素个数。count_if:计算容器中满足特定条件的元素个数。
排序算法:
sort:对容器中的元素进行排序。random_shuffle:随机打乱容器中的元素顺序(注意:C++17开始已被弃用,推荐使用其他方式实现随机排序)。merge:合并两个已排序的范围。reverse:反转容器中的元素顺序。
拷贝和替换算法:
copy:从一个位置拷贝元素到另一个位置。replace:替换容器中等于指定值的元素。replace_if:替换容器中满足特定条件的元素。swap:交换两个元素的值。
算术生成算法:
accumulate:计算容器中元素的累积和(或其他二元操作的累积结果)。fill:用指定值填充容器中的元素。
集合算法:
set_intersection:计算两个已排序集合的交集。set_union:计算两个已排序集合的并集。set_difference:计算两个已排序集合的差集(第一个集合中存在但第二个集合中不存在的元素)。迭代器
迭代器是访问容器中元素的指针或类似指针的对象。 迭代器允许算法间接访问和操作容器中的元素。 容器可以通过返回迭代器的方式向算法暴露其内部元素。
仿函数/函数对象
仿函数/函数对象是一个行为类似于函数的对象,可以被调用,并且可以在泛型编程中用作函数参数,用于定义算法的行为策略 (允许我们为算法提供自定义的比较、判断或操作规则)。 在C++中,仿函数可以通过函数指针、函数对象(重载了函数调用运算符operator()的对象)、以及C++11引入的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 <stack>int main() { // 容器: 使用vector容器存储整数 std::vector<int> numbers = {1, 5, 8, 3, 9, 2}; // 迭代器: 使用迭代器(指针)遍历vector // 1. 获取vector的begin()和end()迭代器 // 2. 使用迭代器 it 遍历容器中的元素,直到达到end()迭代器 for (std::vector<int>::iterator it = numbers .begin(); it != numbers .end(); ++it) { std::cout << *it << " "; } std::cout << std::endl; // 函数对象: 使用lambda表达式检查一个整数是否大于5 auto 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适配器(基于vector) std::stack<int, std::vector<int>> 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: 8Popped from stack: 8
标签: #多重集合的排列数