手写STL之Vector

代码仓库：yanglianoo/My_STL at timer (github.com)

1.Vector 概述

在C++ STL（标准模板库）中，vector 是一个动态数组容器，它是一个模板类具有以下特性：

1. 动态大小: vector 的大小可以根据需要动态增长或缩小。它可以自动调整内部存储空间，以适应容器中元素的数量。
2. 连续存储: vector 中的元素在内存中是连续存储的，这使得对元素的随机访问变得高效。
3. 快速插入和删除: 在 vector 的末尾插入或删除元素是高效的，时间复杂度为常数。但在中间或开头插入或删除元素的操作可能会导致元素的移动，时间复杂度为线性。
4. 随机访问: vector 支持通过索引进行随机访问。可以使用下标运算符 [] 或 at() 函数来访问特定位置的元素。
5. 动态调整内存: 当 vector 的大小超过当前分配的内存空间时，它会重新分配更大的内存块，并将现有元素移动到新的内存中。这可以确保容器始终具有足够的内存来存储元素。
6. 元素访问: 可以使用迭代器来遍历 vector 中的元素。可以使用 begin() 和 end() 成员函数获取指向容器开头和结尾的迭代器。
7. 容器操作: vector 支持许多常见的容器操作，如排序、查找、插入和删除元素。它还提供了与其他容器兼容的接口，例如迭代器、范围构造函数和算法函数。

STL库中vector的定义如下:

template< class T,class Allocator = std::allocator<T>> 
    class vector;

T	元素的类型。T 必须满足可复制赋值 (CopyAssignable) 和可复制构造 (CopyConstructible) 的要求。

Allocator	用于获取/释放内存及构造/析构内存中元素的分配器。类型必须满足分配器 (Allocator) 的要求。

成员函数
(构造函数)	构造 vector (公开成员函数)
(析构函数)	析构 vector (公开成员函数)
operator=	赋值给容器 (公开成员函数)
assign	将值赋给容器 (公开成员函数)
get_allocator	返回相关的分配器 (公开成员函数)
元素访问
at	访问指定的元素，同时进行越界检查 (公开成员函数)
operator[]	访问指定的元素 (公开成员函数)
front	访问第一个元素 (公开成员函数)
back	访问最后一个元素 (公开成员函数)
data	直接访问底层数组 (公开成员函数)
迭代器
begincbegin(C++11)	返回指向起始的迭代器 (公开成员函数)
endcend(C++11)	返回指向末尾的迭代器 (公开成员函数)
rbegincrbegin(C++11)	返回指向起始的逆向迭代器 (公开成员函数)
rendcrend(C++11)	返回指向末尾的逆向迭代器 (公开成员函数)
容量
empty	检查容器是否为空 (公开成员函数)
size	返回容纳的元素数 (公开成员函数)
max_size	返回可容纳的最大元素数 (公开成员函数)
reserve	预留存储空间 (公开成员函数)
capacity	返回当前存储空间能够容纳的元素数 (公开成员函数)
shrink_to_fit	通过释放未使用的内存减少内存的使用 (公开成员函数)
修改器
clear	清除内容 (公开成员函数)
insert	插入元素 (公开成员函数)
emplace(C++11)	原位构造元素 (公开成员函数)
erase	擦除元素 (公开成员函数)
push_back	将元素添加到容器末尾 (公开成员函数)
emplace_back(C++11)	在容器末尾就地构造元素 (公开成员函数)
pop_back	移除末元素 (公开成员函数)
resize	改变容器中可存储元素的个数 (公开成员函数)
swap	交换内容

参考链接: std::vector - cppreference.com

2.构造Vector

自己手写vector时，迭代器不是通用的Allocator类型，需要在vector内部实现一个自定义的迭代器

vector模板类定义如下，需要维护三个私有的成员变量

template<typename T>
class vector
{
private:
    int _size;    //实际数组大小
    int _capacity;//最大容量
    T* _elem;     //数据区指针  
}

注意：模板类的实现和声明不能分离编译，因此最好将模板类的声明和实现都放在头文件中
参考链接：(64条消息) C++中模板类的编译过程_c++模板编译_jiazhucai的博客-CSDN博客

2.1构造函数

构造函数定义：

vector();   //默认构造函数
vector(std::initiallizer_list<T> init) // c++11 列表初始化
vector(const vector<T>& other); //用另外一个vector来构造
vector(const vector<T>& other,int left,int right); //用另外一个vector区间构造
vector(size_t count, T& value); //初始化为count个 value

2.1.1 辅助函数

在定义构造函数具体实现时需要定义几个辅助函数:

protected:
	void expand(); //空间不足时扩容
	void shrink(); //装填因子过小时压缩
	void copyFrom ( T const* A, int left, int right ); //复制数组区间 A[left, right]

