STL空间配置器

空间配置器的核心功能就是把==对象的内存开辟和对象构造的过程分解开，对象析构和内存释放的过程分解开==，因此空间配置器主要提供了以下四个函数：

空间配置器的函数	功能
allocate	负责开辟内存
deallocate	负责释放内存
construct	负责在容器中构造对象
destroy	负责析构对象

简单的空间配置器：

// 手写空间配置器
template<typename T>
class Alloc{
public:
    T *allocate(size_t size){
        return (T*)malloc(sizeof(T) * size);
    }
    void deallocate(T* ptr, size_t size){
        free(ptr);
        // free(ptr, sizeof(T) * size);
    }
    template<typename... Args>
    void construct(T *ptr,  Args&& ...args){
        new ((void*)ptr) T(std::forward<Args>(args)...);
    }
    void destroy(T *ptr){
        ptr->~T();
    }
};

这是一种设计思想：将分配空间和构造、释放空间和析构分离，这样在容器初始化时不需要构造，只用分配空间，push时才构造。

常规的new 和 delete 都包含两阶段操作：

• 对于 new 来说，编译器会先调用 ::operator new 分配内存；然后调用 Obj::Obj() 构造对象内容。

• 对于 delete 来说，编译器会先调用 Obj::~Obj() 析构对象；然后调用 ::operator delete 释放空间。

STL allocator 决定将这两个阶段操作区分开来，分工明确。

• 对象构造由 ::construct() 负责；对象释放由 ::destroy() 负责。

• 内存配置由 alloc::allocate() 负责；内存释放由 alloc::deallocate() 负责；

如果不这样做，会出现什么问题？（参考大秦坑王博客）

• vector<A> v(10)构造容器时，不应该构造10个A对象，应该为其分配空间，A对象的构造应由用户调用。
• v.pop_back()时，应同时析构A对象。
• 出了v的作用域时，应析构v内的所有有效元素。

内存池设计思想以及两级空间配置器这里暂不讨论！

STL迭代器

traits编程技法 traits 编程技法

迭代器模式和STL中的迭代器的区别？

什么是萃取？

traits技法利⽤“内嵌型别“的编程技巧与编译器的template参数推导功能，增强C++未能提供的关于型别认证⽅⾯的能⼒。常⽤的有iterator_traits 和 type_traits。iterator_traits负责萃取迭代器的特性，type_traits负责萃取型别特性

为什么需要萃取？

本质就是通过模板的偏特化扩充value type的适用性（泛化性）

工作原理

这里提供一个简单版本的迭代器：

template<typename T>
class Iterator{
public:
    template<typename U, typename Alloc>
    friend class Vector;
    Iterator(T *ptr = nullptr):ptr_(ptr){}
    void operator++() { ++ptr_;}
    bool operator!= (const Iterator &it){
        return ptr_ != it.ptr_;
    }
    T& operator*(){ return *ptr_; }
    T* operator->() { return ptr_; }
private:
    T *ptr_;
};

如上所述，会存在上文提到的几个问题，但是面试中写出这个就够了！

面试题：push_back()以及emplace_back()区别？

我们来看源码，从源码分析是最直观的：

push_back:

/**
 * 向容器的末尾添加一个新元素。
 * 
 * 此函数通过移动语义将给定的值val添加到容器的末尾。如果容器已满，
 * 则调用resize函数来增加容器的容量。使用分配器的construct方法来
 * 在新位置构造元素，确保正确地管理资源。最后，更新元素数量的计数器。
 * 
 * @tparam Args 参数类型列表，支持完美转发。
 * @param val 要添加到容器末尾的值，可以是任意类型。
 */
void push_back(Args&& val)
{
    // 检查容器是否已满，如果满则扩大容器容量
    if(size_ == capacity_){
        makeSpace();
    }
    // 使用分配器在容器末尾构造新元素，通过转发语义保持值的原始性
    allocator_.construct(vec_ + size_, std::forward<Args>(val) );
    // 更新元素数量
    ++ size_;
}

emplace_back:

/**
 * 向向量末尾添加一个新元素，使用emplace_back直接在容器内就地构造对象。
 * 这样做的好处是避免了额外的对象拷贝或移动，从而可能提高性能。
 * 
 * @tparam Args 构造函数的参数类型列表，支持完美转发。
 * @param args 用于构造新元素的参数，通过解包传递给构造函数。
 */
void emplace_back(Args&&... args)
{
    // 如果当前容量不足，则增加容量以容纳新元素。
    if(size_ == capacity_){
        makeSpace();
    }
    // 使用分配器在向量的末尾位置构造一个新元素。
    // 这里使用了std::forward来保证参数能被正确地转发给新元素的构造函数。
    allocator_.construct(vec_ + size_, std::forward<Args>(args)...);
    // 更新元素数量。
    ++size_;
} 

几点区别：

• push_back和emplace_back在末尾插入一个已经存在的对象是没有丝毫区别的！

• emplace的方便之处在于，在原地构造对象，少了一次拷贝构造或者移动构造的开销。

  并且可以接受多个参数（源码：可变参模板、万能引用+完美转发）

面试题：resize()以及reserve()区别？

size()函数返回的是已用空间大小，capacity()返回的是总空间大小，capacity()-size()则是剩余的可用空间大小。

当size()和capacity()相等，说明vector目前的空间已被用完，如果再添加新元素，会引起vector空间的动态增长。

由于动态增长会引起重新分配内存空间、拷贝原空间、释放原空间，这些过程会降低程序效率。

因此，可以使用reserve(n)预先分配一块较大的指定大小的内存空间，这样当指定大小的内存空间未使用完时，是不会重新分配内存空间的，这样便提升了效率。

