CPP基础|简单实现vector

引言

其实就是数据结构复健,调库调多了,自知内功越来越差.巩固巩固基础.~~既是给博客灌水文充充数量~~

vector实现步骤

vector的数组内存通常是在堆上分配,而创建vector对象时,及控制数组内存上 , 指向数据的指针、大小和容量等）通常存储在栈上（如果是局部变量）或其他存储区（如全局/静态存储区），但实际的元素数据是在堆上分配的。

先从简单的入手构造析构函数入手

template <typename T>
class MyVector{
private:
    T *elements;     
    size_t capacity; 
    size_t size;     
public:
    MyVector(): elements(nullptr), capacity(0), size(0){}
    ~MyVector()
    {
        delete[] elements;
    }
    MyVector(const MyVector& v):capacity(v.capacity), size(v.size)
    {
       elements = new T[capacity];
       std::copy(v.elements, v.elements + size, elements);
     }
    MyVector operator=(const MyVector& v)
    {
    if (this != &other) 
        {
            delete[] elements;
            capacity = other.capacity;
            size = other.size;
            elements = new T[capacity];
            std::copy(other.elements, other.elements + size, elements);
        }
        return *this;
    }
}

老三样无参,拷贝,赋值构造.其中的CPP语法知识点也就初始化列表, 没什么特别的.

std::copy的用法是一个标准库算法，通常用于从一个容器复制元素到另一个容器。std::copy需要三个参数：两个指定要复制的元素范围的迭代器（起始迭代器和结束迭代器），以及一个指向目标位置开始的迭代器。指针也是一种天然的迭代器

那么简单的vector对象已经做出来了主干部分,接下来就是为主干添加对外的功能接口.

首先需要考虑的就是对数组空间的管理,这里简单写了个增量拓展,没有做异常处理

void reserve(size_t newCapacity)
    {
        if (newCapacity > capacity)
        {
            T *newElements = new T[newCapacity];
            std::copy(elements, elements + size, newElements);
            delete[] elements;
            elements = newElements;
            capacity = newCapacity;
        }
    }

实际上的vector本质上就是一个对连续内存进行管理的容器,根据需要拓宽内存容量,后续的操作都围绕增删改查展开.

  // 访问数组中的元素
    T &operator[](size_t index)
    {
        // 检查索引是否越界
        if (index >= size)
        {
            throw std::out_of_range("Index out of range");
        }
        return elements[index];
    }

    // const版本的访问数组中的元素
    const T &operator[](size_t index) const
    {
        // 检查索引是否越界
        if (index >= size)
        {
            throw std::out_of_range("Index out of range");
        }
        return elements[index];
    }
  // 在指定位置插入元素
    void insert(size_t index, const T &value)
    {
        if (index > size)
        {
            throw std::out_of_range("Index out of range");
        }
        if (size == capacity)
        {
            reserve(capacity == 0 ? 1 : capacity * 2);
        }
        for (size_t i = size; i > index; --i)
        {
            elements[i] = elements[i - 1];
        }
        elements[index] = value;
        ++size;
    }

    // 删除数组末尾的元素 实际上内存并没有释放
    void pop_back()
    {
        if (size > 0)
        {
            --size;
        }
    }
   void clear() 
   {
    size = 0;
    }

当然了,也需要给外部提供一个迭代器相关接口

T* begin() {
    return elements;
}

T* end() {
    return elements + size;
}

const T* begin() const {
    return elements;
}

const T* end() const {
    return elements + size;
}

至此,一个简单的vector 就实现了.

模拟了一些 std::vector 的基本行为,没有涵盖 std::vector 的所有功能和特性.

内存管理策略对比 std::vector 每次插入元素时都可能触发内存重新分配. std::vector 会提供范围检查、异常处理等。它会在越界访问等错误情况下提供保护.MyVector 类并未实现这些安全性检查，因此在特定条件下可能导致未定义行为。

Q&A