• 内存扩充函数expand()

#define DEFAULT_CAPACITY 3 
template <typename T> 
void vector<T>::expand()
{

    if(_size <= _capacity) return;  //当size 小于等于 capacity 时 不需要扩容
    if(_capacity < DEFAULT_CAPACITY) _capacity = DEFAULT_CAPACITY; //当capacity小于最小大小，更改capacity为最小大小
    /* 反复翻倍，直到 _capacity > _size*/
    while (_capacity < _size)
    {
        _capacity *=2;
    }
    T* old_data = _data;
    _data = new T[_capacity << 1];  //capacity 增大一倍，重新 new 内存
    for(int i=0;i<_size; i++)       //赋值
    {
        _data[i] = old_data[i];
    }
    delete[] old_data;
}

• 内存缩小函数shrink()

template <typename T> 
void vector<T>::shrink()
{
    if(_capacity < DEFAULT_CAPACITY << 1) return; //不致收缩倒DEFAULT_CAPACITY以下
    if(_size << 2 > _capacity) return;  //以 25% 为边界

    T* old_data = _data;
    _data = new T[_capacity >> 1];
    for(size_t i = 0; i < _size; i++)
    {
        _data[i] = old_data[i];
    }
    delete[] old_data;
}

• 区间复制函数copyFrom ( T const* A, int left, int right )

template <typename T> 
void vector<T>::copyFrom ( T const* A, int left, int right )
{
    if(_data != nullptr)
    {
        delete [] _data;
        _data = nullptr;
    }
    _capacity = (right - left) * 2;
    _size = 0;
    _data = new T[_capacity];

    while (left < right)
    {
        _data[_size] = A[left];
        _size++;
        left++;
    }
}

2.2.2 构造函数实现

• vector()

/*构造函数*/
template<typename T>
vector<T>::vector():_data(nullptr),_capacity(0),_size(0){}

• vector(const vector<T>& *other*)

template <typename T>
vector<T>::vector(const vector<T>& other)
{
    copyFrom(other._data,0,other._size); //直接调用 copyFrom 函数
}

• vector(std::initializer_list<T> *init*)

/* c++11 列表初始化 */
template <typename T>
vector<T>::vector(std::initializer_list<T> init)
{
    _size = init.size();
    _capacity = _size * 2;
    int i = 0;
    _data = new T[_capacity];
    for(const auto & elem : init)
    {
        _data[i++] = elem;
    }
}

• vector(int *count*, T& *value*)

template <typename T>
vector<T>::vector(size_t count, T& value)
{
    _size = count;
    _capacity = 2 * _size;
    _data = new T[_capacity];
    for(size_t i =0; i<count;i++)
    {
        _data[i] = value;
    }
}

2.2 析构函数

/* 析构函数 */
template<typename T>
vector<T>::~vector()
{
    if(_data != nullptr)
    {
        delete [] _data;
        _data = nullptr;
    }
    _size = 0;
    _capacity = 0;
}

3.赋值

实现的成员函数如下：

public: //成员函数
    vector& operator=(const vector& other);
    vector& operator=( std::initializer_list<T> ilist );

    void assign(size_t count,const T& value);
    void assign(std::initializer_list<T> ilist );

• vector& operator=(const vector& other)

template <typename T>
vector<T>& vector<T>::operator=(const vector& other)
{
    copyFrom(other._data,0,other._size);
    return *this;
}

• vector<T>::operator=( std::initializer_list<T> *ilist* )

template <typename T>
vector<T>& vector<T>::operator=( std::initializer_list<T> ilist )
{
    if(_data != nullptr)
    {
        delete [] _data;
        _data = nullptr;
    }
    _size = ilist.size();
    _capacity = _size * 2;
    int i = 0;
    _data = new T[_capacity];
    for(const auto & elem : ilist)
    {
        _data[i++] = elem;
    }
    return *this;
}

4.元素访问

元素访问的接口有如下这些：

public: //元素访问
    T& at(size_t index);
    T& operator[](size_t index);
    T& front();
    T& back();
    T* data();

具体实现如下：

template <typename T>
T& vector<T>::at(size_t index)
{
    if(index <0 || index >= _size)
    {
        throw std::logic_error("out of range");
    }
    return _data[index];
}

template <typename T>
T& vector<T>::operator[](size_t index)
{
    return this->at(index);
}

template <typename T>
T& vector<T>::front()
{
    return _data[0];
}

template <typename T>
T& vector<T>::back()
{
    if (_size <= 0)
    {
        throw std::logic_error("vector is empty");
    }
    return _data[_size-1];
}

template <typename T>
T* vector<T>::data()
{
    return _data;
}

5.迭代器

