手写stl源码过程中获取的知识

这里记录了我写stl过程中遇到的问题和知识点。里面涉及了stl六大件的知识点。

计算迭代器间的距离

分 input_iterator_tag 和 random_access_iterator_tag 的版本。

// distance 的 input_iterator_tag 的版本
template <class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance_dispatch(InputIterator first, InputIterator last, input_iterator_tag)
{
  typename iterator_traits<InputIterator>::difference_type n = 0;
  while (first != last)
  {
    ++first;
    ++n;
  }
  return n;
}

// distance 的 random_access_iterator_tag 的版本
template <class RandomIter>
typename iterator_traits<RandomIter>::difference_type
distance_dispatch(RandomIter first, RandomIter last,
                  random_access_iterator_tag)
{
  return last - first;
}

萃取器萃取过程

如果是原生指针 T 或者 const T 就用偏特化版本

// 萃取迭代器的特性
template <class Iterator>
struct iterator_traits
    : public iterator_traits_helper<Iterator, has_iterator_cat<Iterator>::value> {};   // 根据迭代器是否有 iterator_category 选择不同函数

// 针对原生指针的偏特化版本
template <class T>
struct iterator_traits<T*>
{
    typedef random_access_iterator_tag             iterator_category;
    typedef T                                      value_type;
    typedef T*                                     pointer;
    typedef T&                                     reference;
    typedef ptrdiff_t                              difference_type;   
};

// 针对 const * 的偏特化
template <class T>
struct iterator_traits<const T*>
{
    typedef random_access_iterator_tag          iterator_category;
    typedef T                                   value_type;
    typedef const T*                            pointer;
    typedef const T&                            reference;
    typedef ptrdiff_t                           difference_type;                                  
};

如果是普通的类的就是，进入iterator_traits_helper<Iterator, has_iterator_cat<Iterator>::value> {},判断是否有iterator_category属性。

template <class Iterator, bool>
struct iterator_traits_helper {};

template <class Iterator>
struct iterator_traits_helper<Iterator, true>
    : public iterator_traits_impl<Iterator,
    /*
    如果 Iterator::iterator_category 能转换为 input_iterator_tag 
    或者 Iterator::iterator_category 能转换为 output_iterator_tag
    就继承自 iterator_traits_impl<Iterator, true>
    因为 迭代器的5个属性中，有3个属于继承的，所以只要判断这两个就可以判断是否有 iterator_category 了、
    has_iterator_cat 判断是否有 iterator_category，这个判断 iterator_category 是不是这 5 个
  */
    std::is_convertible<typename Iterator::iterator_category, input_iterator_tag>::value ||
    std::is_convertible<typename Iterator::iterator_category, output_iterator_tag>::value>       // 如果 Iterator::iterator_category 能转化为 output_iterator_tag 返回一个true
{
};

如果有就进入iterator_traits_impl<Iterator, true>，返回该迭代器类中定义的属性就好了。

template <class Iterator, bool>
struct iterator_traits_impl {};

template <class Iterator>
struct iterator_traits_impl<Iterator, true>
{
    typedef typename Iterator::iterator_category iterator_category;
    typedef typename Iterator::value_type        value_type;
    typedef typename Iterator::pointer           pointer;
    typedef typename Iterator::reference         reference;
    typedef typename Iterator::difference_type   difference_type;
};

移动构造函数

在移动构造函数中，通常会执行以下操作：

• 将源对象的资源指针或资源句柄赋值给目标对象，避免深拷贝。
• 将源对象的资源指针或资源句柄置为nullptr，以确保源对象析构时不会释放资源。

移动构造语义中，一般是将源对象的指针赋值给新的对象，然后将源对象的指针赋值为nullptr，这个过程中没有内存的创建，只是资源管理权的转移。

为什么要将源对象的指针赋值为nullptr呢？

因为它是转移指针，如果不把源对象的指针设置为nullptr，那么就是相当于源对象和现在对象都指向这个资源，如果源对象销毁了调用析构函数，就会将这个资源给释放了。
也不能调用析构函数，因为也会释放这片资源。将源对象的指针设置为nullptr，这样源对象就处于有效但不再拥有资源的状态，这样如果源对象销毁时，就不会释放这片资源。

销毁元素destroy

有两种。一种是传入一个指针的，另一个是传入两个指针的一个指向开头一个指向结尾。
传入一个指针的，先利用std::is_trivially_destructible<Ty>{}判断是不是具有平凡的析构函数，然后传入对应的重载函数中。

template <class Ty>
void destroy(Ty* pointer)
{
    destroy_one(pointer, std::is_trivially_destructible<Ty>{});
}

