内存分配器的作用与实现

allocate内存分配器是STL中的一个核心组件，负责容器的内存管理（分配、释放、对象构造与析构），是容器与内存之间的抽象层，有了内存分配器，容器可以独立于具体的内存管理策略。

在特殊的场景下，可以重写内存分配器allocate，但是一般都不会，因为标准库的毕竟更完善，效率更高（大家可以针对自己场景自己判断）。

1. 内存分配与释放

为容器元素分配原始内存（此时并未构造，只是分配内存），返回分配地址空间的指针，具体的实现方式就是调用全局 operator new操作符，分配一块大小为n的地址空间

    /// 分配内存空间
    pointer allocate(size_type n) {
        /// 调用全局operator new操作符
        return static_cast<pointer>(::operator new(n * sizeof(T)));
    }

	/// 调用上方这个版本
    pointer allocate(size_type n, const void *) {
        return allocate(n);
    }

释放内存空间的实现方式是调用全局 operator delete，删除对应的空间地址，如下

  /// 销毁内存空间
    void deallocate(pointer p, size_type n) {
        ::operator delete(p);
    }

2. 构造对象与析构对象

构造对象时采用在已经分配的内存空间上调用构造函数构造对象，以及调用析构函数销毁对象。

这里使用placement new，不会分配内存，只负责调用构造函数，并且static_cast<void*>*(P)让编译器直到这个地址是合法地址，防止类型转换的警告，构造时使用可变参模板实现。

在析构对象时则显示调用析构函数即可，

/// 调用构造函数，利用可变参数模板，在这块内存空间中，构造可变数量的对象
    template<typename U, typename...Args>
    void construct(U *p, Args &&... args) {
        /// U(...)：调用目标对象类型 U 的构造函数
        ::new(static_cast<void *>(p))U(std::forward<Args>(args)...);
    }

    void destroy(pointer p) {
        /// 显式调用析构函数
        p->~T();
    }

    /// 将刚刚构造的可变参数列表的对象释放掉
    template<typename U>
    void destroy(U *p) {
        p->~U();
    }

3. 常见的接口

除了上面四个最重要的接口之外，还提供了获取内存空间真实地址的接口 address、max_size以及rebind模板，使得支持转换为其他类型的 allocator

	pointer address(reference x) const noexcept {
        /// 返回真实的地址
        return std::addressof(x);
    }

    const_pointer address(const_reference x) const noexcept {
        return std::addressof(x);
    }

	/// rebind 模板（使得支持转换为其他类型的 allocator）
    template<typename U>
    struct rebind {
        using other = MyAlloc<U>;
    };

4. 比较运算符

在 STL中，强制要求提供比较运算符号，起核心作用是验证内存操作的安全性，其中 operator==用于判断两个分配器是否属于同构内存池（可以安全的交叉释放彼此分配的内存），operator !=逻辑正好相反。

一般的应用场景包括：

• 当容器复制或者移动时，需要检查源容器和目标容器的分配是否兼容；
• 在内存释放时（deallocate)，需要对传入的指针验证是否由当前分配器分配；
• 在容器进行合并或者拼接过程中，例如list::splice，需要确保两个容器的分配可以共享内存

template<typename T, typename U>
bool operator==(const MyAlloc<T> &, const MyAlloc<U> &) {
    return true;
}

template<typename T, typename U>
bool operator!=(const MyAlloc<T> &, const MyAlloc<U> &) {
    return false;
}

以上表明所有的MyAlloc实例（无论类型参数 T 和 U 是否相同）都被视为兼容，表示这个分配器管理的是全局共享的内存池。

type_traits

在STL中，type_traits也是一个非常重要的头文件<type_traits>，提供了一系列模板和函数，可以在编译时查询、判断和转换类型信息

核心作用

主要用于在编译期间获取类型的各种属性（如指针、是否为整数类型等）；还可以基于类型属性进行条件判断和选择性编译；也可以实现对类型进行转换（添加/移除const 限定符等）

工作原理

主要是基于模板和SFINAE原则，模板在实例化过程中，如果遇到无法解析的情况，不会将其视为错误，而是尝试其他模板特化或重载解析。