由此vector的简单实现,可以延申出面试相关问题

1. `std::vector`的扩容过程

当向 std::vector 添加元素并且当前容量不足以容纳新元素时，std::vector 会进行扩容。这通常涉及以下步骤：

分配一个更大的内存块，通常是当前大小的两倍（这个增长因子取决于实现）。
将当前所有元素移到新分配的内存中。
销毁旧元素，并释放旧内存块。
插入新元素。

这个过程中的复制和移动操作可能会导致性能开销，尤其当元素具有复杂的拷贝构造函数或移动构造函数时。

2. 解释 `std::vector::push_back` 和 `std::vector::emplace_back` 的区别。

std::vector::push_back 和 std::vector::emplace_back 都是在 std::vector 的末尾添加一个新元素，但它们添加元素的方式不同。

push_back 会对给定的对象进行拷贝或移动构造，以将元素添加到 vector 的末尾。
emplace_back 则使用给定的参数直接在 vector 的末尾构造一个元素，无需拷贝或移动操作，这通常更高效。

3. 什么时候会使用 `std::vector::reserve()`？

std::vector::reserve() 用于预分配内存，以避免在添加新元素时重新分配内存。当知道将要存储大量元素，但又不想在每次插入时都可能发生内存重新分配时，使用 reserve() 可以提高性能。这样可以减少因扩容导致的不必要的内存分配和元素拷贝。

4. 如何减少 `std::vector` 占用的空间？

可以使用 std::vector::shrink_to_fit 方法来请求移除未使用的容量，减少 vector 的内存使用。这个函数是 C++11 引入的，它会尝试压缩 std::vector 的容量，使其等于其大小。但是，这只是一个请求，并不保证容量会减少，因为这依赖于实现。

5. 如何检查 `std::vector` 是否为空？

使用 std::vector::empty() 方法可以检查 vector 是否没有元素。这比使用 size() 方法（比较 size() == 0）更首选，因为 empty() 通常可以保证是常数时间复杂度的操作。

6. 什么是迭代器失效? 如何避免?

当 vector 进行操作，如增加或删除元素，尤其是在中间插入或删除元素时，迭代器可能会失效。例如：

如果 vector 进行了重新分配，所有指向元素的迭代器都会失效。
如果在 vector 中间插入或删除元素，从该点到末尾的所有迭代器都会失效。

解决方案是最好使用标准库提供的算法，如 std::remove 和 std::remove_if 结合 vector::erase 方法来删除元素。这些算法在设计时已经考虑了迭代器失效的问题。

7. 如果 `std::vector` 的元素是指针，需要注意什么？

当 vector 的元素是指针对 std::vector 元素为指针的情况，需要注意以下几点：

内存管理：如果 std::vector 存储的是原始指针，那么仅仅清空 vector 或者让 vector 被销毁，并不会释放指针所指向的内存。因此，需要确保在 vector 被销毁之前，逐个删除所有动态分配的对象。
所有权和生命周期：需要确保在 vector 所包含的指针被使用期间，指向的对象是有效的。同时，需要清楚地定义谁拥有这些对象的所有权，以及在何时何地进行释放。
异常安全：如果在创建和填充 vector 的过程中遇到异常，需要有一个清晰的机制来处理已经分配的内存，以避免内存泄漏。
智能指针：为了简化内存管理，推荐使用智能指针（如 std::unique_ptr 或 std::shared_ptr）作为 vector 的元素类型。这样，当 vector 被清空或销毁时，智能指针会自动释放它们所拥有的资源。
避免悬垂指针：当指针指向的对象被删除或移动时，需要确保没有悬垂指针指向无效的内存地址。同样，当 vector 被重新分配时，如果存储的是指向其他元素的指针，这些指针也会失效。
深拷贝与浅拷贝：如果需要复制这样的 vector，就需要决定是进行深拷贝（复制指针指向的对象）还是浅拷贝（仅复制指针本身）。正确地选择取决于应用需求和所有权策略。