5.1 迭代器使用实例

在构建迭代器之前，先看看迭代器的用法，一般用于遍历容器中的各个元素

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};
    // 1. 使用迭代器进行遍历
    std::cout << "1. Iterate using iterators: ";
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    // 2. 使用auto关键字进行简化
    std::cout << "2. Iterate using auto keyword: ";
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    // 3. 使用范围基于循环 (range-based loop)
    std::cout << "3. Iterate using range-based loop: ";
    for (const auto& element : vec) {
        std::cout << element << " ";
    }
    // 4. 修改容器中的元素
    std::cout << "4. Modify elements using iterators: ";
    for (auto it = vec.begin(); it != vec.end(); ++it) {
        *it = *it * 2;
    }
    for (const auto& element : vec) {
        std::cout << element << " ";
    }
    // 5. 插入元素
    std::cout << "5. Insert elements using iterators: ";
    auto insertPos = vec.begin() + 2; // 在索引2的位置之后插入元素
    vec.insert(insertPos, 10);
    for (const auto& element : vec) {
        std::cout << element << " ";
    }
    // 6. 删除元素
    std::cout << "6. Erase elements using iterators: ";
    auto erasePos = vec.begin() + 1; // 删除索引1的元素
    vec.erase(erasePos);
    for (const auto& element : vec) {
        std::cout << element << " ";
    }
    return 0;
}

5.2 迭代器类实现

iterrator是一个类，在内部维护了一个指针，需要对其进行各种操作符重载，iterrator的具体实现如下：

public: //迭代器
    class Iterrator
    {
        private:
            T * m_pointer;
        public:
            Iterrator():m_pointer(nullptr) {}
            Iterrator(T * pointer) : m_pointer(pointer) {}
            ~Iterrator() {}
        /* 判断两个迭代器是否相等 */
        bool operator == (const Iterrator & other)
        {
            return m_pointer == other.m_pointer;   
        } 
        /* 迭代器赋值 */
        Iterrator operator = (const Iterrator& other)
        {
            m_pointer = other.m_pointer;
        }

        /* 前缀递增*/
        Iterrator & operator ++ ()
        {
            m_pointer +=1;
            return *this;
        }

        /* 后缀递增 */
        Iterrator operator ++ (int)
        {
            Iterrator it = *this;
            ++(*this);
            return it;
        }

        Iterrator operator + (int i)
        {
            Iterrator it = *this;
            it.m_pointer += i;
            return it;
        }
        Iterrator operator += (int i)
        {
            m_pointer += i;
            return *this;
        }

        Iterrator operator -= (int i)
        {
            m_pointer -= i;
            return *this;
        }

        Iterrator operator - (int i)
        {
            Iterrator it = *this;
            it.m_pointer -= i;
            return it;
        }

        int operator - (const Iterrator& other) const
        {
            return m_pointer - other.m_pointer;
        }

        T & operator * ()
        {
            return *m_pointer;
        }

        T * operator -> ()
        {
            return m_pointer;
        }
    };

记录：在对Iterrator前++和后++重载时，如下:

/* 前缀递增*/
Iterrator & operator ++ ()
{
	m_pointer +=1;
	return *this;
}
 /* 后缀递增 */
Iterrator operator ++ (int)
{
     Iterrator it = *this;
     ++(*this);
     return it;
}

在C++中，后缀递增操作符(it++)可以通过接受一个额外的int参数进行区分，这是由C++语言规范所定义的。根据规范，后缀递增操作符的函数参数列表中必须有一个int类型的参数，尽管在函数体内并没有使用该参数。

这种设计是为了在语法上能够区分前缀递增和后缀递增操作。当编译器遇到it++表达式时，它会根据后缀递增操作符的函数参数列表中是否存在一个额外的int参数来决定使用后缀递增操作符的重载函数。

编译器会将后缀递增操作符的调用转换为对重载的后缀递增操作符函数的调用，并传递一个编译器生成的临时整数参数（通常是0）。

请注意，这个整数参数的名称在函数体内并没有使用，因为它的存在只是为了与前缀递增操作符进行区分，而不是为了实际使用。

5.3 迭代器操作函数实现

begin用于获取头指针，end用于获取尾指针

public: //迭代器操作函数
    Iterator begin();
    Iterator end();

具体实现如下：

template <typename T>
typename vector<T>::Iterator vector<T>::begin()
{
    vector<T>::Iterator it(_data);
    return it;
}

template <typename T>
typename vector<T>::Iterator vector<T>::end()
{
    vector<T>::Iterator it(_data + _size);
    return it;
}

这里需要使用typename显示的告诉编译器vector<T>::Iterator是一个类型

6.容量

和容量相关的接口函数比较简单，实现的接口如下：

