实现自定义容器——vector

什么是vector

  • 容器是 STL 中的一个重要概念，它们封装了一些常用的数据结构，可以提高程序的编写速度，方便程序员使用。
  • 前面我们介绍了 vector 的基本使用，接下来我们来实现一个自定义的 vector，方便我们更好的理解这个容器
  • 对 vector 的接口的实现参考cppreference-vector

准备工作

  • 这里是对 vector 的介绍，vecctor 是一个封装了动态数组的序列容器
    在这里插入图片描述
  • 如果你学过数据结构的话，动态数组是使用指针模拟的，而动态数组会涉及到扩容的问题，既然 vector 也是使用动态数组封装的，那么必定是需要扩容的，扩容后还需要把现有元素移动到新空间等操作，为了方便，我们可以实现一些工具函数，减少重复代码。
  • 我们实现的是接受一个模板参数的 vector，标准库的 vector 还有一个 空间分配器
    • 需要哪些成员变量（类型都为 T*），有了前两个变量我们可以 O(1) 的知道容器内有效元素的个数，有了最后一个变量我们可以方便的知道什么时候该扩容了
      • 动态数组的起始地址
      • 最后一个有效元素的下一个位置
      • 最后一个可用空间的下一个位置
    • 模板参数 T 比较抽象，我们不知道他是什么意思，我们来封装一些意义明确的数据类型，参考官网即可
      在这里插入图片描述
  • 封装是面向对象的概念，实现自然少不了类，vector 也有各种不同的构造函数，有的构造函数需要预分配空间，所以需要分配空间，我们实现的 vector 暂时不需要使用分配器，我们使用 new 来实现空间的分配，有的构造函数还支持对空间内的元素进行初始化

在这里插入图片描述

  • 分析得到需要分配空间、初始化空间内的元素为指定的元素的函数
void initialize_fill(size_type count, const T& value)
{
    start = allocate_storage(count);
    finish = start;
    capacity_ = start + count;
    fill_n(start, count, value);
    finish = start + count;
}
static T* allocate_storage(size_type count)
{
    return count == 0 ? nullptr : new T[count];
}
static void fill_n(T* dest, size_type count, const T& value)
{
    while (count--)
    {
        *dest = value;
        ++dest;
    }
}

具体实现

  • 首先我们实现最基本的构造函数和析构函数，C++11 后还引入了移动构造函数和移动赋值重载函数，改变参数类型为右值引用即可
  • 这里还需要增加一些工具函数，移动构造函数会进行资源窃取而非拷贝，所以需要一个交换双方资源的函数，窃取后需要对被移动的对象的资源置空，还需要一个重置函数， 使用另一个容器构造一个新的容器时，需要拷贝对方的资源，需要一个拷贝函数
  • 工具函数
void copy_from(const vector& other)
{
    size_type other_size = other.size();
    if (other_size == 0)
        return;

    start = allocate_storage(other_size);
    finish = start;
    capacity_ = start + other_size;
    copy_range(other.start, other.finish, start);
    finish = start + other_size;
}
void reset_storage() noexcept
{
    start = nullptr;
    finish = nullptr;
    capacity_ = nullptr;
}
static void copy_range(const T* first, const T* last, T* dest)
{
    while (first != last)
    {
        *dest = *first;
        ++first;
        ++dest;
    }
}
void swap(vector& other) noexcept
{
    std::swap(start, other.start);
    std::swap(finish, other.finish);
    std::swap(capacity_, other.capacity_);
}
  • 完整构造函数实现（实现重载赋值运算符的时候注意检查自我赋值）
vector() noexcept : start(nullptr), finish(nullptr), capacity_(nullptr) {}

vector(int n, const T& value)
    : start(nullptr), finish(nullptr), capacity_(nullptr)
{
    if (n <= 0)
        return;

    initialize_fill(static_cast<size_type>(n), value);
}

vector(const vector& other)
    : start(nullptr), finish(nullptr), capacity_(nullptr)
{
    copy_from(other);
}

vector(vector&& other) noexcept
    : start(other.start), finish(other.finish), capacity_(other.capacity_)
{
    other.reset_storage();
}

~vector()
{
    delete[] start;
}

