STL标准库与泛型编程（侯捷）

本文是学习笔记，仅供个人学习使用。如有侵权，请联系删除。

参考链接

Youbute: 侯捷-STL标准库与泛型编程

B站: 侯捷 - STL

Github:STL源码剖析中源码 https://github.com/SilverMaple/STLSourceCodeNote/tree/master

Github:课程ppt和源码 https://github.com/ZachL1/Bilibili-plus

下面是C++标准库体系结构与内核分析的第三讲

27 算法的形式

算法algorithm是function template，而其他的container，interator，functor，adapter，allocator都是class template。

算法看不到container，只看得到iterator（由container提供）

28 迭代器的分类（category）

iterator_category 是 C++ 中迭代器的一种属性，用于表示迭代器的类型或范畴。它属于 C++ 的迭代器概念中的一部分，主要包括以下几个范畴：

1. Input Iterator（输入迭代器）：

   • std::input_iterator_tag

2. Output Iterator（输出迭代器）：

   • std::output_iterator_tag

3. Forward Iterator（前向迭代器）：

   • std::forward_iterator_tag

4. Bidirectional Iterator（双向迭代器）：

   • std::bidirectional_iterator_tag

5. Random Access Iterator（随机访问迭代器）：

   • std::random_access_iterator_tag

这些标签用于描述迭代器的能力和行为，从而影响了对迭代器的操作。例如，对于 std::advance 函数，它会根据迭代器的类型选择不同的实现，以保证效率。

具体的使用示例如下：

#include <iostream>
#include <iterator>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    // 获取迭代器类型
    using IteratorType = std::vector<int>::iterator;
    IteratorType it = vec.begin();

    // 使用 iterator_category 获取迭代器类型
    std::cout << "Iterator category: ";
    if (std::is_same<std::iterator_traits<IteratorType>::iterator_category,
                     std::random_access_iterator_tag>::value) {
        std::cout << "Random Access Iterator" << std::endl;
    } else if (std::is_same<std::iterator_traits<IteratorType>::iterator_category,
                            std::bidirectional_iterator_tag>::value) {
        std::cout << "Bidirectional Iterator" << std::endl;
    } else if (std::is_same<std::iterator_traits<IteratorType>::iterator_category,
                            std::forward_iterator_tag>::value) {
        std::cout << "Forward Iterator" << std::endl;
    } else if (std::is_same<std::iterator_traits<IteratorType>::iterator_category,
                            std::input_iterator_tag>::value) {
        std::cout << "Input Iterator" << std::endl;
    } else if (std::is_same<std::iterator_traits<IteratorType>::iterator_category,
                            std::output_iterator_tag>::value) {
        std::cout << "Output Iterator" << std::endl;
    }

    return 0;
}

在这个示例中，我们使用 std::iterator_traits 获取迭代器的属性，然后根据 iterator_category 输出不同类型的迭代器。在实际应用中，这些信息通常用于实现泛型算法，以适应不同类型的迭代器。

对于下图中的各种容器，简单介绍一下它们迭代器是什么种类：

array，vector，deque它们是连续的，它们的迭代器是Random Access Iterator，list的迭代器是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
#include<bits/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;    }

template<typename I>
void display_category(I itr)
{
   typename iterator_traits<I>::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(array<int,10>::iterator()); // random_access_iterator
  	display_category(vector<int>::iterator());  // random_access_iterator
  	display_category(list<int>::iterator());	// bidirectional_iterator
  	display_category(forward_list<int>::iterator());  // forward_iterator
  	display_category(deque<int>::iterator()); // random_access_iterator

  	display_category(set<int>::iterator()); // bidirectional_iterator
  	display_category(map<int,int>::iterator()); // bidirectional_iterator
  	display_category(multiset<int>::iterator()); // bidirectional_iterator
  	display_category(multimap<int,int>::iterator()); // bidirectional_iterator
    
  	display_category(unordered_set<int>::iterator()); // forward_iterator
  	display_category(unordered_map<int,int>::iterator()); // forward_iterator
  	display_category(unordered_multiset<int>::iterator()); // forward_iterator
  	display_category(unordered_multimap<int,int>::iterator());	   // forward_iterator
	    	
  	display_category(istream_iterator<int>()); // input_iterator
  	display_category(ostream_iterator<int>(cout,"")); // output_iterator
}															 
}

int main(int argc, char** argv) 
{
	jj33::test_iterator_category();	
	return 0;
}

输出结果：

test_iterator_category().......... 
random_access_iterator
typeid(itr).name()= Pi

random_access_iterator
typeid(itr).name()= N9__gnu_cxx17__normal_iteratorIPiSt6vectorIiSaIiEEEE