public: //容量
    bool empty() const; //判断容器是否为空
    size_t size() const; //获取容器元素个数
    size_t max_size() const; //获取容器最大存储个数
    void reserve(size_t new_cap);
    size_t capacity() const;
    void shrink_to_fit();

template <typename T>
bool vector<T>::empty() const
{
    return _size==0;
}

template <typename T>
size_t vector<T>::size() const
{
    return _size;
}

template <typename T>
size_t vector<T>::max_size() const
{
    return _capacity;
}


template <typename T>
size_t vector<T>::capacity() const
{
    return _capacity;
}
/* 重置容器大小 */
template <typename T>
void vector<T>::reserve(size_t new_cap)
{
    if(_capacity >= new_cap)
    {
        return;
    }
    else
    {
        _size += new_cap;
        expand();
    }
}

/* 如果 _capacity 过大则缩减*/
template <typename T>
void vector<T>::shrink_to_fit()
{
    shrink();
}

7.修改器

和修改容器有关的接口函数如下：

public: //修改器
    void clear();
    Iterator insert(const Iterator it ,const T & value);  
    Iterator insert(const Iterator it ,int n,const T & value);
    Iterator erase(const Iterator it);
    Iterator erase(const Iterator first,const Iterator last);
    void push_back(const T & value);
    void pop_back();
    void resize(size_t size);
    void swap(vector & other);

• clear()

/* clear操作，直接将 _size 清零*/
template <typename T>
void vector<T>::clear()
{
    if (_size <= 0)
    {
        throw std::logic_error("vector is empty");
    }
    _size = 0;
}

• Iterator insert(const Iterator it ,int n,const T & value)

/* 在 it 的位置插入 n 个 T 元素*/
template <typename T>
typename vector<T>::Iterator vector<T>::insert(const Iterator it ,int n,const T & value)
{
    int size = it - begin();
    _size += n;
    //如果有需要，则扩容
    expand();
    for(size_t i=_size; i>size;i--)
    {
        _data[i+n-1] = _data[i-1];
    }
    for(size_t i=0; i<n;i++)
    {
        _data[size+i] = value;
    }
    return vector<T>::Iterator(_data + size);
}

• Iterator insert(const Iterator it ,const T & value)

/* 在 it 位置插入 1 个元素 value*/
template <typename T>
typename vector<T>::Iterator vector<T>::insert(const Iterator it ,const T & value)
{
    _size+=1;
    expand();
    insert(it,1,value);
}

• Iterator erase(const Iterator it)

/* 删除 it 位置的元素 */
template <typename T>
typename vector<T>::Iterator vector<T>::erase(const Iterator it)
{
    if(end() - it == 1)
    {
        _size -= 1;
        return end();
    }
    int count = it - begin();
    for(size_t i = count; i < _size -1 ; i++)
    {
        _data[i] = _data[i+1];
    }
    _size -= 1;
    return it;
}

• Iterator erase(const Iterator first,const Iterator last)

/* 区间删除 */
template <typename T>
typename vector<T>::Iterator vector<T>::erase(const Iterator first,const Iterator last)
{
    if( first == last)
    {
        return first;  
    }
    else
    {
        int f = first - begin();
        int l = last - begin();
        while ( l < _size) // [last,_szie) 顺次前移 l - f 个单元
        {
            _data[f++] = _data[l++];
        }
        _size = f;  //更新规模
        shrink(); //若有必要则缩容
        return first;
    }
}

• void push_back(const T & value)

/* 在尾部插入一个元素value */
template <typename T>
void vector<T>::push_back(const T& value)
{
    if(_size < _capacity)
    {
        _data[_size] = value; 
        _size++;
        return;
    }
    else
    {
        _size++;
        expand();
        int index = _size - 1;
        _data[index] = value; 
    }
}

• void pop_back()

/* 弹出最后一个元素 */
template <typename T>
void vector<T>::pop_back()
{
    if(_size != 0)
    {
        _size--;
    }
}

• void resize(size_t size)

template <typename T>
void vector<T>::resize(size_t size)
{
    if(_size > size)
    {
        _size = size;
        return;
    }

    if(size <= _capacity)
    {
        for(size_t i= _size; i < size; i++)
        {
            _data[i] = T();
        }
        _size = size;
        return;
    }
    _size = size;
    expand(); 
}

• void swap(vector & other)

/* 两个 vector 交换*/
template <typename T>
void vector<T>::swap(vector & other)
{
    T * data = other._data;
    int size = other._size;
    int capacity = other._capacity;

    other._data = _data;
    other._size = _size;
    other._capacity = _capacity;

    _data = data;
    _size = size;
    _capacity = capacity;
}

8.结束语

至此，vector 构造完毕，未进行测试，不知道是否有bug