TinySTL

Container

vector

模板参数: 

1
2
3
tmplate <class T>
class vector
{ ... };

​ T: 数据类型

内部类型表示:

  • typedef mystl::allocator<T> allocator_type; 分配器类型
  • typedef mystl::allocator<T> data_allocator; 分配数据内存类型
  • typedef typename allocator_type::value_type value_type; 内部数据类型
  • typedef typename allocator_type::pointer pointer; 内部指针类型, 下面的引用类似
  • typedef typename allocator_type::const_pointer const_pointer;
  • typedef typename allocator_type::reference reference;
  • typedef typename allocator_type::const_reference const_reference;
  • typedef typename allocator_type::size_type size_type; 容量类型
  • typedef typename allocator_type::difference_type difference_type; 两个迭代器之间的距离
  • typedef value_type* iterator; 迭代器类型
  • typedef const value_type* const_iterator;
  • typedef mystl::reverse_iterator<iterator> reverse_iterator; 反向迭代器
  • typedef mystl::reverse_iterator<const_iterator> const_reverse_iterator;
1
2
3
T* start; // vector 的第一个元素的位置
T* finish; // vecotr 的最后一个元素的下一个位置
T* end_of_storage; //vector 容量的最后一个位置的下一个位置

方法关系图:

[OlZhGV.png

辅助函数

  • 1
    void insert_aux(iterator position, const T& value);
    • position: 插入的位置
    • value: 插入的值

    内部调用:

    • clear()

    对插入的数据进行内部调整, 如果剩余容量可以插入, 就直接插入, 反之则重新进行空间分配后再插入元素

  • 1
    2
    template<class ...Args>
    void insert_aux(iterator position, Args&& ...args);

    模板参数:

    • …Args: 要传入的数据列表

    方法参数:

    • position: 要插入的位置
    • args: 传入的参数列表的右值引用

    对插入的数据进行内部调整, 如果剩余容量可以插入, 就直接插入, 反之则重新进行空间分配后再插入元素, 且元素为右值, 用于插入右值时使用

    内部调用:

    • clear()
  • 1
    void deallocate();

    释放 vector 管理的内存

  • 1
    void fill_initialize(size_type n, const T& value);

    • n: 给 vector 初始化的大小

    • value: vector 中元素的初始值

内部调用: 

  • 1
    void space_initialize(size_type size, size_type cap)
    将 vector 的空间初始化为 n, 且所有元素的值都是 value
  • 1
    2
    template <class Iter>
    void range_initialize(Iter first, Iter last);
    模板参数:
    • Iter: 需要一个迭代器
    方法参数:
    • first: 区间起始位置
    • last: 区间最后位置的下一个位置
    内部调用:
  • 1
    void space_initialize(size_type size, size_type cap)
    接受两个迭代器并将 $[first, last)$ 中的内容作为 vector 的初始内容, 此时 vector 的大小为 distance(first, last)
  • 1
    void try_init() noexcept;

    给 vector 分配默认大小, 当前设置默认大小为 16, 且内部没有元素

    保证不抛出异常

  • 1
    void space_initialize(size_type size, size_type cap)
    • size: 要给 vector 初始化的大小
    • cap: 给 vector 初始化时设置的最大容量

    使 vector 留出 size 大小, 同时容量为 cap

构造函数

  • 默认构造: vector() 内部调用 try_init() 来为 vector 分配初始大小

  • 有参构造 1: explicit vector(size_type n)

    • n : vector 的大小, 容器内的元素都将初始化为 value_type 的默认值**(有构造函数则调用 T 的默认构造)**

    • explicit: 防止出现隐式转换为 vector

  • 有参构造 2:vector(size_type n, const T& value)

    • n: 同 1

    • value: vector 中元素的初始值

    内部调用:

    ​ fill_initialize(n, value)

  • 有参构造 3: 

    1
    2
    3
    template <class Iter, typename std::enable_if<
            mystl::is_input_iterator<Iter>::value, int>::type = 0>
    vector(Iter first, Iter last)

    模板参数:

    • Iter: 接收的迭代器类型

    • 第二个模板参数则是进行判断是否为 input_iterator , 若不是则该方法失效

    方法参数:

    • first: 区间起始位置的迭代器

    • last: 为区间结束位置的下一位置迭代器, 且该位置为开区间

    内部调用:

    ​ range_initialize(first, last)

  • 初始化列表构造函数:

    1
    vector(std::initializer_list<T> ilist) { ... }
    • ilist: 初始化列表

    内部调用: 

    1
    2
    template <class Iter>    
    range_initialize(Iter first, Iter last)

复制构造函数:

  1. vector(const vector<T>& other)

    • other: 要复制的 vecotr<T> 对象引用

    内部调用: range_initialize(other.begin(), other.end())

1
2
3
4
vector(vector<T>&& other)
    :start(other.start),
     finish(other.finish),
     end_of_storage(other.end_of_storage) { ... }
  • other: 要复制的 vector 的右值引用

保证不抛出异常

析构函数

1
~vector()

将 vector 内部元素全部析构, 再将 vector 内部空间释放

内部调用:

1
deallocate()

获取容器信息:

  • iterator begin() noexcept

​ 获取容器第一个元素位置, 并返回迭代器, 保证不抛出异常

  • const_iterator begin() const noexcept

    返回常量迭代器, 当 vector 对象是 const 时会被调用, 其他同上

  • iterator end() noexcept

    返回 vector 最后一个元素的后一个位置

  • const_iterator end() const noexcept

    参考 begin()

  • reverse_iterator rbegin() noexcept

    返回一个反向迭代器, 其本质指向 vector 的 end() 保证不抛出异常

  • const_reverse_iterator rbegin() const noexcept

    参考 begin()

  • reverse_iterator rend() noexcept

    返回一个反向迭代器, 指本质向 vector 的 begin() 保证不抛出异常

  • const_reverse_iterator rend() const noexcept

    参考 begin()

  • const_iterator cbegin() const noexcept

    返回 vector 首部位置的迭代器, 且其是一个常量, 保证不抛出异常

  • const_iterator cend() const noexcept

    参考 cbegin()

  • const_reverse_iterator crbegin() const noexcept

    参考 cbegin()

  • const_reverse_iterator crend() const noexcept

    参考 cbegin()

  • bool empty() const noexcept

    判断 vector 是否为空, 根据 start 是否和 finish 指向同一位置来判断 vector 是否为空. 保证不抛出异常

  • size_type size() const noexcept

    返回 vector 中元素个数. 保证不抛出异常

  • size_type max_size() const noexcept

    vector 可纳最大元素个数. 保证不抛出异常

  • size_type capacity() const noexcept

    返回 vector 容量. 保证不抛出异常

  • void reserve(size_type n);

    • n: 要求重新分配的大小

    内部调用:

    • clear()

    重新分配 vector 容量, 且只有原容量小于要求大小时才会重新分配

  • reference at(size_type n)

    • n: 要获取的下标位置

    获取指定下标处元素, 当指定下标超出有效范围后会抛出异常

  • const_reference at(size_type n) const

    效果同上, 返回的是常量引用, 作为 const vector 对象调用时的版本

  • reference front()

    获取第一个元素的引用

  • const_reference front() const

    参考 at(size_type n)

  • reference back()

    获取最后一个元素的引用

  • const_reference back() const

    参考 at(size_type n)

修改容器相关

  • void fill_assign(size_type n, const T& value);

    • n: 向 vector 中填充的元素个数
    • value: 向 vector 中填充的元素值

    调用方法:

    • vector(size_type n, const T& value)
    • iterator erase(const_iterator pos)

    该方法会将 vector 的 size() 修改为 $n$

  • 1
    2
    template <class IIter>
    void copy_assign(IIter first, IIter last, input_iterator_tag);

    模板参数:

    • IIter: 接受的迭代器

    方法参数:

    • first: 区间左端点迭代器
    • last: 区间右端点迭代器
    • input_iterator_tag: 表明 IIter 是一个 input_iterator

    内部调用:

    • iterator erase(const_iterator first, const_iterator last)
    • iterator insert(const_iterator pos, const T& value)

    使用 $[first, last)$ 中的元素填充 vector 并将容量设置为 distance(first, last), 该方法用于处理 input_iterator 类型迭代器, 其内部复制使用采用循环赋值的方式

  • 1
    2
    template <class FIter>
    void copy_assign(FIter first, FIter last, forward_iterator_tag);

    模板参数:

    • FIter: 接受的前向迭代器

    方法参数:

    • first: 区间左端点迭代器
    • last: 区间右端点迭代器
    • forward_iterator_tag: 表明 FIter 是一个 forward_iterator

    使用 $[first, last)$ 中的元素填充 vector 并将容量设置为 distance(first, last), 该方法用于处理 forward_iterator 类型迭代器, 其内部复制使用采用整体拷贝的方式, 来提升性能

  • 1
    void assign(size_type n, const T& value)

    方法参数:

    • n: 向 vector 中填充的元素个数
    • value: 向 vector 中填充的元素值

    内部调用:

    • void fill_assign(size_type n, const T& value);

    使用 $n$ 个值为 value 的元素填充 vector

  • ```c++
    template <class Iter, typename std::enable_if<

        mystl::is_input_iterator<Iter>::value, int>::type = 0>

    void assign(Iter first, Iter last)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18

    **模板参数:**

    - Iter: 接受的迭代器
    - 第二参数来判断是否为 `input_iterator` 类型迭代器, 不是则该方法则失效

    **方法参数:**

    - first: 区间左端点迭代器
    - last: 区间右端点迭代器

    使用 $[first, last)$ 的元素来填充 `vector` , 并且将容量修改为 `distance(first, last)` 同时内部根据迭代器实际类型来实例化不同的处理方法, 来提高性能

    **内部调用:**

    ```c++
    copy_assign(first, last, iterator_category(first));
    // 根据第三参数来选择调用
    1
    2
    template <class IIter>
    void copy_assign(IIter first, IIter last, input_iterator_tag);

    或

    1
    2
    template <class FIter>
    void copy_assign(FIter first, FIter last, forward_iterator_tag);

  • void assign(std::initializer_list<value_type> il)

    内部调用:

    • void copy_assign(FIter first, FIter last, forward_iterator_tag);

    使用初始化链表来填充 vector 

  • 1
    2
    template <class... Args>
    iterator emplace(const_iterator pos, Args&& ...args);

    方法参数:

    • pos: 要插入元素的位置
    • …args: 要插入的参数包的右值引用

    将参数包的第一个参数在 pos 位置处就地构造元素, 避免额外的复制或者移动开销

    内部调用:

    • 当需要扩容时调用 

      1
      2
      template <class ...Args>
      void insert_aux(iterator position, Args&& ...args)
  • 1
    2
    template <class... Args>
    void emplace_back(Args&& ...args);

    方法参数:

    • …args: 要插入的参数包的右值引用

    内部调用:

    • 当需要扩容时调用

      1
      2
      template <class T>
      void insert_aux(iterator position, const T& value)

    将参数包的第一个参数在 end()位置处就地构造元素, 避免额外的复制或者移动开销

  • void push_back(const T& value)

    方法参数:

    • value: 要放入 vector 中的值引用

    内部调用:

    • void insert_aux(iterator position, const T& value);

    向 vector 最后加入元素

  • void push_back(T&& value)

    方法参数:

    • value: 要插入的元素的右值引用

    内部调用:

    1
    2
    template <class... Args>
    void emplace_back(Args&& ...args);

    作用同上, 只是这里传入的右值引用

  • void pop_back()

    删除最后一个元素

  • 1
    2
    template<class Iter>
    void range_insert(const_iterator position, Iter first, Iter last);

    模板参数:

    • Iter: 接受的迭代器

    方法参数:

    • position: 要插入的位置

    • first: 区间左端点迭代器

    • last: 区间右端点迭代器

    在 position 处插入 $[first, last)$ 区间内的元素

  • iterator insert(const_iterator pos, const T& value)

    方法参数:

    • pos: 要插入的位置
    • value: 要插入元素的值

    内部调用:

    • void insert_aux(iterator position, const T& value);

    在 pos 处插入值为 value 的元素

  • iterator insert(const_iterator pos, T&& value)

    方法参数:

    • pos: 要插入元素的位置
    • value: 要插入元素的值

    内部调用:

    1
    2
    template <class... Args>
    iterator emplace(const_iterator pos, Args&& ...args);

    将元素值为 value 插入 vector 的 pos 处

  • iterator insert(const_iterator pos)

    方法参数:

    • pos: 要插入的位置

    内部调用:

    • iterator insert(const_iterator pos, T&& value)

    在 pos 插入一个该类型的默认值

  • void insert(const_iterator pos, size_type n, const T& value);

    方法参数:

    • pos: 要插入的位置
    • n: 要插入的元素的数量
    • value: 要插入元素的值

    在 pos 处插入 $n$ 个值为 value 的元素

  • 1
    2
    3
    template <class Iter, typename std::enable_if<
            mystl::is_input_iterator<Iter>::value, int>::type = 0>
    void insert(const_iterator pos, Iter first, Iter last)

    模板参数:

    • Iter: 接受的迭代器
    • 第二参数来判断是否为 input_iterator 类型迭代器, 不是则该方法则失效

    方法参数:

    • pos: 要插入的位置
    • first: 要插入区间的左端点
    • last: 要插入区间的右端点

    内部调用:

    1
    2
    template<class Iter>
    void range_insert(const_iterator position, Iter first, Iter last);

    将 $[first, last)$ 的元素值插入到 pos 位置

  • iterator erase(const_iterator pos);

    方法参数:

    • pos: 要删除元素的位置

    删除 pos 位置的元素

  • iterator erase(const_iterator first, const_iterator last);

    方法参数:

    • first: 要删除区间的左端点
    • last: 要删除区间的右端点

    删除区间 $[first, last)$ 内的元素

  • void swap(vector<T>& other) noexcept;

    方法参数:

    • other: 要与当前对象交换的对象

    交换两个 vector 该方法不会抛出异常.

  • void clear();

    清空 vector 只是析构掉储存的元素, 并不释放空间

  • void reverse()

    内部调用:

    • std::reverse(first, last)

    此部分暂时通过调用 std::reverse 实现, 反转 vector 元素

  • void resize(size_type new_size, const T& value);

    方法参数:

    • new_size: 设置的 vector 存储元素的大小
    • value: 重新设置大小后元素的值

    内部调用:

    • iterator erase(const_iterator first, const_iterator last);
    • void insert(const_iterator pos, size_type n, const T& value);

    将 vector 的元素数量重置为 new_size 且元素值为 value

  • void resize(size_type new_size)

    方法参数:

    • new_size: 设置的 vector 存储元素的大小

    内部调用:

    • void resize(size_type new_size, const T& value);

    将 vector 的元素数量重置为 new_size 且元素值为默认值

重载运算符

赋值运算符:

  • 左值引用版本

    vector<T>& operator=(const vector<T>& rhs);

    内部调用:

    1
    2
    3
    template <class Iter, typename std::enable_if<
            mystl::is_input_iterator<Iter>::value, int>::type = 0>
    vector(Iter first, Iter last)

  • 右值引用版本

    vector<T>& operator=(vector<T>&& rhs)

    内部调用:

    • clear()

    保证不抛出异常

  • 初始化列表版本
    vector<T>& operator=(std::initializer_list<T> ilist)

  • 内部调用:

    • vector(std::initializer_list<T> ilist) { ... }

重载 [] 运算符:

  • reference operator[](size_type n)

    取出下标为 $n$ 的元素

  • const_reference operator[](size_type n) const

    同上, 当对象为常对象时优先调用