我们可以根据代码就可以很直接看出作用了，这里贴出我自己复现的enable_if ：如果判断条件 cond 为真，则类型为T否则为默认

// enable_if
// 默认版本
template <bool cond, typename T = void>
struct enable_if{};

// 特化版本,满足条件时 定义type = T
template<typename T>
struct enable_if<true, T>{
    using type = T;
};

// 辅助别名模板
template<bool cond, typename T = void>
using enable_if_t = typename enable_if<cond, T>::type;

is_same :即两个类型一致，则value为true，否则为false

// is_same --->  默认两个模板类型是T  U,如果两个都是T，则true
template <typename T, typename U>
struct is_same{
    static constexpr bool value = false;
};

// 满足条件则返回true
template <typename T>
struct is_same<T, T>{
    static constexpr bool value = true;
};

conditional:类似于三目运算符，默认true为第一个值

// condition-->类似于三目运算符
template <bool cond, typename T, typename U>
struct conditional{
    // 三目运算 默认为true 等于第一个值
    using type = T;
};

template <typename T, typename U>
struct conditional<false, T, U>{
    using type = U;
};

// 辅助别名模板
template<bool cond, typename T, typename U>
using conditional_t = typename conditional<cond, T, U>::type;

SFINAE

SFINAE 是 “Substitution Failure Is Not An Error”（替换失败不是错误）的缩写，是C++模板编程中的一个重要概念。它允许编译器在模板实例化过程中，如果在替换模板参数时失败（即不满足某些条件），不会将其视为编译错误，而是继续寻找其他可能的模板或重载。

工作原理

在模板实例化过程中，编译器会尝试将模板参数替换为具体类型。如果替换过程中出现不合法的表达式或者类型，编译器不会报错，而是将该模板视为不可行的，继续尝试其他模板。

应用场景以及用法

1. 函数重载选择

可以根据参数类型的不同选择不同的函数重载，例如下面这个例子

#include <type_traits>
#include <iostream>

/**
 template <typename _Tp>
  inline constexpr bool is_void_v = is_void<_Tp>::value;
template <typename _Tp>
  inline constexpr bool is_null_pointer_v = is_null_pointer<_Tp>::value;
template <typename _Tp>
  inline constexpr bool is_integral_v = is_integral<_Tp>::value;
template <typename _Tp>
  inline constexpr bool is_floating_point_v = is_floating_point<_Tp>::value;
 * */

// 适用于int类型
template<typename T>
typename  std::enable_if<std::is_integral<T>::value, void>::type
printType(T val)   // 这个函数的返回类型就是上面std::enable_if决定的类型
{
    std::cout << "this is int type_param, val is " << val << std::endl;
}

// 适用于float类型
template<typename T>
typename  std::enable_if<std::is_floating_point<T>::value, void>::type
printType(T val)   // 这个函数的返回类型就是上面std::enable_if决定的类型
{
    std::cout << "this is float type_param, val is " << val << std::endl;
}


int main()
{
    printType(1);// this is int type_param, val is 1
    printType(2.2); // this is float type_param, val is 2.2

    return 0;
}

2. 类型特性检测

检测类型中是否具有某些成员或者特性，从而去决定是否启用某些功能

#include <type_traits>
#include <iostream>

// 检测类型中是否含有特定的成员
// 经典的 SFINAE（Substitution Failure Is Not An Error）技巧，
// 用于在编译期检测某个类型是否具有特定的成员函数
template<typename T>
class has_foo  // has_foo 是一个类型萃取类，用于检测类型 T 是否具有成员函数 foo
{
private:
    // 这里定义两个数组，用于接收函数重载的选择结果，用于判断条件真假
    typedef char yes[1];
    typedef char no[2];

    // 模板结构体，用于匹配&U::foo的时候发生替换，如果U没有名为foo的void()成员函数
    // 则匹配失败（即 SFINAE 触发），此模板无法实例化
    template<typename U, void (U::*)()>
    struct SFINAE{};