bidirectional_iterator
typeid(itr).name()= St14_List_iteratorIiE

forward_iterator
typeid(itr).name()= St18_Fwd_list_iteratorIiE

random_access_iterator
typeid(itr).name()= St15_Deque_iteratorIiRiPiE

bidirectional_iterator
typeid(itr).name()= St23_Rb_tree_const_iteratorIiE

bidirectional_iterator
typeid(itr).name()= St17_Rb_tree_iteratorISt4pairIKiiEE

bidirectional_iterator
typeid(itr).name()= St23_Rb_tree_const_iteratorIiE

bidirectional_iterator
typeid(itr).name()= St17_Rb_tree_iteratorISt4pairIKiiEE

forward_iterator
typeid(itr).name()= NSt8__detail14_Node_iteratorIiLb1ELb0EEE

forward_iterator
typeid(itr).name()= NSt8__detail14_Node_iteratorISt4pairIKiiELb0ELb0EEE

forward_iterator
typeid(itr).name()= NSt8__detail14_Node_iteratorIiLb1ELb0EEE

forward_iterator
typeid(itr).name()= NSt8__detail14_Node_iteratorISt4pairIKiiELb0ELb0EEE

input_iterator
typeid(itr).name()= St16istream_iteratorIicSt11char_traitsIcElE

output_iterator
typeid(itr).name()= St16ostream_iteratorIicSt11char_traitsIcEE

istream_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_tag，advance只能向前
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_tag，advance方向可正可负，实现如下
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;
  else
    while (__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_tag，bidirectional_iterator_tag，random_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 主要包括以下几个方面的功能：

1. 类型特征查询： Type traits 允许你在编译时查询某个类型的特征，例如是否是指针类型、是否是引用类型、是否是数组类型等。这些信息可以通过类似 std::is_pointer、std::is_reference、std::is_array 等 type traits 来获取。

2. 类型转换和操作： Type traits 提供了一些模板工具，使得可以在编译时进行类型的转换和操作。例如，可以使用 std::remove_pointer、std::remove_reference 来移除指针或引用。

3. 条件判断： Type traits 还提供了条件判断，可以根据某个类型是否满足某个条件来进行编译期间的分支选择。例如，std::conditional 根据条件选择不同的类型。

4. 类型比较： 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 <iostream>

int 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 iterator，rotate函数想要接收forward iterator等等。

30 算法源代码剖析（11个例子）

哪些是C++标准库提供的algorithm呢？需要符合如下接口

template<typename Iterator>
std::Algorithm(Iterator itr1, Iterator itr2, ...)
{
    ...
}

下图中的qsort和bsearch是C语言的函数，而count_if，find，sort等是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 x+2*y;}

// 仿函数
struct myclass {
	int operator()(int x, int y) {return x+3*y;}
} myobj;

void test_accumulate()
{
  cout << "\ntest_accumulate().......... \n";	
  int init = 100;
  int nums[] = {10,20,30};

  cout << "using default accumulate: ";
  cout << accumulate(nums,nums+3,init);  //160
  cout << '\n';

  cout << "using functional's minus: ";
  cout << accumulate(nums, nums+3, init, minus<int>()); //40，这里用functor，减法
  cout << '\n';

  cout << "using custom function: ";
  cout << accumulate(nums, nums+3, init, myfunc);	//220
  cout << '\n';

  cout << "using custom object: ";
  cout << accumulate(nums, nums+3, init, myobj);	//280
  cout << '\n';
}															 
}

其中用到的minus仿函数如下

  /// One of the @link arithmetic_functors math functors@endlink.
  template<typename _Tp>
    struct minus : public binary_function<_Tp, _Tp, _Tp>
    {
      _GLIBCXX14_CONSTEXPR
      _Tp
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x - __y; }
    };