template <class ForwardIter>
void destroy(ForwardIter first, ForwardIter last)
{
    destroy_cat(first, last, std::is_trivially_destructible<
                    typename iterator_traits<ForwardIter>::value_type>{});
}

如果是平凡的析构函数就什么也不做。平凡的啥也不用干，也干不了，因为没有占用资源（动态分配的内存，关闭文件句柄，锁等）就和int啥的一样。
你平时用int的时候也没调用析构函数吧，就类的调用了析构函数。
如果是非凡的析构函数（就是显示定义了自己的析构函数），就调用对应的析构函数就行了。

template <class Ty>
void destroy_one(Ty*, std::true_type) {}

// 不具有平凡的析构函数（在类中显式的定义了类的析构函数）
template <class Ty>
void destroy_one(Ty* pointer, std::false_type)
{
    if (pointer != nullptr)
    {
        pointer->~Ty();
    }
}

释放一个段的，也就是遍历一边，然后一个一个调用destroy_one释放内存。

template <class ForwardIter>
void destroy_cat(ForwardIter , ForwardIter , std::true_type) {}

template <class ForwardIter>
void destroy_cat(ForwardIter first, ForwardIter last, std::false_type)
{
  for (; first != last; ++first)
    destroy(&*first);
}

vector的容量capacity

到end_是已经有元素的内存，假如我们没有capacity，end_就是最后元素的最后，我们每次加入一个新的数据，就要往后什么一个内存然后把数据放到这里吧（因为
vector是连续存储的），但是我们有没有想过：最后一个元素后面的空间是否已经被用了，如果其他地方用了，那么这就相当于覆盖了它的数据，这是十分不安全的。
那么capacity应运而生，也就是我先声明一下，从begin到capacity这都是我(vector)的，其他程序不要占用了。如果vector的元素超过了capacity,就会成倍
扩增capacity，然后找到一个适合的地址区域，将当前元素拷贝过去。

销毁元素和释放内存不一样

vector扩容时，通常先销毁元素，然后再释放内存。

重载vector移动赋值操作符

先销毁当前对象的元素，并释放当前vector的内存，并重新分配。

// 移动赋值操作符
template <class T>
vector<T>& vector<T>::operator=(vector&& rhs) noexcept
{
  destroy_and_recover(begin_, end_, cap_ - begin_);
  begin_ = rhs.begin_;
  end_ = rhs.end_;
  cap_ = rhs.cap_;
  rhs.begin_ = nullptr;
  rhs.end_ = nullptr;
  rhs.cap_ = nullptr;
  return *this;
}

支持随机访问的迭代器类型可以通过简单的减法操作来确定元素的数量

随机访问的迭代器可以直接end - first指针的方法获取元素的数量，因为空间是连续的，数据都是存在一段连续的空间中。指针本质就是地址，地址是连续的，
当然就可以通过首位地址相减获取元素数量了。这里为什么不再减去1呢，因为end那是开区间，取不到。
但是如果不是支持随机访问的迭代器，就只能从第一个元素遍历到最后一个元素了，比如链表，因为数据不是存在一段连续的空间中，所以无法通过首尾地址相减来获取
元素的数量。

记录一下在写STL源码中遇到的知识点。以后有时间再归纳总结一下。

非平凡析构函数、平凡析构函数、非平凡构造函数、平凡构造函数

非平凡（non-trivial）简单来说就是在类中显式的定义了析构函数或者构造函数。
平凡就是类中没有显式的定义，式编译器调用默认的。

对默认构造函数和析构函数来说，“平凡”意味着什么也不做。
对拷贝构造函数和拷贝赋值函数来说，“平凡”意味着只做简单的内存拷贝。



参考博客

std::false_type和std::true_type

用于编程时的类型萃取（type traits）。它的作用是表示某个条件为真的情况，通常与模板编程一起使用，用于在编译期间进行条件判断。

# 判断类型是不会非平凡的
std::is_trivially_destructible<typename iterator_traits<ForwardIter>::value_type>{}

destroy_cat(first, last, std::is_trivially_destructible<
                    typename iterator_traits<ForwardIter>::value_type>{});
template <class ForwardIter>
void destroy_cat(ForwardIter, ForwardIter, std::true_type) {}

template <class ForwardIter>
void destroy_cat(ForwardIter first, ForwardIter last, std::false_type)
{
    for (; first != last; ++first)
        destroy(&*first);
}

计算迭代器间的距离

分 input_iterator_tag 和 random_access_iterator_tag 的版本

// distance 的 input_iterator_tag 的版本
template <class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance_dispatch(InputIterator first, InputIterator last, input_iterator_tag)
{
  typename iterator_traits<InputIterator>::difference_type n = 0;
  while (first != last)
  {
    ++first;
    ++n;
  }
  return n;
}

