STL分析

929code / 2024-09-26 / 原文

一. 配置器

配置器（Allocator）负责为容器（如 vector、list 等）分配和释放内存，以及对象的构造和析构。
这也是为什么vector等容器不用显式的回收内存，采用的是通过类对象来创建回收资源的RALL思想

1. 类模板的使用

类模板是一种可以在声明时不指定具体类型的方式，使得类可以在多个不同类型的场景下复用。

在代码中，allocator使用了模板参数 T 来表示类型。例如：

template <class T>
class allocator
{
  // 类中的代码
};

通过template <class T>，allocator可以处理不同的数据类型，具体类型在实例化时才决定，比如 allocator<int> 会针对 int 类型分配内存。

此外，在类外定义成员函数时，仍需使用 template <class T> 再次声明，这是模板类成员函数的标准写法：

template <class T>
T* allocator<T>::allocate()
{
  return static_cast<T*>(::operator new(sizeof(T)));  // 为 T 类型分配内存
}

这样，在实例化时，可以为 T 类型的对象分配内存，类型 T 是灵活变化的。

2. 命名空间的使用

命名空间用于防止不同代码块之间的命名冲突。在你的代码中，mystl命名空间包含了allocator类，避免了与其他库中的allocator命名冲突：

namespace mystl
{
  template <class T>
  class allocator
  {
    // 内存分配器的定义
  };
}

mystl命名空间表明该分配器是属于用户自定义的，并且可以在不同的代码库中独立存在。使用时可以通过mystl::allocator来访问该类，避免与其他库中的 allocator 类混淆。

3. 可变参数模板与完美转发

可变参数模板是C++11引入的一项功能，允许模板接受不定数量的模板参数和函数参数。与传统的C语言可变参数不同，可变参数模板支持类型安全。

在代码中，allocator类使用了可变参数模板来处理构造函数的不同调用方式：

template <class... Args>
static void construct(T* ptr, Args&& ...args)
{
  mystl::construct(ptr, mystl::forward<Args>(args)...);  // 完美转发
}

template <class... Args> 定义了可以接受任意类型和数量参数的模板函数。Args&& 表示参数包，这里使用了 万能引用 来接收所有参数，包括左值和右值。

mystl::forward<Args>(args)... 通过 完美转发 保留了参数的原始类型性质（左值、右值），并将它们传递给下游的构造函数。这种方式确保了高效的参数传递，避免不必要的拷贝。

4. 四种类型的重载

allocator中的construct函数展示了四种不同的重载方式，每种重载都适用于不同的场景：

// 1. 默认构造
static void construct(T* ptr)
{
  mystl::construct(ptr);  // 调用默认构造函数
}

// 2. 拷贝构造
static void construct(T* ptr, const T& value)
{
  mystl::construct(ptr, value);  // 拷贝构造
}

// 3. 移动构造
static void construct(T* ptr, T&& value)
{
  mystl::construct(ptr, mystl::move(value));  // 移动构造
}

// 4. 可变参数构造
template <class... Args>
static void construct(T* ptr, Args&& ...args)
{
  mystl::construct(ptr, mystl::forward<Args>(args)...);  // 完美转发构造
}

5. 内存分配和释放

allocator使用 ::operator new 和 ::operator delete 来分配和释放内存。值得注意的是，前面的 :: 是作用域解析运算符，用来明确调用的是全局的 operator new 和 operator delete。

// 分配单个对象的内存
static T* allocate()
{
  return static_cast<T*>(::operator new(sizeof(T)));  // 使用全局 new 分配
}

// 分配多个对象的内存
static T* allocate(size_type n)
{
  if (n == 0) return nullptr;
  return static_cast<T*>(::operator new(n * sizeof(T)));  // 分配 n 个对象的内存
}

// 释放单个对象的内存
static void deallocate(T* ptr)
{
  if (ptr == nullptr) return;
  ::operator delete(ptr);  // 使用全局 delete 释放内存
}

这里的 ::operator new 和 ::operator delete 用于手动分配和释放原始内存（没有调用构造函数和析构函数），这与C++标准库 new 和 delete 不同，它们同时会调用构造函数和析构函数。