    // 检测函数重载
    // 如果U有成员函数void foo()，则&U::foo是合法的函数指针，那么SFINAE<U, &U::foo>能匹配成功
    template<typename U>
    // 返回yes表明找到了foo
    static yes& test(SFINAE<U, &U::foo>*);

    // 如果前面那个不匹配，就用这个模板
    // 返回 no&，表示“没有找到 foo”
    template <typename U>
    static no& test(...);
public:
    /**
     * 1、编译时调用test<T>(0),根据函数重载解析选择返回值
     * 2、如果返回yes&，说明有foo成员函数， value == true
     * 3、返回no&，说明没有foo成员函数， value = false
     * */
    static constexpr bool value = sizeof(test<T>(0)) == sizeof(yes);
};

// 函数仅在T有 foo()成员时启用
template <typename T>
typename std::enable_if<has_foo<T>::value, void>::type
call_fool(T& obj) {  // call_foo 函数模板仅在 T 具有 foo 成员时启用
    obj.foo();
    std::cout << "foo() called." <<std::endl;
}

class WithFoo{
public:
        void foo()
        {
            std::cout << "WithFoo::foo()" << std::endl;
        }
    };

class WithOutFoo  // 对于不具有 foo 成员的类型，编译器会忽略 call_foo，从而避免编译错误
{};

int main()
{

    WithFoo wf;
    WithOutFoo wof;
    call_fool(wf);
    //WithFoo::foo()
    //foo() called.
//    call_fool(wof);  // 没有匹配的函数
    return 0;
}

3. 条件编译

根据模板参数的特性决定是否编译某些代码段，通过模板特化实现不同的行为

首先定义一个 Trait用于检测T 是否有非void 的 value_type即：

Trait has_non_void_value_type：

• 主模板： 默认情况下，has_non_void_value_type<T>继承自std::false_type，表示T没有value_type或value_type为void
• 特化模板： 仅当T有value_type且value_type不是void时，has_non_void_value_type<T>继承自std::true_type

template <typename T, typename  = void>
struct has_non_void_value_type : std::false_type {};

// 仅当 T 有 `value_type` 且 `value_type` 不是 void 时，特化为 std::true_type
template <typename T>
struct has_non_void_value_type<T,
        std::enable_if_t<!std::is_void_v<typename T::value_type>>> : std::true_type {};

然后定义 TypePrinter 主模板，使用一个布尔参数控制特化

• 主模板： 接受一个类型T和一个布尔模板参数 HasValueType,默认为 has_non_void_type<T>::value
• 特化模板： TypePrinter<T, true>,当HasValueType为true时表明T有非void的value_type，提供相应的print实现
• 特化模板： TypePrinter<T, false>,当HasValueType为false时表明T没有value_type或者value_type为void,提供默认的print实现

// TypePrinter通用模板
template <typename T, bool HasValueType = has_non_void_value_type<T>::value>
struct TypePrinter;
// 3. 特化：当 HasValueType 为 true 时，表示 T 有非 void 的 `value_type`
template <typename T>
struct TypePrinter<T, true>{
    static void print()
    {
        std::cout << "T has a member type 'value_type'." << std::endl;
    }
};
// 特化：当 HasValueType 为 false 时，表示 T 没有 `value_type` 或 `value_type` 是 void
template <typename T>
struct TypePrinter<T, false>{
    static void print()
    {
        std::cout << "T doesn't have a member type 'value_type'." << std::endl;
    }
};

接下来给出测试结构体

• WithValueType:有一个非void的value_type

• WithoutValueType:没有value_type
• WithVoidType:有一个value_type,但它是void

struct WithValueType{
    using value_type = int;
};

struct WithoutValueType{};

struct WithVoidType{
    using value_type = void;
};

测试结果

int main()
{
    // 分别测试三种不同的情况
    TypePrinter<WithValueType>::print();
    TypePrinter<WithoutValueType>::print();
    TypePrinter<WithVoidType>::print();
    /**
            T has a member type 'value_type'.
            T doesn't have a member type 'value_type'.
            T doesn't have a member type 'value_type'.
     * */
    return 0;
}

SFINAE优缺点

优点

1. 非常灵活，可以根据类型选择不同的实现
2. 在编译期检测，减少了运行时错误