• resize()函数使用

  1、实质：resize()函数实质是改变vector中的元素个数；

  2、参数：resize()含有两个参数，resize(n,m);参数n表示vector中元素个数n,参数 m表示初始化，参数m可省略。

  resize(n,m)使用有3种情况：

  • 1、参数n<v.size()时，结果是容器v的size减小到n,删除n之后的元素；
  • 2、v.size()<参数n<v.capacity(),结果是容器v的size增加到n,增加的元素值初始化为m
  • 3、v.capacity)<参数n,结果是先增大容量capacity至n,然后初始化值，此时v中的size与capacity均发生改变。

  resize()常⽤情形

  1、需要对容器中现有元素进⾏操作时；

  2、容器初始化之后，使⽤容器时。

• **reserve()**函数使⽤

  1、实质：reserve()函数实质是改变vector的容量，即总空间的⼤小**;**

  2、参数：**reserve(n),**只含有⼀个参数，表⽰总空间的⼤小。

  reserve(n)使⽤有2种情况：

  • 1、参数n < v.capacity()时，size与capacity均不发⽣改变；
  • 2、参数**n > v.capacity()时，此时会重新分配⼀块空间，使得capacity扩容⾄n**，size不发⽣改变。

  **reserve()**常⽤情形

  • 常⽤来容器初始化，预留容器空间，以免之后多次动态改变容器空间。
  • 也可以在程序中间调⽤以扩⼤容器的空间.
  • 注意： reserve只能扩⼤容器的空间，并不能减小容器的空间

总结：

• reserve操作的是capacity(), 扩大容器的空间，并不对size造成影响
• resize操作的是size(),只有在参数大于capacity时才会扩大capacity，对size造成影响！所以push_back()也可能引发扩容。

vector<A> v;
v.resize(2);
// v.reserve(2);
v.push_back(A());
v.push_back(A());

• resize操作最后size是4，有四个A对象（两个默认构造的对象）；而reserve操作最后是2，只有两个A对象，符合预期。性能上更优先选reserve

Vector实现完整代码

#include <bits/stdc++.h>

// 手写空间配置器
template<typename T>
class Alloc{
public:
    T *allocate(size_t size){
        return (T*)malloc(sizeof(T) * size);
    }
    void deallocate(T* ptr, size_t size){
        free(ptr);
        // free(ptr, sizeof(T) * size);
    }
    template<typename... Args>
    void construct(T *ptr,  Args&& ...args){
        new ((void*)ptr) T(std::forward<Args>(args)...);
    }
    void destroy(T *ptr){
        ptr->~T();
    }
};
template<typename T>
class Iterator{
public:
    template<typename U, typename Alloc>
    friend class Vector;
    Iterator(T *ptr = nullptr):ptr_(ptr){}
    void operator++() { ++ptr_;}
    bool operator!= (const Iterator &it){
        return ptr_ != it.ptr_;
    }
    T& operator*(){ return *ptr_; }
    T* operator->() { return ptr_; }
private:
    T *ptr_;
};
template<typename T, typename allocator = Alloc<T> >
class Vector{
public:
    Vector(int size = 0)
        :size_(0), capacity_(size)
    {
        vec_ = allocator_.allocate(size);
    }
    ~Vector()
    {
        for(int i = 0; i < size_; ++i){
            allocator_.destroy(vec_ + i);
        }
        allocator_.deallocate(vec_, capacity_);
        vec_ = nullptr;
    }
    Vector(const Vector<T> &src)
        :size_(src.size_)
        , capacity_(src.capacity_)
        , allocator_(src.allocator_)
    {

        vec_ = allocator_.allocate(capacity_);
        for(int i = 0; i < size_; ++i){
            allocator_.construct(vec_ + i, src.vec_[i]);
        }
    }
    void reserve(int size){
        vec_ = allocator_.allocate(size);
        capacity_ = size;
    }
    Vector<T> operator=(const Vector<T> &src)
    {
        if(this == &src){
            return *this;
        }
        for(int i = 0; i < size_; ++i){
            allocator_.destroy(vec_ + i);
        }
        allocator_.delocate(vec_, capacity_);
        size_ = src.size_;
        capacity_ = src.capacity_;
        vec_ = allocator_.allocae(capacity_);
        for(int i = 0; i < size_; ++i){
            allocator_.construct(vec_ + i, src.vec_[i]);
        }
        return *this;
    }
    template<typename Args>
    void push_back(Args&& val)
    {
        if(size_ == capacity_){
            makeSpace();
        }
        allocator_.construct(vec_ + size_, std::forward<Args>(val) );
        ++ size_;
    }
    void pop_back()
    {
        if(size_ == 0){
            return;
        }
        --size_;
        allocator_.destroy(vec_ + size_);
    }
    template<typename... Args>
    void emplace_back(Args&&... args)
    {
        if(size_ == capacity_){
            makeSpace();
        }
        allocator_.construct(vec_ + size_, std::forward<Args>(args)...);
        ++size_;
    } 
    int size(){ return size_; }

    using iterator = Iterator<T>;
    iterator begin(){ return iterator(vec_); }
    iterator end(){ return iterator(vec_ + size_); }

private:
    T *vec_;
    int size_;
    int capacity_;
    allocator allocator_;
    void makeSpace(){
        if(capacity_ == 0){
            vec_ = allocator_.allocate(sizeof(T));
            size_ = 0;
            capacity_ = 1;
        }
        else{
            T *ptr = allocator_.allocate(capacity_ * 2);
            for(int i = 0; i < size_; ++i){
                allocator_.construct(ptr + i, vec_[i]);
            }
            for(int i = 0; i < capacity_; ++i){
                allocator_.destroy(vec_ + i);
            }
            allocator_.deallocate(vec_, capacity_);
            vec_ = ptr;
            capacity_ *= 2;
        }
    }
};