6. 构造与内存分配的分离：灵活与高效

在C++中，内存分配和对象构造的分离有其明确的优势，特别是在复杂的内存管理场景下：

延迟构造：通过先分配内存，再在需要时构造对象，提供了更灵活的内存和对象管理方式。例如，你可以分配一块内存但等到特定时刻才开始构造对象。
批量管理：内存分配的开销通常比构造和销毁对象大得多，将分配与构造分离允许在分配一次内存后，在该内存中多次构造和销毁对象，优化了性能。
优化资源回收：你可以销毁对象后保留分配好的内存，等待下次构造操作使用，这在内存池或容器中非常常见。它减少了频繁分配和释放内存的开销，提升了资源管理效率。

7. 析构与内存释放的分离

与构造和内存分配类似，析构对象和释放内存的分离也有重要意义：

灵活销毁：有时你可能只想销毁对象，而暂时不释放内存。例如，预先分配好一块大内存块，并在其上反复构造和销毁对象，这在内存池中非常常见。
批量释放：在某些场景中，你可能不需要一个一个地销毁对象（特别是当对象类型为 平凡析构 时），而是直接释放整块内存。通过将 destroy 和 deallocate 分开，可以选择是否显式调用析构函数。
异常安全性：析构与释放的分离允许在异常发生时，能够选择性地销毁对象，而确保内存能够被安全地回收，避免内存泄漏。

8. 定位 new（Placement new）：内存控制的关键工具

在 construct 函数中，你看到了 placement new 的使用：

::new ((void*)ptr) Ty(mystl::forward<Args>(args)...);

定位 new：placement new 是一种特殊的 new 运算符，它不分配新的内存，而是在已有的内存位置（通过指针 ptr 提供）上构造对象。
这个技术是分离内存分配与对象构造的基础，允许开发者在预先分配的内存中手动调用构造函数。

使用 placement new 的原因是它赋予了开发者精确的内存控制能力，可以在同一块内存中反复构造和销毁对象，而不涉及频繁的内存分配和释放操作。它广泛用于内存池、STL容器和自定义分配器中。

9. 平凡与非平凡析构对象的差异化处理

在 destroy 函数中，类型特征被用来区分 平凡析构 和 非平凡析构 对象：

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

平凡析构（trivially destructible）对象是指那些不需要显式调用析构函数的对象，例如基本类型（int、float）或者不含有资源管理的类。这类对象的内存可以直接释放，而无需调用析构函数。
非平凡析构对象则需要显式调用析构函数来释放资源（如指针、文件句柄等）。

通过区分这两类对象，代码在处理平凡类型时可以跳过析构步骤，提升效率。这种优化广泛应用于标准库的实现中，比如 std::vector 在处理基础类型时，就会避免不必要的析构调用。

std::is_trivially_destructible<T> 利用模板特化来判断类型 T 是否是平凡析构类型，返回 std::true_type 或 std::false_type，通过类型推导和模板实例化在编译期选择适当的函数重载，这体现了静态多态的思想。
泛型编程允许代码对任意类型进行操作，提升了代码复用性；模板特化则提供了一种机制，根据具体类型在编译期生成特定实现；类型特征（如 std::is_trivially_destructible）通过类型萃取技术，在编译期获取类型的特性，从而实现高效、类型安全的程序设计。

10. 批量销毁中的迭代器支持

在批量销毁时，代码提供了对迭代器的支持，允许你销毁一段范围内的对象：

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

迭代器：通过接受两个迭代器 first 和 last，可以销毁一段内存区域内的所有对象。
优化：同样地，使用 std::is_trivially_destructible 来判断迭代器指向的对象是否需要销毁，可以进一步优化性能。

这种设计灵活性使得 destroy 函数能够轻松处理大多数标准容器（如 std::vector、std::list）中的对象销毁操作，同时保证高效的内存管理。

二. 迭代器

迭代器的总结

在 C++ 中，迭代器是一个非常重要的概念，它们是容器与算法之间的桥梁，用来遍历容器中的元素。迭代器的设计使得同一套算法可以适用于不同类型的容器。迭代器的基本功能包括：

