学建网站 必须学那些知识,网络网页制作,清除wordpress数据库中多余的,网站开发交流STL标准库与泛型编程#xff08;侯捷#xff09;
本文是学习笔记#xff0c;仅供个人学习使用。如有侵权#xff0c;请联系删除。
参考链接
Youbute: 侯捷-STL标准库与泛型编程
B站: 侯捷 - STL
Github:STL源码剖析中源码 https://github.com/SilverMaple/STLSourceCo…STL标准库与泛型编程侯捷
本文是学习笔记仅供个人学习使用。如有侵权请联系删除。
参考链接
Youbute: 侯捷-STL标准库与泛型编程
B站: 侯捷 - STL
Github:STL源码剖析中源码 https://github.com/SilverMaple/STLSourceCodeNote/tree/master
Github:课程ppt和源码 https://github.com/ZachL1/Bilibili-plus
下面是C标准库体系结构与内核分析的第三讲 文章目录 STL标准库与泛型编程侯捷27 算法的形式28 迭代器的分类category29 迭代器分类category对算法的影响30 算法源代码剖析11个例子31 仿函数和函数对象32 存在多种Adapter33 函数适配器Binder2nd34 函数适配器not135 新型适配器bind36 迭代器适配器reverse iterator37 迭代器适配器inserter38 ostream iterator39 istream iterator后记 27 算法的形式
算法algorithm是function template而其他的containerinteratorfunctoradapterallocator都是class template。
算法看不到container只看得到iterator由container提供 28 迭代器的分类category
iterator_category 是 C 中迭代器的一种属性用于表示迭代器的类型或范畴。它属于 C 的迭代器概念中的一部分主要包括以下几个范畴 Input Iterator输入迭代器 std::input_iterator_tag Output Iterator输出迭代器 std::output_iterator_tag Forward Iterator前向迭代器 std::forward_iterator_tag Bidirectional Iterator双向迭代器 std::bidirectional_iterator_tag Random Access Iterator随机访问迭代器 std::random_access_iterator_tag
这些标签用于描述迭代器的能力和行为从而影响了对迭代器的操作。例如对于 std::advance 函数它会根据迭代器的类型选择不同的实现以保证效率。
具体的使用示例如下
#include iostream
#include iterator
#include vectorint main() {std::vectorint vec {1, 2, 3, 4, 5};// 获取迭代器类型using IteratorType std::vectorint::iterator;IteratorType it vec.begin();// 使用 iterator_category 获取迭代器类型std::cout Iterator category: ;if (std::is_samestd::iterator_traitsIteratorType::iterator_category,std::random_access_iterator_tag::value) {std::cout Random Access Iterator std::endl;} else if (std::is_samestd::iterator_traitsIteratorType::iterator_category,std::bidirectional_iterator_tag::value) {std::cout Bidirectional Iterator std::endl;} else if (std::is_samestd::iterator_traitsIteratorType::iterator_category,std::forward_iterator_tag::value) {std::cout Forward Iterator std::endl;} else if (std::is_samestd::iterator_traitsIteratorType::iterator_category,std::input_iterator_tag::value) {std::cout Input Iterator std::endl;} else if (std::is_samestd::iterator_traitsIteratorType::iterator_category,std::output_iterator_tag::value) {std::cout Output Iterator std::endl;}return 0;
}在这个示例中我们使用 std::iterator_traits 获取迭代器的属性然后根据 iterator_category 输出不同类型的迭代器。在实际应用中这些信息通常用于实现泛型算法以适应不同类型的迭代器。
对于下图中的各种容器简单介绍一下它们迭代器是什么种类
arrayvectordeque它们是连续的它们的迭代器是Random Access Iteratorlist的迭代器是Bidirectional Iterator forward_list的迭代器是Forward Iterator。
基于红黑树的set/multiset, map/multimap它们都是Bidirectional Iterator
基于hashtable的unordered_set, unordered_multiset, unordered_map, unordered_multimap的迭代器是双向的Bidirectional Iterator还是单向的Forward Iterator要看bucket对应的链表具体是双向链表还是单向链表。具体到STL应该是forward_iterator。
容器迭代器的分类是基于对象存在继承关系而不是基于enum枚举类型。 /// Marking input iterators.struct input_iterator_tag { };/// Marking output iterators.struct output_iterator_tag { };/// Forward iterators support a superset of input iterator operations.struct forward_iterator_tag : public input_iterator_tag { };/// Bidirectional iterators support a superset of forward iterator/// operations.struct bidirectional_iterator_tag : public forward_iterator_tag { };/// Random-access iterators support a superset of bidirectional/// iterator operations.struct random_access_iterator_tag : public bidirectional_iterator_tag { };下面是测试各种容器迭代器类型的代码
#include iostream // std::cout
#include iterator // std::iterator_traits
#include typeinfo // typeid
#includebits/stdc.h
using namespace std;
namespace jj33
{
void _display_category(random_access_iterator_tag)
{ cout random_access_iterator endl; }
void _display_category(bidirectional_iterator_tag)
{ cout bidirectional_iterator endl; }
void _display_category(forward_iterator_tag)
{ cout forward_iterator endl; }
void _display_category(output_iterator_tag)
{ cout output_iterator endl; }
void _display_category(input_iterator_tag)
{ cout input_iterator endl; }templatetypename I
void display_category(I itr)
{typename iterator_traitsI::iterator_category cagy;_display_category(cagy);cout typeid(itr).name() typeid(itr).name() endl endl; //The output depends on library implementation.//The particular representation pointed by the //returned valueis implementation-defined, //and may or may not be different for different types.
}void test_iterator_category()
{cout \ntest_iterator_category().......... \n;display_category(arrayint,10::iterator()); // random_access_iteratordisplay_category(vectorint::iterator()); // random_access_iteratordisplay_category(listint::iterator()); // bidirectional_iteratordisplay_category(forward_listint::iterator()); // forward_iteratordisplay_category(dequeint::iterator()); // random_access_iteratordisplay_category(setint::iterator()); // bidirectional_iteratordisplay_category(mapint,int::iterator()); // bidirectional_iteratordisplay_category(multisetint::iterator()); // bidirectional_iteratordisplay_category(multimapint,int::iterator()); // bidirectional_iteratordisplay_category(unordered_setint::iterator()); // forward_iteratordisplay_category(unordered_mapint,int::iterator()); // forward_iteratordisplay_category(unordered_multisetint::iterator()); // forward_iteratordisplay_category(unordered_multimapint,int::iterator()); // forward_iteratordisplay_category(istream_iteratorint()); // input_iteratordisplay_category(ostream_iteratorint(cout,)); // output_iterator
}
}int main(int argc, char** argv)
{jj33::test_iterator_category(); return 0;
}输出结果
test_iterator_category()..........
random_access_iterator
typeid(itr).name() Pirandom_access_iterator
typeid(itr).name() N9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEEbidirectional_iterator
typeid(itr).name() St14_List_iteratorIiEforward_iterator
typeid(itr).name() St18_Fwd_list_iteratorIiErandom_access_iterator
typeid(itr).name() St15_Deque_iteratorIiRiPiEbidirectional_iterator
typeid(itr).name() St23_Rb_tree_const_iteratorIiEbidirectional_iterator
typeid(itr).name() St17_Rb_tree_iteratorISt4pairIKiiEEbidirectional_iterator
typeid(itr).name() St23_Rb_tree_const_iteratorIiEbidirectional_iterator
typeid(itr).name() St17_Rb_tree_iteratorISt4pairIKiiEEforward_iterator
typeid(itr).name() NSt8__detail14_Node_iteratorIiLb1ELb0EEEforward_iterator
typeid(itr).name() NSt8__detail14_Node_iteratorISt4pairIKiiELb0ELb0EEEforward_iterator
typeid(itr).name() NSt8__detail14_Node_iteratorIiLb1ELb0EEEforward_iterator
typeid(itr).name() NSt8__detail14_Node_iteratorISt4pairIKiiELb0ELb0EEEinput_iterator
typeid(itr).name() St16istream_iteratorIicSt11char_traitsIcElEoutput_iterator
typeid(itr).name() St16ostream_iteratorIicSt11char_traitsIcEEistream_iterator的iterator_category ostream_iterator的iterator_category 29 迭代器分类category对算法的影响
iterator_category对算法的影响
下面代码展示了__distance的两种实现不同的实现会影响算法的效率。distance会根据iterator_category(__first)选择不同的 __distance实现。
typename 的使用是为了指定 iterator_traits_InputIterator::difference_type 表示一个类型。iterator_traits_InputIterator::difference_type 是迭代器 _InputIterator 的差值类型表示两个迭代器之间的距离而 typename 在这里是为了明确告诉编译器这是一个类型而不是其他类型的标识符。 template class _InputIterator, class _Distance
inline void distance(_InputIterator __first, _InputIterator __last, _Distance __n)
{__STL_REQUIRES(_InputIterator, _InputIterator);__distance(__first, __last, __n, iterator_category(__first));
}
// 两个__distance的版本
//1. 这里的__distance判断input_iterator_tag
// 用头迭代器__first一直往后移动直到__last统计移动的次数
template class _InputIterator
inline typename iterator_traits_InputIterator::difference_type
__distance(_InputIterator __first, _InputIterator __last, input_iterator_tag)
{typename iterator_traits_InputIterator::difference_type __n 0;while (__first ! __last) {__first; __n;}return __n;
}// 2. 下面的__distance判断random_access_iterator_tag空间是连续的两个迭代器相减
template class _RandomAccessIterator
inline typename iterator_traits_RandomAccessIterator::difference_type
__distance(_RandomAccessIterator __first, _RandomAccessIterator __last,random_access_iterator_tag) {__STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);return __last - __first;
}再举一个关于iterator_category对算法影响的例子
advance函数会根据iterator_category(__i)的类型选择调用不同的__advance的实现。
// 1.如果是input_iterator_tagadvance只能向前
template class _InputIter, class _Distance
inline void __advance(_InputIter __i, _Distance __n, input_iterator_tag) {while (__n--) __i;
}#if defined(__sgi) !defined(__GNUC__) (_MIPS_SIM ! _MIPS_SIM_ABI32)
#pragma set woff 1183
#endif// 2.如果是bidirectional_iterator_tagadvance方向可正可负实现如下
template class _BidirectionalIterator, class _Distance
inline void __advance(_BidirectionalIterator __i, _Distance __n, bidirectional_iterator_tag) {__STL_REQUIRES(_BidirectionalIterator, _BidirectionalIterator);if (__n 0)while (__n--) __i;elsewhile (__n) --__i;
}#if defined(__sgi) !defined(__GNUC__) (_MIPS_SIM ! _MIPS_SIM_ABI32)
#pragma reset woff 1183
#endif// 3.如果是random_access_iterator_tag类型直接i n进行advance
template class _RandomAccessIterator, class _Distance
inline void __advance(_RandomAccessIterator __i, _Distance __n, random_access_iterator_tag) {__STL_REQUIRES(_RandomAccessIterator, _RandomAccessIterator);__i __n;
}template class _InputIterator, class _Distance
inline void advance(_InputIterator __i, _Distance __n) {__STL_REQUIRES(_InputIterator, _InputIterator);__advance(__i, __n, iterator_category(__i));
}通过上面两个例子可以体会到 容器迭代器的分类是基于对象存在继承关系而不是基于enum枚举类型。 这样做的好处
iterator_category有5种这里只看上图中右上角的四种。
上图中右上角有3个继承关系子类is a 父类这样我们就不用非得实现4种类型的__advance或其他函数,这里实现了input_iterator_tagbidirectional_iterator_tagrandom_access_iterator_tag这三种而对于forward_iterator_tag由于是继承关系直接让它调用它的父类input_iterator_tag即可这样可以省去反复的实现过程。
iterator_category和type traits对算法的影响这里举copy的例子
下图左侧的copy函数有三个参数源端待复制的first和last表示待复制的起点和终点目的端复制过去的地方只需要一个起点然后把源端的数据一直复制到目的端。
但是copy具体实现的时候会根据迭代器不同的类型进行不同的检查从而选择不同的动作。处理方法中有的调用了c语言的memmove进行复制速度极快有的使用for循环逐个拷贝速度慢。
其中一个使用memmove的实现 如下
#define __SGI_STL_DECLARE_COPY_TRIVIAL(_Tp) inline _Tp* copy(const _Tp* __first, const _Tp* __last, _Tp* __result) { memmove(__result, __first, sizeof(_Tp) * (__last - __first)); return __result (__last - __first); }其中一个使用for循环拷贝的实现如下
template class _InputIter, class _Size, class _OutputIter
pair_InputIter, _OutputIter __copy_n(_InputIter __first, _Size __count,_OutputIter __result,input_iterator_tag) {for ( ; __count 0; --__count) {*__result *__first;__first;__result;}return pair_InputIter, _OutputIter(__first, __result);
}下图中右侧出现的 has trivial op() 和has non-trivial op() 是两种type traits关于type traits后面会讲。 C标准库中的 type traits 是一组模板元编程工具它们提供了一种在编译时进行类型信息查询和操作的方式。Type traits 主要通过模板来实现它们使得在编译期间能够进行更多的类型判断和转换从而提高代码的灵活性和性能。
Type traits 主要包括以下几个方面的功能 类型特征查询 Type traits 允许你在编译时查询某个类型的特征例如是否是指针类型、是否是引用类型、是否是数组类型等。这些信息可以通过类似 std::is_pointer、std::is_reference、std::is_array 等 type traits 来获取。 类型转换和操作 Type traits 提供了一些模板工具使得可以在编译时进行类型的转换和操作。例如可以使用 std::remove_pointer、std::remove_reference 来移除指针或引用。 条件判断 Type traits 还提供了条件判断可以根据某个类型是否满足某个条件来进行编译期间的分支选择。例如std::conditional 根据条件选择不同的类型。 类型比较 Type traits 允许你在编译时比较两个类型是否相同。例如std::is_same 可以用于检查两个类型是否相同。
这些功能使得 type traits 在泛型编程和模板元编程中非常有用能够在编译期间进行更多的类型相关的操作和判断避免运行时的开销。C标准库提供了一系列的 type traits这些 traits 都定义在头文件 type_traits 中。
补充上图中memmove函数的知识
memmove 是C语言标准库中的一个函数用于在内存中移动一块数据一段字节序列。memmove 的函数原型定义在头文件 cstring或 string.h中。
void* memmove(void* dest, const void* src, size_t n);dest要复制到的目标地址的指针。src要复制的源地址的指针。n要复制的字节数。
memmove 的功能类似于 memcpy都是用于内存的拷贝但有一个重要的区别。memmove 能够处理源地址和目标地址重叠的情况而 memcpy 不行。因此当源和目标地址可能存在重叠时通常推荐使用 memmove。
函数会将从源地址 src 复制的 n 个字节的数据移动到目标地址 dest即使源地址和目标地址重叠也能够保证正确的复制。这是通过在内部使用临时缓冲区来实现的。
示例用法
#include cstring
#include iostreamint main() {char source[] Hello, World!;char destination[20];// 将源数据复制到目标地址memmove(destination, source, strlen(source) 1);// 输出结果std::cout Source: source std::endl;std::cout Destination: destination std::endl;return 0;
}在上面的示例中memmove 被用来将字符串 “Hello, World!” 从 source 复制到 destination即使两者存在重叠。
iterator_category和type traits对算法的影响这里举destroy的例子
这里判断析构函数是重要的调用析构函数还是不重要的不调用析构函数这里也涉及到type traits destroy各种形况处理的源代码如下图蓝色的箭头表示调用关系。 iterator_category和type traits对算法的影响这里举__unique_copy的例子
template class _InputIter, class _OutputIter, class _Tp
_OutputIter __unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result, _Tp*) {_Tp __value *__first;*__result __value;while (__first ! __last)if (!(__value *__first)) {__value *__first;*__result __value;}return __result;
}template class _InputIter, class _OutputIter
inline _OutputIter __unique_copy(_InputIter __first, _InputIter __last,_OutputIter __result, output_iterator_tag) {return __unique_copy(__first, __last, __result, __VALUE_TYPE(__first));
}template class _InputIter, class _ForwardIter
_ForwardIter __unique_copy(_InputIter __first, _InputIter __last,_ForwardIter __result, forward_iterator_tag) {*__result *__first;while (__first ! __last)if (!(*__result *__first))*__result *__first;return __result;
}这需要处理output_iterator_tag和forward_iterator_tag不同的类型对于output_iterator它是write-only的不能像forward_iterator那样read所以不能有*result ! *first的动作所以设计了专门针对output_iterator的 __unique_copy版本。 算法是模板函数可以接收任意类型的参数
在定义模板参数名称的时候会命名暗示它想要接收的类型比如下图distance函数想要接收的是input iterator而sort想要接收的是random access iteratorrotate函数想要接收forward iterator等等。 30 算法源代码剖析11个例子
哪些是C标准库提供的algorithm呢需要符合如下接口
templatetypename Iterator
std::Algorithm(Iterator itr1, Iterator itr2, ...)
{...
}下图中的qsort和bsearch是C语言的函数而count_iffindsort等是C提供的函数。 accumulate算法有两个版本
可学习到一般函数都有两个版本第二个版本一般是允许增加一种原则或者操作从而应用的更广泛。
// 第一个版本
// 直接累加
template class _InputIterator, class _Tp
_Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init)
{__STL_REQUIRES(_InputIterator, _InputIterator);for ( ; __first ! __last; __first)__init __init *__first;return __init;
}
// 第二个版本
// 初值和元素做__binary_op这个动作
template class _InputIterator, class _Tp, class _BinaryOperation
_Tp accumulate(_InputIterator __first, _InputIterator __last, _Tp __init,_BinaryOperation __binary_op)
{__STL_REQUIRES(_InputIterator, _InputIterator);for ( ; __first ! __last; __first)__init __binary_op(__init, *__first);return __init;
}测试
仿函数Function Object也被称为函数对象是一种在C中模拟函数行为的对象。它是一个类对象实现了函数调用操作符 operator()使得对象可以像函数一样被调用。仿函数可以以类对象的形式包装函数行为允许在算法中像调用函数一样使用对象。
#include iostream // std::cout
#include functional // std::minus
#include numeric // std::accumulate
namespace jj34
{
int myfunc (int x, int y) {return x2*y;}// 仿函数
struct myclass {int operator()(int x, int y) {return x3*y;}
} myobj;void test_accumulate()
{cout \ntest_accumulate().......... \n; int init 100;int nums[] {10,20,30};cout using default accumulate: ;cout accumulate(nums,nums3,init); //160cout \n;cout using functionals minus: ;cout accumulate(nums, nums3, init, minusint()); //40这里用functor减法cout \n;cout using custom function: ;cout accumulate(nums, nums3, init, myfunc); //220cout \n;cout using custom object: ;cout accumulate(nums, nums3, init, myobj); //280cout \n;
}
}其中用到的minus仿函数如下 /// One of the link arithmetic_functors math functorsendlink.templatetypename _Tpstruct minus : public binary_function_Tp, _Tp, _Tp{_GLIBCXX14_CONSTEXPR_Tpoperator()(const _Tp __x, const _Tp __y) const{ return __x - __y; }};算法for_each templatetypename _InputIterator, typename _Function_GLIBCXX20_CONSTEXPR_Functionfor_each(_InputIterator __first, _InputIterator __last, _Function __f){// concept requirements__glibcxx_function_requires(_InputIteratorConcept_InputIterator)__glibcxx_requires_valid_range(__first, __last);for (; __first ! __last; __first)__f(*__first); // 对每个元素调用__f函数return __f; // N.B. [alg.foreach] says std::move(f) but its redundant.}测试for_each
#include iostream // std::cout
#include algorithm // std::for_each
#include vector // std::vector
namespace jj35
{
void myfunc (int i) { cout i;
}struct myclass { void operator() (int i) { cout i; }
} myobj;void test_for_each()
{cout \ntest_for_each().......... \n; vectorint myvec;myvec.push_back(10);myvec.push_back(20);myvec.push_back(30);for_each (myvec.begin(), myvec.end(), myfunc);cout endl; //output: 10 20 30for_each (myvec.begin(), myvec.end(), myobj);cout endl; //output: 10 20 30//since C11, range-based for- statementfor (auto elem : myvec)elem 5;for (auto elem : myvec)cout elem ; //output: 15 25 35
}
} 算法replace, replace_if, replace_copy
replace把旧值替换为新值
replace_if: 见到后面带if的函数就是要多给它一个条件这个条件一般是predicate /*** brief Replace each occurrence of one value in a sequence with another* value.* ingroup mutating_algorithms* param __first A forward iterator.* param __last A forward iterator.* param __old_value The value to be replaced.* param __new_value The replacement value.* return replace() returns no value.** For each iterator c i in the range p [__first,__last) if c *i * p __old_value then the assignment c *i p __new_value is performed.*/templatetypename _ForwardIterator, typename _Tp_GLIBCXX20_CONSTEXPRvoidreplace(_ForwardIterator __first, _ForwardIterator __last,const _Tp __old_value, const _Tp __new_value){// concept requirements__glibcxx_function_requires(_Mutable_ForwardIteratorConcept_ForwardIterator)__glibcxx_function_requires(_EqualOpConcepttypename iterator_traits_ForwardIterator::value_type, _Tp)__glibcxx_function_requires(_ConvertibleConcept_Tp,typename iterator_traits_ForwardIterator::value_type)__glibcxx_requires_valid_range(__first, __last);for (; __first ! __last; __first)if (*__first __old_value)*__first __new_value;}/*** brief Replace each value in a sequence for which a predicate returns* true with another value.* ingroup mutating_algorithms* param __first A forward iterator.* param __last A forward iterator.* param __pred A predicate.* param __new_value The replacement value.* return replace_if() returns no value.** For each iterator c i in the range p [__first,__last) if p __pred(*i)* is true then the assignment c *i p __new_value is performed.*/templatetypename _ForwardIterator, typename _Predicate, typename _Tp_GLIBCXX20_CONSTEXPRvoidreplace_if(_ForwardIterator __first, _ForwardIterator __last,_Predicate __pred, const _Tp __new_value){// concept requirements__glibcxx_function_requires(_Mutable_ForwardIteratorConcept_ForwardIterator)__glibcxx_function_requires(_ConvertibleConcept_Tp,typename iterator_traits_ForwardIterator::value_type)__glibcxx_function_requires(_UnaryPredicateConcept_Predicate,typename iterator_traits_ForwardIterator::value_type)__glibcxx_requires_valid_range(__first, __last);for (; __first ! __last; __first)if (__pred(*__first))*__first __new_value;}
算法count, count_if
容器带有成员函数count那么就要用容器自带的版本它是根据具体底层的结构实现出来适配自己的版本。
比如set/ multiset, map/multimap, unordered_set/ unordered_multiset, unordered_map/ unordered_multimap等就是自己实现的count。 算法findfind_if
set/ multiset, map/multimap, unordered_set/ unordered_multiset, unordered_map/ unordered_multimap等就是自己实现的find。 算法sort
容器list和forward_list带有成员函数sort用的时候要调用自己的sort 以下是一个使用 std::list 进行排序的简单示例代码
#include iostream
#include listint main() {// 创建一个包含一些整数的 liststd::listint myList {5, 2, 8, 1, 3};// 使用 list 提供的排序函数对元素进行排序myList.sort();// 输出排序后的结果std::cout Sorted list: ;for (const auto element : myList) {std::cout element ;}std::cout std::endl;return 0;
}在这个示例中我们首先创建了一个 std::list其中包含一些整数。然后使用 sort 函数对 list 中的元素进行升序排序。最后通过迭代器遍历输出排序后的结果。
需要注意的是std::list 自身提供了 sort 函数因为它是一个双向链表可以高效地在链表上进行排序。在使用 std::list 时可以直接调用其成员函数进行排序。如果要对其他容器进行排序可能需要使用全局的 std::sort 函数并传递容器的迭代器范围。
std::sort 算法要求能够使用随机访问迭代器而 std::list 的迭代器是双向迭代器不支持随机访问。因此不能直接使用 std::sort 对 std::list 进行排序。
关于reverse iteratorrbegin(), rend()
逆向迭代器rbegin()使用end()然后套用一个reverse_iterator适配器具体会在后面讲。 算法binary_search
它里面调用了lower_boundlower_bound是在有序序列中返回不小于val的第一个位置。binary_search最后返回的是bool意思是是否查找到某元素。 31 仿函数和函数对象
仿函数Function Object也被称为函数对象是一种在C中模拟函数行为的对象。它是一个类对象实现了函数调用操作符 operator()使得对象可以像函数一样被调用。仿函数可以以类对象的形式包装函数行为允许在算法中像调用函数一样使用对象。
仿函数只为算法服务 下面的identityselect1stselect2nd都是前面出现过的都是仿函数。不过这是GNU C编译器独有的。 functors可以使用函数类的对象默认的比较等
下面介绍一下lessint()的写法 less是一个类型后面加括号()表示创建一个对象创建临时对象 上图中可以看到右下角greater,less 都继承了binary_functionT, T, bool,表示有两个操作数的操作对应的还有unary_function表示有1个操作数的操作。 /*** Helper for defining adaptable binary function objects.* deprecated Deprecated in C11, no longer in the standard since C17.*/templatetypename _Arg1, typename _Arg2, typename _Resultstruct binary_function{/// c first_argument_type is the type of the first argumenttypedef _Arg1 first_argument_type; /// c second_argument_type is the type of the second argumenttypedef _Arg2 second_argument_type;/// c result_type is the return typetypedef _Result result_type;};/*** Helper for defining adaptable unary function objects.* deprecated Deprecated in C11, no longer in the standard since C17.*/templatetypename _Arg, typename _Resultstruct unary_function{/// c argument_type is the type of the argumenttypedef _Arg argument_type; /// c result_type is the return typetypedef _Result result_type; };
这两个结构体 binary_function 和 unary_function 是用于帮助定义可适应的二元和一元函数对象的辅助结构体。它们在早期的 C 标准中起到了一些作用但在 C11 标准之后被废弃从 C17 标准起它们就不再是标准库的一部分了。 binary_function binary_function 用于定义可适应的二元函数对象。在这个结构体中定义了三个成员类型 first_argument_type 表示函数对象的第一个参数的类型。second_argument_type 表示函数对象的第二个参数的类型。result_type 表示函数对象的返回类型。 unary_function unary_function 用于定义可适应的一元函数对象。在这个结构体中定义了两个成员类型 argument_type 表示函数对象的参数的类型。result_type 表示函数对象的返回类型。
需要注意的是由于这两个结构体已经在 C11 标准中被废弃它们在现代 C 中并不建议使用。在新的标准中可以直接使用更简洁的方式定义函数对象例如使用 std::function 或者直接定义一个符合函数对象的类。 32 存在多种Adapter
在STL中“adapter”适配器通常指的是一类用于在不同接口之间进行转换的工具类或函数。适配器的目标是让原本不兼容的接口能够协同工作。
在STL中适配器常见的有以下几种
迭代器适配器Iterator Adapters 用于在不同迭代器之间进行转换或提供额外功能的适配器。例如std::back_inserter、std::front_inserter、std::inserter 等。 函数适配器Function Adapters 用于在函数对象之间进行转换或提供额外功能的适配器。例如std::bind、std::function 等。 容器适配器Container Adapters 提供不同接口的容器例如std::stack、std::queue、std::priority_queue 等。
这些适配器提供了一种通用的方式来处理不同接口之间的兼容性问题使得不同组件可以更加灵活地组合在一起。适配器模式是一种设计模式它通过将一个类的接口转换成客户端希望的另外一个接口从而使得原本不兼容的类可以协同工作。 在C STL中适配器通常使用复合composition来实现。复合是一种对象关系其中一个对象包含另一个对象从而形成更复杂的对象。适配器通过包含或组合现有的组件来实现接口的转换或功能的增强。
以下是一个使用复合实现迭代器适配器的简单示例
#include iostream
#include vector
#include iterator// 自定义迭代器适配器用于将输入迭代器逆序输出
template typename Iterator
class ReverseIteratorAdapter {
public:// 构造函数接受原始迭代器ReverseIteratorAdapter(Iterator it) : originalIterator(it) {}// 适配器的解引用操作typename Iterator::value_type operator*() const {Iterator temp originalIterator;return *(--temp); // 逆序输出}// 其他适配器需要实现的操作如递增ReverseIteratorAdapter operator() {--originalIterator;return *this;}// 判断相等bool operator(const ReverseIteratorAdapter other) const {return originalIterator other.originalIterator;}// 不相等bool operator!(const ReverseIteratorAdapter other) const {return !(*this other);}private:Iterator originalIterator; // 包含原始迭代器
};int main() {std::vectorint vec {1, 2, 3, 4, 5};// 使用适配器包装原始迭代器ReverseIteratorAdapterstd::vectorint::iterator reverseIter(vec.end());// 使用适配器进行逆序输出while (reverseIter ! ReverseIteratorAdapterstd::vectorint::iterator(vec.begin())) {std::cout *reverseIter ;reverseIter;}return 0;
}在这个例子中ReverseIteratorAdapter 是一个迭代器适配器它通过包含一个原始迭代器实现逆序输出的功能。这里使用复合将原始迭代器作为成员变量嵌入到适配器类中。适配器实现了解引用操作、递增、相等性等迭代器操作以便能够被使用在STL算法中。
容器adapterstackqueue
stack和queue都内含一个deque 33 函数适配器Binder2nd
函数适配器bind2nd的介绍
下面less()不是函数调用而是typename加小括号表示创建临时对象,它的类型是less
cout count_if(vi.begin(), vi.end(),not1(bind2nd(lessint(), 40)));对于bind2nd函数
/// One of the link binders binder functorsendlink.templatetypename _Operationclass binder2nd: public unary_functiontypename _Operation::first_argument_type,typename _Operation::result_type{protected:_Operation op; // 就是上面传进来的lessint()typename _Operation::second_argument_type value; // 上面传进来的40public:binder2nd(const _Operation __x,const typename _Operation::second_argument_type __y): op(__x), value(__y) { }typename _Operation::result_typeoperator()(const typename _Operation::first_argument_type __x) const{ return op(__x, value); }// _GLIBCXX_RESOLVE_LIB_DEFECTS// 109. Missing binders for non-const sequence elementstypename _Operation::result_type// adpater修饰functor本身也要表现出functor的样子所以要重载()operator()(typename _Operation::first_argument_type __x) const{ return op(__x, value); }} _GLIBCXX11_DEPRECATED_SUGGEST(std::bind);/// One of the link binders binder functorsendlink.templatetypename _Operation, typename _Tpinline binder2nd_Operationbind2nd(const _Operation __fn, const _Tp __x){typedef typename _Operation::second_argument_type _Arg2_type;return binder2nd_Operation(__fn, _Arg2_type(__x)); // typename()表示创建临时对象} /** } */
上面的代码是C标准库中与函数适配器相关的部分主要涉及函数适配器binder2nd和与之相关的bind2nd函数。 binder2nd类 binder2nd是函数适配器之一用于将一个二元操作函数_Operation和一个固定的值__y绑定在一起。binder2nd类继承自unary_function表示其为一元函数对象其operator()用于执行绑定的操作。构造函数接受一个二元操作函数对象和一个固定值将它们保存在op和value成员变量中。operator()实现了函数适配器的主要功能接受一个参数 __x并调用保存的二元操作函数对象 op传递参数 __x 和固定值 value 进行操作。 bind2nd函数 bind2nd函数是一个工厂函数用于创建binder2nd的实例。接受一个二元操作函数对象 __fn 和一个值 __x。利用binder2nd类的构造函数创建一个binder2nd实例将 __fn 和 __x 绑定在一起。
这种函数适配器的设计允许将一个带有两个参数的二元操作函数转换成一个只接受一个参数的一元函数对象通过在其中固定一个参数的值。这样的适配器提供了更多的灵活性使得这些函数可以更容易地与STL算法一起使用。在这里binder2nd被用于在二元操作函数中固定一个参数值形成一个新的一元操作函数。 34 函数适配器not1
/// One of the link negators negation functorsendlink.templatetypename _Predicate_GLIBCXX14_CONSTEXPRinline unary_negate_Predicatenot1(const _Predicate __pred){ return unary_negate_Predicate(__pred); } // typename()创建临时对象调用构造函数/// One of the link negators negation functorsendlink.templatetypename _Predicateclass unary_negate: public unary_functiontypename _Predicate::argument_type, bool{protected:_Predicate _M_pred; // 内部成员public:_GLIBCXX14_CONSTEXPRexplicitunary_negate(const _Predicate __x) : _M_pred(__x) { }_GLIBCXX14_CONSTEXPRbooloperator()(const typename _Predicate::argument_type __x) const{ return !_M_pred(__x); }}; 35 新型适配器bind
std::bind是C标准库中的一个函数模板用于创建函数对象函数适配器并部分应用参数。它允许将参数绑定到一个函数对象的参数并在需要时延迟执行。std::bind的主要作用是将一个可调用对象函数、函数指针、成员函数、函数对象等与一组参数绑定在一起形成一个新的可调用对象。
std::bind的基本语法如下
templateclass F, class... Args
std::bind(F f, Args... args);其中F是可调用对象的类型Args...是参数列表。
使用std::bind时可以将参数按照所需的顺序绑定也可以使用std::placeholders::_1、std::placeholders::_2等占位符表示参数的位置。通过这种方式可以实现参数的部分绑定、参数顺序的改变等操作。
下面是一个简单的示例演示了std::bind的使用
#include iostream
#include functional// 定义一个函数对象
struct Adder {int operator()(int a, int b, int c) const {return a b c;}
};int main() {// 使用 std::bind 绑定参数auto adder std::bind(Adder(), std::placeholders::_1, 2, std::placeholders::_2);// 调用绑定后的函数对象std::cout adder(1, 3) std::endl; // 输出6return 0;
}在上面的例子中std::bind将Adder()一个函数对象与参数1、2、std::placeholders::_2绑定在一起形成了一个新的函数对象adder。当调用adder(1, 3)时实际上是调用了Adder()(1, 2, 3)输出结果为6。这就实现了函数参数的部分绑定。
36 迭代器适配器reverse iterator
适配器adapter的共性是把要改造的东西记起来后面对其进行改造。 37 迭代器适配器inserter
对操作符重载将iterator的赋值操作改变为insert操作。 38 ostream iterator
ostream_iterator 是 C 标准库中的输出迭代器用于将数据输出到输出流ostream。它是一个模板类通常用于将容器中的元素输出到输出流或者将其他可输出的数据类型输出到流中。
ostream_iterator 的基本用法如下
#include iostream
#include iteratorint main() {std::ostream_iteratorint intOstreamIterator(std::cout, ); // 创建 int 类型的 ostream_iteratorfor (int i 1; i 5; i) {*intOstreamIterator i; // 将数据输出到流}std::cout std::endl;return 0;
}在这个例子中ostream_iterator 被用来输出整数到标准输出流 std::cout并使用空格分隔每个输出的元素。可以看到通过 *intOstreamIterator i; 这样的语法将整数 i 输出到流中。
除了整数ostream_iterator 还可以用于输出其他类型的数据例如字符串、自定义类型等。其构造函数接受两个参数第一个参数是输出流第二个参数是用于分隔输出元素的字符串。
#include iostream
#include iterator
#include vectorint main() {std::vectorstd::string words {Hello, World, C};std::ostream_iteratorstd::string strOstreamIterator(std::cout, \n); // 创建 string 类型的 ostream_iteratorfor (const auto word : words) {*strOstreamIterator word; // 将字符串输出到流}return 0;
}这个例子中ostream_iterator 被用来输出字符串到标准输出流并使用换行符 \n 分隔每个输出的字符串。 上图中可以看到copy函数第三个参数传入的是ostream_iterator在ostream_iterator对赋值运算符和*, 等符号都进行了重载。实现把值输出给ostream。
39 istream iterator
istream_iterator 是 C 标准库中的输入迭代器用于从输入流istream中读取数据。它是一个模板类通常用于从输入流中读取数据到容器中或者直接读取输入流中的数据。
istream_iterator 的基本用法如下
#include iostream
#include iterator
#include vectorint main() {std::vectorint numbers;std::istream_iteratorint intIstreamIterator(std::cin); // 创建 int 类型的 istream_iterator// 从标准输入流中读取整数并将其添加到容器中直到遇到文件结束符或非整数输入while (intIstreamIterator ! std::istream_iteratorint()) {numbers.push_back(*intIstreamIterator);intIstreamIterator;}// 输出读取到的整数for (const auto num : numbers) {std::cout num ;}return 0;
}在这个例子中istream_iterator 被用来从标准输入流 std::cin 中读取整数并将它们添加到 numbers 容器中。当遇到文件结束符或非整数输入时输入过程结束。随后通过循环遍历 numbers 容器将读取到的整数输出到标准输出流。
istream_iterator 的构造函数接受一个输入流作为参数。它的行为是通过迭代器解引用操作符 * 从输入流中读取下一个元素。在上述例子中intIstreamIterator; 语句用于使 istream_iterator 前进到输入流的下一个元素。
除了整数istream_iterator 还可以用于读取其他类型的数据例如字符串、自定义类型等。 下面还是结合copy和istream iterator适配器对操作符进行重载实现和cin的同步。 后记
完成第三讲的学习这里主要涉及algorithm仿函数适配器等的知识。