vector& operator=(const vector& other)
{
    if (this != &other)
    {
        vector tmp(other);
        swap(tmp);
    }
    return *this;
}

vector& operator=(vector&& other) noexcept
{
    if (this != &other)
    {
        delete[] start;
        start = other.start;
        finish = other.finish;
        capacity_ = other.capacity_;
        other.reset_storage();
    }
    return *this;
}
  • 接下来实现元素的插入，插入元素涉及到扩容和移动元素，工具函数，当 vector 存储的事非平凡类型时，使用 move 可以调用对方的移动赋值重载，提高效率。需要特别处理容器容量为0的时候，否则会出现段错误
void shift_right(iterator pos, size_type count)
{
     iterator src = finish;
     while (src != pos)
     {
         * (src + count - 1) = std::move(*(src - 1));
         --src;
     }
 }
 void ensure_capacity(size_type required_capacity)
 {
     if (required_capacity <= capacity())
         return;
     size_type new_capacity = capacity() == 0 ? 1 : capacity();
     while (new_capacity < required_capacity)
         new_capacity *= 2;
     reallocate(new_capacity);
 }
  • push_back 和 insert 实现，需要注意插入后移动 finish 的位置，让其始终指向有效元素的下一个位置，insert 返回的是插入位置的迭代器，push_back一般按照2倍扩容
void push_back(const T& value)
{
   ensure_capacity(size() + 1);
   *finish = value;
   ++finish;
}

void push_back(T&& value)
{
   ensure_capacity(size() + 1);
   *finish = std::move(value);
   ++finish;
}
iterator insert(const_iterator pos, const T& value)
{
   size_type index = position_index(pos);
   ensure_capacity(size() + 1);
   iterator insert_pos = start + index;
   shift_right(insert_pos, 1);
   *insert_pos = value;
   ++finish;
   return insert_pos;
}

iterator insert(const_iterator pos, T&& value)
{
   size_type index = position_index(pos);
   ensure_capacity(size() + 1);
   iterator insert_pos = start + index;
   shift_right(insert_pos, 1);
   *insert_pos = std::move(value);
   ++finish;
   return insert_pos;
}

iterator insert(const_iterator pos, size_type count, const T& value)
{
   size_type index = position_index(pos);
   if (count == 0)
       return start + index;
   ensure_capacity(size() + count);
   iterator insert_pos = start + index;
   shift_right(insert_pos, count);
   fill_n(insert_pos, count, value);
   finish += count;
   return insert_pos;
}
  • 接下来实现一些和容器容量和访问的函数，这里使用 std::reverse_iterator 实现反向迭代器
T* data() noexcept { return start; }
const T* data() const noexcept { return start; }

iterator begin() noexcept { return start; }
iterator end() noexcept { return finish; }
const_iterator begin() const noexcept { return start; }
const_iterator end() const noexcept { return finish; }
const_iterator cbegin() const noexcept { return begin(); }
const_iterator cend() const noexcept { return end(); }

reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
const_reverse_iterator rbegin() const noexcept { return const_reverse_iterator(end()); }
const_reverse_iterator rend() const noexcept { return const_reverse_iterator(begin()); }
const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator(end()); }
const_reverse_iterator crend() const noexcept { return const_reverse_iterator(begin()); }

T& front() { return *start; }
T& back() { return *(finish - 1); }
const T& front() const { return *start; }
const T& back() const { return *(finish - 1); }

bool empty() const noexcept { return finish == start; }
size_type size() const noexcept { return static_cast<size_type>(finish - start); }
size_type capacity() const noexcept { return static_cast<size_type>(capacity_ - start); }

T& operator[](size_type index) { return start[index]; }
const T& operator[](size_type index) const { return start[index]; }
const T& at(size_type index) const
{
    if (index >= size())
        throw std::out_of_range("vector::at");
    return start[index];
}
T& at(size_type index)
{
    if (index >= size())
        throw std::out_of_range("vector::at");
    return start[index];
}
  • 接下来实现和删除有关的函数，删除元素后需要将指定位置后的元素向左移动，erase 函数需要注意如果要删除的位置大于 end()，直接返回 end()，如果符合要求则需要返回被删除元素的下一个位置的迭代器，注意clear函数并不会改变容量，只会清空元素