遍历容器中的元素：通过迭代器可以逐个访问容器中的元素。
支持前进、后退、随机访问等操作：不同类型的迭代器支持不同的操作，如输入迭代器支持读取，双向迭代器支持前进和后退，随机访问迭代器则可以直接通过索引访问元素。
兼容性：C++ 标准库中设计的各种算法（如 std::sort、std::find）都是基于迭代器实现的，支持多种容器（如 vector、list、map）的遍历。

迭代器可以分为五种类型：

输入迭代器（Input Iterator）：只能读取元素，常见于输入流。
输出迭代器（Output Iterator）：只能写入元素，常见于输出流。
前向迭代器（Forward Iterator）：可以读取、写入，并且只能前向遍历。
双向迭代器（Bidirectional Iterator）：可以前向和后退遍历。
随机访问迭代器（Random Access Iterator）：支持常数时间内的随机访问，类似于数组的指针。

实现迭代器的理解

实现迭代器的核心思想是通过类型萃取和模板技术，使得不同容器的迭代器能够提供统一的接口，便于在泛型算法中进行操作。迭代器实现的核心功能包括：

遍历容器：通过 ++、-- 操作符前进和后退，或者通过 +=、-= 在容器中移动。
访问元素：通过 * 或 -> 操作符访问迭代器当前指向的元素。
计算迭代器之间的距离：不同类型的迭代器支持不同的距离计算方式。
迭代器分类：通过 iterator_category，使算法能够区分不同的迭代器类型，并根据迭代器的能力选择最优的操作方式。

迭代器的基本接口：

iterator_traits：用于萃取迭代器的类型信息，如迭代器的类型、指针类型、引用类型、差值类型等。
advance 函数：让迭代器前进或后退特定的步数。
distance 函数：计算两个迭代器之间的距离。
reverse_iterator：实现反向迭代器，使得前进操作变为后退，后退变为前进，通常用于从后向前遍历容器。

串联用到的知识与功能实现

模板编程与泛型设计：
迭代器的实现大量依赖模板技术。通过模板编程，我们可以实现一个支持多种类型的迭代器，而无需为每种类型单独定义迭代器。模板允许迭代器对容器中的任意类型进行操作，并且在编译期确定具体的类型和操作方式。
类型萃取（Type Traits）：
iterator_traits 是类型萃取的核心，它用于从迭代器中提取类型信息，如 value_type、pointer、reference 等。这样可以让算法和迭代器分离，算法只需要知道如何通过类型萃取器获取迭代器的信息，而不需要关心迭代器的具体实现。

例如：
```
typedef typename iterator_traits<Iterator>::iterator_category iterator_category;
```
这行代码提取了 Iterator 迭代器的类型标签，让算法可以根据 iterator_category 选择合适的操作。
模板特化与静态多态：
迭代器的设计中使用了大量的模板特化，以实现针对不同迭代器类型的优化。例如，针对 random_access_iterator_tag，我们可以直接通过算术运算符计算迭代器的距离，而对其他类型的迭代器则需要逐个遍历计算。