// distance 的 random_access_iterator_tag 的版本
template <class RandomIter>
typename iterator_traits<RandomIter>::difference_type
distance_dispatch(RandomIter first, RandomIter last,
                  random_access_iterator_tag)
{
  return last - first;
}

萃取器萃取过程

如果是原生指针 T 或者 const T 就用偏特化版本

// 萃取迭代器的特性
template <class Iterator>
struct iterator_traits
    : public iterator_traits_helper<Iterator, has_iterator_cat<Iterator>::value> {};   // 根据迭代器是否有 iterator_category 选择不同函数

// 针对原生指针的偏特化版本
template <class T>
struct iterator_traits<T*>
{
    typedef random_access_iterator_tag             iterator_category;
    typedef T                                      value_type;
    typedef T*                                     pointer;
    typedef T&                                     reference;
    typedef ptrdiff_t                              difference_type;   
};

// 针对 const * 的偏特化
template <class T>
struct iterator_traits<const T*>
{
    typedef random_access_iterator_tag          iterator_category;
    typedef T                                   value_type;
    typedef const T*                            pointer;
    typedef const T&                            reference;
    typedef ptrdiff_t                           difference_type;                                  
};

如果是普通的类的就是，进入iterator_traits_helper<Iterator, has_iterator_cat<Iterator>::value> {},判断是否有iterator_category属性。

template <class Iterator, bool>
struct iterator_traits_helper {};

template <class Iterator>
struct iterator_traits_helper<Iterator, true>
    : public iterator_traits_impl<Iterator,
    /*
    如果 Iterator::iterator_category 能转换为 input_iterator_tag 
    或者 Iterator::iterator_category 能转换为 output_iterator_tag
    就继承自 iterator_traits_impl<Iterator, true>
    因为 迭代器的5个属性中，有3个属于继承的，所以只要判断这两个就可以判断是否有 iterator_category 了、
    has_iterator_cat 判断是否有 iterator_category，这个判断 iterator_category 是不是这 5 个
  */
    std::is_convertible<typename Iterator::iterator_category, input_iterator_tag>::value ||
    std::is_convertible<typename Iterator::iterator_category, output_iterator_tag>::value>       // 如果 Iterator::iterator_category 能转化为 output_iterator_tag 返回一个true
{
};

如果有就进入iterator_traits_impl<Iterator, true>，返回该迭代器类中定义的属性就好了。

template <class Iterator, bool>
struct iterator_traits_impl {};

template <class Iterator>
struct iterator_traits_impl<Iterator, true>
{
    typedef typename Iterator::iterator_category iterator_category;
    typedef typename Iterator::value_type        value_type;
    typedef typename Iterator::pointer           pointer;
    typedef typename Iterator::reference         reference;
    typedef typename Iterator::difference_type   difference_type;
};

移动构造函数

在移动构造函数中，通常会执行以下操作：

• 将源对象的资源指针或资源句柄赋值给目标对象，避免深拷贝。
• 将源对象的资源指针或资源句柄置为nullptr，以确保源对象析构时不会释放资源。

移动构造语义中，一般是将源对象的指针赋值给新的对象，然后将源对象的指针赋值为nullptr，这个过程中没有内存的创建，只是资源管理权的转移。

为什么要将源对象的指针赋值为nullptr呢？

因为它是转移指针，如果不把源对象的指针设置为nullptr，那么就是相当于源对象和现在对象都指向这个资源，如果源对象销毁了调用析构函数，就会将这个资源给释放了。
也不能调用析构函数，因为也会释放这片资源。将源对象的指针设置为nullptr，这样源对象就处于有效但不再拥有资源的状态，这样如果源对象销毁时，就不会释放这片资源。

销毁元素destroy

有两种。一种是传入一个指针的，另一个是传入两个指针的一个指向开头一个指向结尾。
传入一个指针的，先利用std::is_trivially_destructible<Ty>{}判断是不是具有平凡的析构函数，然后传入对应的重载函数中。

template <class Ty>
void destroy(Ty* pointer)
{
    destroy_one(pointer, std::is_trivially_destructible<Ty>{});
}

template <class ForwardIter>
void destroy(ForwardIter first, ForwardIter last)
{
    destroy_cat(first, last, std::is_trivially_destructible<
                    typename iterator_traits<ForwardIter>::value_type>{});
}

如果是平凡的析构函数就什么也不做。平凡的啥也不用干，也干不了，因为没有占用资源（动态分配的内存，关闭文件句柄，锁等）就和int啥的一样。
你平时用int的时候也没调用析构函数吧，就类的调用了析构函数。\
如果是非凡的析构函数（就是显示定义了自己的析构函数），就调用对应的析构函数就行了。