void shift_left(iterator from, size_type count)
{
    iterator dest = from - count;
    while (from != finish)
    {
        *dest = std::move(*from);
        ++dest;
        ++from;
    }
}
void pop_back()
{
    if (!empty())
        --finish;
}
iterator erase(iterator pos)
{
    if (pos < begin() || pos >= end())
        return end();

    shift_left(pos + 1, 1);
    --finish;
    return pos == finish ? end() : pos;
}

iterator erase(const_iterator pos)
{
    if (pos < begin() || pos >= end())
        return end();
    return erase(start + (pos - begin()));
}
void clear() noexcept
{
    finish = start;
}
  • 测试代码
#include "vector.hpp"

#include <cassert>
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>

using my_vector::vector;

template <class T>
void expect_sequence(const vector<T>& vec, std::initializer_list<T> expected)
{
    assert(vec.size() == expected.size());
    std::size_t index = 0;
    for (const auto& value : expected)
    {
        assert(vec[index] == value);
        ++index;
    }
}

void test_default_constructor()
{
    vector<int> vec;
    assert(vec.empty());
    assert(vec.size() == 0);
    assert(vec.capacity() == 0);
    assert(vec.begin() == vec.end());
}

void test_fill_constructor()
{
    vector<int> vec(4, 7);
    assert(!vec.empty());
    assert(vec.size() == 4);
    assert(vec.capacity() == 4);
    expect_sequence(vec, {7, 7, 7, 7});
}

void test_push_back_and_element_access()
{
    vector<std::string> vec;
    vec.push_back("a");
    vec.push_back(std::string("b"));
    vec.push_back("c");

    assert(vec.size() == 3);
    assert(vec.front() == "a");
    assert(vec.back() == "c");
    assert(vec[1] == "b");

    const vector<std::string>& cvec = vec;
    assert(cvec.front() == "a");
    assert(cvec.back() == "c");
    assert(cvec[2] == "c");
}

void test_at()
{
    vector<int> vec;
    vec.push_back(10);
    vec.push_back(20);

    assert(vec.at(0) == 10);
    assert(vec.at(1) == 20);

    bool thrown = false;
    try
    {
        (void)vec.at(2);
    }
    catch (const std::out_of_range&)
    {
        thrown = true;
    }
    assert(thrown);
}

void test_reserve_and_resize()
{
    vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);

    vec.reserve(10);
    assert(vec.capacity() >= 10);
    expect_sequence(vec, {1, 2});

    vec.resize(5);
    assert(vec.size() == 5);
    assert(vec[0] == 1);
    assert(vec[1] == 2);
    assert(vec[2] == 0);
    assert(vec[3] == 0);
    assert(vec[4] == 0);

    vec.resize(3);
    expect_sequence(vec, {1, 2, 0});
}

void test_insert_single()
{
    vector<int> vec;
    vec.push_back(1);
    vec.push_back(3);

    auto it = vec.insert(vec.begin() + 1, 2);
    assert(it == vec.begin() + 1);
    assert(*it == 2);
    expect_sequence(vec, {1, 2, 3});

    auto end_it = vec.insert(vec.end(), 4);
    assert(end_it == vec.end() - 1);
    expect_sequence(vec, {1, 2, 3, 4});
}

void test_insert_multiple()
{
    vector<std::string> vec;
    vec.push_back("head");
    vec.push_back("tail");

    auto it = vec.insert(vec.begin() + 1, 3, std::string("mid"));
    assert(it == vec.begin() + 1);
    expect_sequence<std::string>(vec, {"head", "mid", "mid", "mid", "tail"});
}

void test_pop_back_and_clear()
{
    vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);

    vec.pop_back();
    expect_sequence(vec, {1, 2});

    std::size_t old_capacity = vec.capacity();
    vec.clear();
    assert(vec.empty());
    assert(vec.size() == 0);
    assert(vec.capacity() == old_capacity);

    vec.push_back(9);
    expect_sequence(vec, {9});
}