例如，对于 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;
}
```
静态多态与编译期优化：
C++ 的模板和类型萃取机制使得迭代器的多态行为可以在 编译期 确定，而不是像传统的虚函数那样在运行时进行多态操作。这大大提升了性能，因为所有的类型判断和函数选择都在编译期间完成。
反向迭代器：
reverse_iterator 是 STL 中非常常见的迭代器类型，它通过包装正向迭代器，将前进变为后退，后退变为前进，从而实现反向遍历的功能。

例如：
```
template <class Iterator>
class reverse_iterator {
private:
  Iterator current;
public:
  reverse_iterator& operator++() {
    --current;
    return *this;
  }
  reverse_iterator& operator--() {
    ++current;
    return *this;
  }
};
```
reverse_iterator 通过重载 ++、-- 操作符改变正向迭代器的遍历方向。

结论

实现迭代器的复杂性在于如何提供一个泛型、灵活且高效的遍历接口。通过模板编程、类型萃取和模板特化，C++ 标准库成功实现了一个强大且通用的迭代器机制。每个迭代器可以根据不同容器的需求提供不同的功能，同时通过 iterator_traits 进行类型萃取，保证算法和迭代器的解耦，并且利用静态多态和编译期优化提升性能。

三. 算法

通过迭代器以及模板进行简单操作即可
也就是通过迭代器内容里面的val值，进行操作
包括常用的max_element、min_elememt、count、find、upper_bound、lower_bound、accumulate、iota、max等

四. 容器(基本数据结构)

1. vector

vector 是通过指针来管理其内部连续的内存空间，并利用这一特性来实现高效的动态数组操作。通过指针操作，vector 可以实现快速的元素访问、插入、删除、扩展和收缩等功能。以下是如何利用指针和连续内存空间的视角来串联 vector 实现的所有函数的总结。

1. 指针在内存管理中的作用

vector 内部使用三个指针：begin_、end_ 和 cap_。
- begin_：指向当前 vector 存储空间的起始位置。
- end_：指向当前使用空间的末尾（即最后一个元素的后一个位置）。
- cap_：指向 vector 已分配的存储空间的末尾。

这三个指针一起管理 vector 的内存，使得它能够有效地插入和删除元素，同时动态扩展和收缩存储空间。

2. 利用指针进行元素访问

operator[] 和 at()：通过 begin_ + n 来计算元素的地址，指针偏移实现常数时间的随机访问。
```
return *(begin_ + n);
```
这种直接通过指针偏移访问元素的方式是 vector 快速随机访问的关键。

3. 利用指针进行插入和删除

insert() 和 erase()：通过指针操作进行插入和删除。
- 插入：在指定位置 pos 插入元素时，vector 首先通过指针定位到 pos 的位置，然后将 pos 之后的元素依次向后移动（通过 memmove 实现），腾出空间插入新元素。
- 删除：删除元素时，vector 通过指针操作将 pos 之后的元素向前移动，覆盖被删除的元素。
```
mystl::move(xpos + 1, end_, xpos);  // 将[pos + 1, end_)区间的元素前移
```

这种通过指针移动数据的方式非常高效，尤其是在处理大块数据时。

4. 利用指针进行动态扩展

扩容机制：当 vector 空间不足时，它会通过指针重新分配内存。vector 使用 get_new_cap() 函数计算新的容量，并通过指针 uninitialized_move() 将旧内存中的元素移动到新分配的空间中，随后释放旧的内存。
```
auto new_begin = data_allocator::allocate(new_size);
mystl::uninitialized_move(begin_, end_, new_begin);  // 将旧内存的数据移动到新内存
```
这个过程的核心是通过指针操作将内存块进行搬移，尽可能减少复制操作，提高效率。

5. 利用指针快速访问容器的头尾

front() 和 back()：通过 begin_ 和 end_ - 1 返回首尾元素的引用。由于 vector 的存储空间是连续的，直接通过指针访问头尾元素非常高效。
```
return *begin_;  // front
return *(end_ - 1);  // back
```

6. 利用连续内存提高遍历效率

迭代器遍历：vector 的迭代器本质上就是一个指向元素的指针，遍历时可以通过简单的指针递增来实现高效遍历。由于 vector 的存储空间是连续的，所以指针的递增操作非常快。
```
for (auto it = begin_; it != end_; ++it)
{
  // 直接通过指针遍历
}
```

7. 容器大小管理

size() 和 capacity()：通过指针运算计算当前 vector 的大小和容量：

size_type size() const noexcept { return static_cast<size_type>(end_ - begin_); }
size_type capacity() const noexcept { return static_cast<size_type>(cap_ - begin_); }

这种通过指针相减的方式能够快速计算当前元素个数和可用容量。

8. 内存回收与释放

destroy_and_recover()：在释放 vector 时，通过指针遍历当前内存区域，并逐个调用析构函数销毁元素，最后释放整个内存块。
```
data_allocator::destroy(first, last);  // 销毁[first, last)之间的对象
data_allocator::deallocate(first, n);  // 释放内存
```