算法for_each

  template<typename _InputIterator, typename _Function>
    _GLIBCXX20_CONSTEXPR
    _Function
    for_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 it's 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";	
	
  vector<int> 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 30

  for_each (myvec.begin(), myvec.end(), myobj);
  cout << endl;		//output: 10 20 30
  
  //since C++11, range-based for- statement
  for (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.
  */
  template<typename _ForwardIterator, typename _Tp>
    _GLIBCXX20_CONSTEXPR
    void
    replace(_ForwardIterator __first, _ForwardIterator __last,
	    const _Tp& __old_value, const _Tp& __new_value)
    {
      // concept requirements
      __glibcxx_function_requires(_Mutable_ForwardIteratorConcept<
				  _ForwardIterator>)
      __glibcxx_function_requires(_EqualOpConcept<
	    typename 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.
  */
  template<typename _ForwardIterator, typename _Predicate, typename _Tp>
    _GLIBCXX20_CONSTEXPR
    void
    replace_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。

算法find，find_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 <list>

int main() {
    // 创建一个包含一些整数的 list
    std::list<int> 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 iterator，rbegin(), rend()

逆向迭代器，rbegin()使用end()，然后套用一个reverse_iterator适配器，具体会在后面讲。

算法binary_search

它里面调用了lower_bound，lower_bound是在有序序列中返回不小于val的第一个位置。binary_search最后返回的是bool，意思是是否查找到某元素。

31 仿函数和函数对象

仿函数（Function Object），也被称为函数对象，是一种在C++中模拟函数行为的对象。它是一个类对象，实现了函数调用操作符 operator()，使得对象可以像函数一样被调用。仿函数可以以类对象的形式包装函数行为，允许在算法中像调用函数一样使用对象。

仿函数只为算法服务

下面的identity，select1st，select2nd都是前面出现过的，都是仿函数。不过这是GNU C++编译器独有的。

functors可以使用函数，类的对象，默认的比较等

下面介绍一下less<int>()的写法， less是一个类型，后面加括号()表示创建一个对象（创建临时对象）

上图中可以看到右下角greater,less 都继承了binary_function<T, T, bool>,表示有两个操作数的操作，对应的还有unary_function，表示有1个操作数的操作。

 /**
   *  Helper for defining adaptable binary function objects.
   *  @deprecated Deprecated in C++11, no longer in the standard since C++17.
   */
  template<typename _Arg1, typename _Arg2, typename _Result>
    struct binary_function
    {
      /// @c first_argument_type is the type of the first argument
      typedef _Arg1 	first_argument_type; 

      /// @c second_argument_type is the type of the second argument
      typedef _Arg2 	second_argument_type;

      /// @c result_type is the return type
      typedef _Result 	result_type;
    };

/**
   *  Helper for defining adaptable unary function objects.
   *  @deprecated Deprecated in C++11, no longer in the standard since C++17.
   */
  template<typename _Arg, typename _Result>
    struct unary_function
    {
      /// @c argument_type is the type of the argument
      typedef _Arg 	argument_type;   

      /// @c result_type is the return type
      typedef _Result 	result_type;  
    };

这两个结构体 binary_function 和 unary_function 是用于帮助定义可适应的二元和一元函数对象的辅助结构体。它们在早期的 C++ 标准中起到了一些作用，但在 C++11 标准之后被废弃，从 C++17 标准起，它们就不再是标准库的一部分了。

1. binary_function：

   • binary_function 用于定义可适应的二元函数对象。在这个结构体中，定义了三个成员类型：
     • first_argument_type 表示函数对象的第一个参数的类型。
     • second_argument_type 表示函数对象的第二个参数的类型。
     • result_type 表示函数对象的返回类型。

2. unary_function：

   • unary_function 用于定义可适应的一元函数对象。在这个结构体中，定义了两个成员类型：
     • argument_type 表示函数对象的参数的类型。
     • result_type 表示函数对象的返回类型。

需要注意的是，由于这两个结构体已经在 C++11 标准中被废弃，它们在现代 C++ 中并不建议使用。在新的标准中，可以直接使用更简洁的方式定义函数对象，例如使用 std::function 或者直接定义一个符合函数对象的类。

32 存在多种Adapter

在STL中，“adapter”（适配器）通常指的是一类用于在不同接口之间进行转换的工具类或函数。适配器的目标是让原本不兼容的接口能够协同工作。

在STL中，适配器常见的有以下几种：

1. 迭代器适配器（Iterator Adapters）：
   • 用于在不同迭代器之间进行转换或提供额外功能的适配器。例如，std::back_inserter、std::front_inserter、std::inserter 等。
2. 函数适配器（Function Adapters）：
   • 用于在函数对象之间进行转换或提供额外功能的适配器。例如，std::bind、std::function 等。
3. 容器适配器（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::vector<int> vec = {1, 2, 3, 4, 5};

    // 使用适配器包装原始迭代器
    ReverseIteratorAdapter<std::vector<int>::iterator> reverseIter(vec.end());

    // 使用适配器进行逆序输出
    while (reverseIter != ReverseIteratorAdapter<std::vector<int>::iterator>(vec.begin())) {
        std::cout << *reverseIter << " ";
        ++reverseIter;
    }

    return 0;
}

在这个例子中，ReverseIteratorAdapter 是一个迭代器适配器，它通过包含一个原始迭代器实现逆序输出的功能。这里使用复合，将原始迭代器作为成员变量嵌入到适配器类中。适配器实现了解引用操作、递增、相等性等迭代器操作，以便能够被使用在STL算法中。

容器adapter：stack，queue

stack和queue都内含一个deque

33 函数适配器Binder2nd

函数适配器bind2nd的介绍

下面less()不是函数调用，而是typename加小括号，表示创建临时对象,它的类型是less

cout << count_if(vi.begin(), vi.end(),
                not1(bind2nd(less<int>(), 40)));

对于bind2nd函数

/// One of the @link binders binder functors@endlink.
  template<typename _Operation>
    class binder2nd
    : public unary_function<typename _Operation::first_argument_type,
			    typename _Operation::result_type>
    {
    protected:
      _Operation op; // 就是上面传进来的less<int>()
      typename _Operation::second_argument_type value;  // 上面传进来的40

    public:
      binder2nd(const _Operation& __x,
		const typename _Operation::second_argument_type& __y)
      : op(__x), value(__y) { }

      typename _Operation::result_type
      operator()(const typename _Operation::first_argument_type& __x) const
      { return op(__x, value); }

      // _GLIBCXX_RESOLVE_LIB_DEFECTS
      // 109.  Missing binders for non-const sequence elements
      typename _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 functors@endlink.
  template<typename _Operation, typename _Tp>
    inline binder2nd<_Operation>
    bind2nd(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函数。

1. binder2nd类：

   • binder2nd是函数适配器之一，用于将一个二元操作函数（_Operation）和一个固定的值（__y）绑定在一起。
   • binder2nd类继承自unary_function，表示其为一元函数对象，其operator()用于执行绑定的操作。
   • 构造函数接受一个二元操作函数对象和一个固定值，将它们保存在op和value成员变量中。
   • operator()实现了函数适配器的主要功能，接受一个参数 __x，并调用保存的二元操作函数对象 op，传递参数 __x 和固定值 value 进行操作。

2. bind2nd函数：

   • bind2nd函数是一个工厂函数，用于创建binder2nd的实例。
   • 接受一个二元操作函数对象 __fn 和一个值 __x。
   • 利用binder2nd类的构造函数创建一个binder2nd实例，将 __fn 和 __x 绑定在一起。

这种函数适配器的设计允许将一个带有两个参数的二元操作函数转换成一个只接受一个参数的一元函数对象，通过在其中固定一个参数的值。这样的适配器提供了更多的灵活性，使得这些函数可以更容易地与STL算法一起使用。在这里，binder2nd被用于在二元操作函数中固定一个参数值，形成一个新的一元操作函数。

34 函数适配器not1

/// One of the @link negators negation functors@endlink.
  template<typename _Predicate>
    _GLIBCXX14_CONSTEXPR
    inline unary_negate<_Predicate>
    not1(const _Predicate& __pred)
    { return unary_negate<_Predicate>(__pred); } // typename()创建临时对象，调用构造函数

/// One of the @link negators negation functors@endlink.
  template<typename _Predicate>
    class unary_negate
    : public unary_function<typename _Predicate::argument_type, bool>
    {
    protected:
      _Predicate _M_pred; // 内部成员

    public:
      _GLIBCXX14_CONSTEXPR
      explicit
      unary_negate(const _Predicate& __x) : _M_pred(__x) { }

      _GLIBCXX14_CONSTEXPR
      bool
      operator()(const typename _Predicate::argument_type& __x) const
      { return !_M_pred(__x); }
    };

35 新型适配器bind

std::bind是C++标准库中的一个函数模板，用于创建函数对象（函数适配器）并部分应用参数。它允许将参数绑定到一个函数对象的参数，并在需要时延迟执行。std::bind的主要作用是将一个可调用对象（函数、函数指针、成员函数、函数对象等）与一组参数绑定在一起，形成一个新的可调用对象。

std::bind的基本语法如下：

template<class 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;  // 输出：6

    return 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 <iterator>

int main() {
    std::ostream_iterator<int> intOstreamIterator(std::cout, " ");  // 创建 int 类型的 ostream_iterator

    for (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 <vector>

int main() {
    std::vector<std::string> words = {"Hello", "World", "C++"};

    std::ostream_iterator<std::string> strOstreamIterator(std::cout, "\n");  // 创建 string 类型的 ostream_iterator

    for (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 <vector>

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

    std::istream_iterator<int> intIstreamIterator(std::cin);  // 创建 int 类型的 istream_iterator

    // 从标准输入流中读取整数，并将其添加到容器中，直到遇到文件结束符或非整数输入
    while (intIstreamIterator != std::istream_iterator<int>()) {
        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，仿函数，适配器等的知识。