void test_erase()
{
    vector<int> vec;
    for (int i = 1; i <= 5; ++i)
        vec.push_back(i);

    auto it = vec.erase(vec.begin() + 2);
    assert(it == vec.begin() + 2);
    assert(*it == 4);
    expect_sequence(vec, {1, 2, 4, 5});

    auto end_it = vec.erase(vec.end() - 1);
    assert(end_it == vec.end());
    expect_sequence(vec, {1, 2, 4});

    auto invalid = vec.erase(vec.end());
    assert(invalid == vec.end());
}

void test_copy_semantics()
{
    vector<std::string> original;
    original.push_back("a");
    original.push_back("b");

    vector<std::string> copy(original);
    vector<std::string> assigned;
    assigned = original;

    original[0] = "changed";

    expect_sequence<std::string>(copy, {"a", "b"});
    expect_sequence<std::string>(assigned, {"a", "b"});
    expect_sequence<std::string>(original, {"changed", "b"});
}

void test_move_semantics_and_swap()
{
    vector<std::string> source;
    source.push_back("x");
    source.push_back("y");

    vector<std::string> moved(std::move(source));
    expect_sequence<std::string>(moved, {"x", "y"});
    assert(source.empty());

    vector<std::string> other;
    other.push_back("left");
    other.push_back("right");

    moved.swap(other);
    expect_sequence<std::string>(moved, {"left", "right"});
    expect_sequence<std::string>(other, {"x", "y"});

    vector<std::string> assigned;
    assigned = std::move(moved);
    expect_sequence<std::string>(assigned, {"left", "right"});
    assert(moved.empty());
}

void test_iterators()
{
    vector<int> vec;
    vec.push_back(1);
    vec.push_back(2);
    vec.push_back(3);

    int sum = 0;
    for (auto it = vec.begin(); it != vec.end(); ++it)
        sum += *it;
    assert(sum == 6);

    const vector<int>& cvec = vec;
    auto cit = cvec.cbegin();
    assert(*cit == 1);
    assert(*(cvec.cend() - 1) == 3);

    auto rit = vec.rbegin();
    assert(*rit == 3);
    ++rit;
    assert(*rit == 2);

    auto crit = cvec.crbegin();
    assert(*crit == 3);
}

int main()
{
    test_default_constructor();
    test_fill_constructor();
    test_push_back_and_element_access();
    test_at();
    test_reserve_and_resize();
    test_insert_single();
    test_insert_multiple();
    test_pop_back_and_clear();
    test_erase();
    test_copy_semantics();
    test_move_semantics_and_swap();
    test_iterators();

    std::cout << "all tests passed\n";
    return 0;
}

迭代器失效

  • 通过自定义 vector ，你应该了解了 vector 的原理，接下来让我们探讨一个比较坑的问题——迭代器失效。什么会导致其失效呢？我们的实现中出现了扩容的操作，这就是一个迭代器失效的问题，扩容后原来的元素都指向了新的内存， 但是现存的迭代器指向的还是旧的内存，此时再去访问就会导致出现未定义行为；再比如 insert 插入后会导致部分元素移动位置，就会出现迭代器失效。
  • 从上面我们可以推出，只要涉及到了元素移动，那么迭代器失效就会发生，下面是官网对迭代器失效的场景的介绍

在这里插入图片描述

  • 迭代器失效的危害
    • 原来的内存已经不被当前对象持有，访问可能会出现段错误或者程序崩溃的问题
    • 可能某个结果是对的，让你误以为其它的结果也是对的，可能导致未预期的结果
  • 如何预防：
    • 尽量不要使用迭代器遍历容器，如果使用，遍历的时候不要做读以外的操作；或者必须接收删除、插入等函数的返回值

这篇文章就到这里了，如果觉得写的还不错的话还请点个赞，如果有写的不对的地方还请批评指正

# rpc # dubbo # 网络协议 # c++ # 算法 # 数据结构
Logo
https://edu.csdn.net/learn/39067/627173?utm_source=2019755004

汇聚全球AI编程工具，助力开发者即刻编程。

更多推荐

cover

一个 API 入口调用多个大模型：AiiOnly客户端 + CC Switch 打通 Codex AI编程流程

avatar AI编程社区
cover

VSCode Claude Code + MiMo 中转免登录完整配置教程（解决原生登录弹窗 + 模型报错）

avatar AI编程社区
cover

从零开始做一个属于自己的 Skill（保姆级教程）

avatar AI编程社区