template <class Ty>
void destroy_one(Ty*, std::true_type) {}

// 不具有平凡的析构函数（在类中显式的定义了类的析构函数）
template <class Ty>
void destroy_one(Ty* pointer, std::false_type)
{
    if (pointer != nullptr)
    {
        pointer->~Ty();
    }
}

释放一个段的，也就是遍历一边，然后一个一个调用destroy_one释放内存。

template <class ForwardIter>
void destroy_cat(ForwardIter , ForwardIter , std::true_type) {}

template <class ForwardIter>
void destroy_cat(ForwardIter first, ForwardIter last, std::false_type)
{
  for (; first != last; ++first)
    destroy(&*first);
}

vector的容量capacity

到end_是已经有元素的内存，假如我们没有capacity，end_就是最后元素的最后，我们每次加入一个新的数据，就要往后什么一个内存然后把数据放到这里吧（因为
vector是连续存储的），但是我们有没有想过：最后一个元素后面的空间是否已经被用了，如果其他地方用了，那么这就相当于覆盖了它的数据，这是十分不安全的。
那么capacity应运而生，也就是我先声明一下，从begin到capacity这都是我(vector)的，其他程序不要占用了。如果vector的元素超过了capacity,就会成倍
扩增capacity，然后找到一个适合的地址区域，将当前元素拷贝过去。

销毁元素和释放内存不一样

vector扩容时，通常先销毁元素，然后再释放内存。

重载vector移动赋值操作符

先销毁当前对象的元素，并释放当前vector的内存，并重新分配。

// 移动赋值操作符
template <class T>
vector<T>& vector<T>::operator=(vector&& rhs) noexcept
{
  destroy_and_recover(begin_, end_, cap_ - begin_);
  begin_ = rhs.begin_;
  end_ = rhs.end_;
  cap_ = rhs.cap_;
  rhs.begin_ = nullptr;
  rhs.end_ = nullptr;
  rhs.cap_ = nullptr;
  return *this;
}

支持随机访问的迭代器类型可以通过简单的减法操作来确定元素的数量

随机访问的迭代器可以直接end - first指针的方法获取元素的数量，因为空间是连续的，数据都是存在一段连续的空间中。指针本质就是地址，地址是连续的，
当然就可以通过首位地址相减获取元素数量了。这里为什么不再减去1呢，因为end那是开区间，取不到。\
但是如果不是支持随机访问的迭代器，就只能从第一个元素遍历到最后一个元素了，比如链表，因为数据不是存在一段连续的空间中，所以无法通过首尾地址相减来获取
元素的数量。

vector并没有设计自己的迭代器

vector没有设计自己的迭代器，只是个T*的指针，也就是一个普通的指针。萃取的时候，直接走的萃取器的偏特化T*版本。\
好多容器都设计了自己的迭代器类，在这个类中定义了本迭代器的属性、值类型等属性。

data_allocator::construct

也是调用的construct文件中的construct函数。

destroy() 和 deallocate() 的区别和相关性

destroy()是调用类的析构函数，相当于释放对象动态申请的内存（释放对象内的动态内存），为彻底销毁对象做准备。\
deallocate()是真正的释放内存块（释放对象所占有的动态内存），底层其实就是封装的delete函数。\
简单来讲，就是对象占一大块内存。然后在对象中new元素，就是相当于在其他的地址申请内存。\
destroy()就是相当于释放对象内动态申请的内存，deallocate()就是相当于将这个对象的这一块连续内存释放掉。如果只deallocate了对象，没有
destroy就会导致内存泄漏。我们看stl的源码，都是先destroy()然后deallocate()。\

destroy 函数：这个函数用于销毁容器中的元素，即调用元素的析构函数。在 STL 中，容器对象（如 vector、list、map 等）通常包含元素对象，而这些元素在容器销毁时需要被逐个销毁，以防止内存泄漏和资源泄漏。
destroy 函数的作用是调用元素的析构函数，确保资源得到正确释放。

deallocate 函数：这个函数用于释放分配的内存。在 STL 中，容器通常需要分配一块连续的内存来存储元素。当容器销毁时，需要释放这块内存，以防止内存泄漏。
deallocate 函数的作用是将先前分配的内存释放回内存池或系统内存管理器。

vector并没有设计自己的迭代器

vector没有设计自己的迭代器，只是个T*的指针，也就是一个普通的指针。萃取的时候，直接走的萃取器的偏特化T*版本。
好多容器都设计了自己的迭代器类，在这个类中定义了本迭代器的属性、值类型等属性。