缺点

复杂，不太好写，并且如果报错了的话，有的bug还是不太好调的（估计是因为本人技术水平有限）

现代C++替换方案

概念 Concept

在c++20中使用概念 (concept)替换SFINAE，更加简洁直观，减少复杂性。

使用概念 concept来代替std::enable_if，语法更简单，更易读；当类型不满足概念时，编译器会给出明确的语法错误信息，便于调试。

例如下面的例子：

#include <iostream>
#include <concepts>

template <typename T>
concept Interger = std::is_integral_v<T>;   // 如果类型满足限定条件则概念有效

template <Interger T>
void print_type(T value)
{
    std::cout << "this is Interger " << value << std::endl;
}

int main()
{
    print_type(3);  // 输入了满足要求的类型
    // this is Interger 3
    print_type(3.1);  
    /**
    此时输入double，不满足条件，会报错，但是跟SPFNAE比起来有明确报错提示
    例如：
    D:/coding/cpp_trainning/TypePrinter.cpp:97:15: error: no matching function for call to 'print_type(double)'
   97 |     print_type(3.1);
      |     ~~~~~~~~~~^~~~~
D:/coding/cpp_trainning/TypePrinter.cpp:89:6: note: candidate: 'template<class T>  requires  Interger<T> void print_type(T)'
   89 | void print_type(T value)
      |      ^~~~~~~~~~
D:/coding/cpp_trainning/TypePrinter.cpp:89:6: note:   template argument deduction/substitution failed:
D:/coding/cpp_trainning/TypePrinter.cpp:89:6: note: constraints not satisfied
D:/coding/cpp_trainning/TypePrinter.cpp: In substitution of 'template<class T>  requires  Interger<T> void print_type(T) [with T = double]':
D:/coding/cpp_trainning/TypePrinter.cpp:97:15:   required from here
   97 |     print_type(3.1);
      |     ~~~~~~~~~~^~~~~
D:/coding/cpp_trainning/TypePrinter.cpp:86:9:   required for the satisfaction of 'Interger<T>' [with T = double]
D:/coding/cpp_trainning/TypePrinter.cpp:86:25: note: the expression 'is_integral_v<T> [with T = double]' evaluated to 'false'
   86 | concept Interger = std::is_integral_v<T>;   // 如果类型满足限定条件则概念有效
      |                    ~~~~~^~~~~~~~~~~~~~~~
ninja: build stopped: subcommand failed.
    */ 

可以看到，给出明显的错误信息。

类型特性检测

针对用类型特性检测：检测类型是否具有某些成员或特性，从而决定是否启用某些功能概念方法重写

#include <concepts>
#include <type_traits>
#include <iostream>

// 定义一个概念，要求类型 T 具有 void foo()
template <typename T>
// HasFoo含义是：类型 T 必须具有成员函数 foo()，并且这个函数必须无参且返回 void
concept HasFoo = requires(T t) {
    { t.foo() } -> std::same_as<void>;
};

// 仅当 T 满足 HasFoo 概念时启用
// 本质上是一个编译期布尔值表达式  constexptr bool  HasFool<T> = ...
template <HasFoo T>
void call_foo(T& obj) {
    obj.foo();
    std::cout << "foo() called." << std::endl;
}

class WithFoo {
public:
    void foo() { std::cout << "WithFoo::foo()" << std::endl; }
};

class WithoutFoo {};

int main() {
    WithFoo wf;
    call_foo(wf);
    // 输出: WithFoo::foo()
    //      foo() called.

    // WithoutFoo wf2;
    // call_foo(wf2); // 编译错误，不满足 HasFoo 概念
    return 0;
}

迭代器

迭代器是容器与算法之间的桥梁，语法与指针相似，用于遍历容器中的元素，提供了一个统一的接口来访问容器中的元素，而不需要关注容器的实现

定义

迭代器的定义有三种不同的概念

1. 迭代器这个概念本身
   某个类型是迭代器当且仅当它支持一套操作，可以让我们访问容器的元素或者从某一个元素移动到另一个元素。
2. 容器中定义的迭代器类型
   每一个容器类都会定义一个迭代器，支持一套操作，比如vector，string等
3. 指某一个迭代器对象

类别

迭代器一般有5类，分别是
输入迭代器：支持读取元素，但是只能单向递增
输出迭代器：支持写入元素，也只能单向递增
前向迭代器：支持读取和写入元素，只能单向递增，支持多次遍历
双向迭代器：支持读取和写入元素，在前向迭代器基础上增加了递减操作（--it)
随机访问迭代器：支持读取和写入元素，可以随机访问(it + n)

迭代器使用

迭代器一般提供了多个操作接口，可以按照相应的接口操作容器中的元素，比如解引用（*）、前向自增/自减，后向自增/自减等

• 解引用，使用*访问迭代器指向的元素
• 递增，使用++将迭代器移动到下一个元素
• 递减，使用--操作符移动到上一个元素（仅适用于双向迭代器和随机访问迭代器）
• 比较 == ！=

使用迭代器可以遍历常见的容器，迭代器一般使用begin()获取容器第一个元素的迭代器，使用end()获取末尾元素的后一个位置的迭代器，所以迭代器的使用方法中，元素的范围是在[begin,end)，end()被称为尾迭代器。
如果容器为空，begin()==end()

1. it.begin()，it.end()表示常规迭代器，可以访问和修改其中的元素
2. it.cbegin()，it.cend() 这两个都是const_iterator()表示常量迭代器，仅仅支持访问容器中的元素，不支持修改
3. it.rbegin()，it.rend()这是reverse_iterator()表示逆序迭代器，即从末尾开始，一般只有双向迭代器或随机访问迭代器才有

迭代器失效

当容器的结构发生变化时，如插入、删除、扩容等操作时，之前获取的迭代器就会失效，需要重新获取，常见的两种情况就是：

• 在循环中对容器进行添加元素会导致迭代器失效
• 改变容器的结构
  这里给出不同容器的迭代器失效的情形对比

容器类型	插入元素时	删除元素时	清空容器后
std::vector	插入导致扩容 ⇒ 所有迭代器失效,尾部插入不扩容 ⇒ 不失效	删除后面元素 ⇒ 后面迭代器失效	所有迭代器失效
std::list	不失效（双向链表）	删除的元素迭代器失效，其余不变	所有迭代器失效
std::deque	插入/删除任意位置 ⇒ 迭代器可能失效	有时部分失效	所有失效
std::map/std::set	插入 ⇒ 不失效	删除 ⇒ 删除元素对应迭代器失效	删除元素迭代器失效，其它不变
std::unordered_map/std::unordered_set	插入/删除 ⇒ 可能会失效（哈希表重排）	同上	所有失效

这里举一个例子：

std::vector<int> vec = {1, 2, 3, 4, 5};
for (auto it = vec.begin(); it != vec.end(); ++it) {
    if (*it == 3) {
        vec.erase(it);  /// 删除后 it 失效，++it 就是未定义行为
    }
}

迭代器源码实现

我自己参考STL手写了一个迭代器，大家感兴趣的可以查看，也可以自己手写

/**
 * 自定义一个随机访问迭代器，支持所有迭代器支持的操作
 * */
#pragma once

#include <cstddef>  /// for std::ptrdiff_t
#include <iterator>

template <typename T>
class MyIterator
{
public:
    using iterator_category = std::random_access_iterator_tag;          /// 代表随机访问迭代器
    using value_type        = T;                                        /// 数据类型
    using difference_type   = std::ptrdiff_t;
    using pointer           = T*;                                       /// 指针
    using reference         = T&;                                       /// 引用

    /// 构造函数
    MyIterator()
        : data_(nullptr)
    {}

    /// 单参数构造函数--->explicit
    explicit MyIterator(T* p)
        : data_(p)
    {}

    /// 拷贝构造
    MyIterator(const MyIterator&) = default;
    MyIterator& operator=(const MyIterator&) = default;

    /// 移动构造
    MyIterator(MyIterator&& other) noexcept
        : data_(other.data_)
    {
        other.data_ = nullptr;
    }

    MyIterator& operator=(MyIterator&& other) noexcept
    {
        if (this != &other) {
            delete data_;
            data_ = other.data_;

            other.data_ = nullptr;
        }
        return *this;
    }

    /// 析构函数
    ~MyIterator() = default;

    /// 解引用
    reference operator*() const
    {
        return *data_;
    }

    pointer operator->() const
    {
        return data_;
    }

    /// 前置递增递减
    MyIterator& operator++()
    {
        ++data_;
        return *this;
    }

    MyIterator& operator--()
    {
        --data_;
        return *this;
    }

    /// 后置递增递减
    MyIterator& operator++(int)
    {
        MyIterator temp = *this;
        ++data_;
        return temp;
    }

    MyIterator& operator--(int)
    {
        MyIterator temp = *this;
        --data_;
        return temp;
    }

    /// 算术运算
    MyIterator operator+(difference_type n) const
    {
        return MyIterator(data_ + n);
    }

    MyIterator operator-(difference_type n) const
    {
        return MyIterator(data_ - n);
    }

    MyIterator& operator+=(difference_type n) const
    {
        data_ += n;
        return *this;
    }

    MyIterator& operator-=(difference_type n) const
    {
        data_ = n;
        return *this;
    }

    /// 迭代器差
    difference_type operator-(const MyIterator& other) const
    {
        return data_ - other.data_;
    }

    /// 下标访问
    reference operator[](difference_type n) const
    {
        return data_[n];
    }

    /// 比较运算符
    bool operator==(const MyIterator& other) const
    {
        return data_ == other.data_;
    }

    bool operator!=(const MyIterator& other) const
    {
        return data_ != other.data_;
    }

    bool operator>(const MyIterator& other) const
    {
        return data_ > other.data_;
    }

    bool operator<(const MyIterator& other) const
    {
        return data_ <other.data_;
    }

    bool operator<=(const MyIterator& other) const
    {
        return data_ <= other.data_;
    }

    bool operator>=(const MyIterator& other) const
    {
        return data_ >= other.data_;
    }

private:
    T* data_;               /// T*数据，如果其中有复杂资源，可以支持重新在stl中自定义并且在拷贝构造或者移动构造中添加相关的操作
};

/// 支持n+iterator
template<typename T>
MyIterator<T> operator+(typename MyIterator<T>::difference_type n, const MyIterator<T>& it)
{
    return it + n;
}

测试

我这里结合了自定义的内存分配器与迭代器，写了一个小例子测试代码的功能逻辑是否正确，如下

int main() {
    std::vector<int, MyAlloc<int>> v = {10, 20, 30, 40};

    MyIterator<int> begin(v.data());
    MyIterator<int> end(v.data() + v.size());

    for (auto it = begin; it != end; ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";

    std::cout << "Second element: " << begin[1] << "\n";
    std::cout << "Distance: " << end - begin << "\n";

    auto it2 = begin + 2;
    std::cout << "*it2: " << *it2 << "\n";
    return 0;
}

运行所得到的结果

    /**
        [MyAlloc] Allocating 4 element(s)
        [MyAlloc] Constructing
        [MyAlloc] Constructing
        [MyAlloc] Constructing
        [MyAlloc] Constructing
        10 20 30 40
        Second element: 20
        Distance: 4
        *it2: 30
        [MyAlloc] Destroying element
        [MyAlloc] Destroying element
        [MyAlloc] Destroying element
        [MyAlloc] Destroying element
        [MyAlloc] Deallocating 4 element(s)
     * */

可见迭代器与内存分配器的功能基础正确。

迭代器的使用场景

二分搜索算法使用迭代器非常方便，即

std::vector<int> numbers = {1, 2, 3, 4, 5};
//二分查找4所在的迭代器为止
auto beg = nums.begin();
auto end = nums.end();
auto mid = beg + (end - beg) / 2;
while (mid != end && *mid != 4) {
    if (*mid < 4) {
        beg = mid + 1;
    } else {
        end = mid;
    }
}
if (mid != end) {
    std::cout << "4 is found" << std::endl;
} else {
    std::cout << "4 is not found" << std::endl;
}