玩命加载中 . . .

4.2-vector

STL
C++
发布日期:   2022-06-12 
template<class T, class Alloc = allocator<T>>
class vector{
private:
    T *start_;
    T *finish_;
    T *endOfStorage_;

    typedef Alloc dataAllocator;
public:
    typedef T                   value_type;
    typedef T*                  iterator;
    typedef const T*            const_iterator;
    typedef reverse_iterator_t<T*>          reverse_iterator;
    typedef reverse_iterator_t<const T*>    const_reverse_iterator;
    typedef iterator            pointer;
    typedef T&                  reference;
    typedef const T&            const_reference;
    typedef size_t              size_type;
    typedef ptrdiff_t           difference_type;
public:
    vector& operator=(const vector& v);
    vector& operator=(vector&& v);
    ~vector();
};

构造函数和析构函数

1、默认构造函数

vector(): start_(0), finish_(0), endOfStorage_(0) {}

2、指定元素个数的构造函数

explicit vector(const size_type n) {
    allocateAndFillN(n, value_type());
}
vector(const size_type n, const value_type& value) {
    allocateAndFillN(n, value);
}

指定了n个元素会调用allocateAndFillN函数，内部使用分配器分配n个元素，如果还指定了要填充的元素，就调用之前提到过的uninitialized_fill_n函数进行填充

template<class T, class Alloc>
void vector<T, Alloc>::allocateAndFillN(const size_type n, const value_type& value) {
    start_ = dataAllocator::allocate(n);
    TinySTL::uninitialized_fill_n(start_, n, value);
    finish_ = endOfStorage_ = start_ + n;
}

3、给定容器迭代器区间的构造函数

// 指定迭代器的构造函数
template<class InputIterator>
vector(InputIterator first, InputIterator last) {
    vector_aux(first, last, typename std::is_integral<InputIterator>::type());
}

根据传入的是迭代器还是整数调用不同版本的vector_aux函数

vector_aux的非整数版本会调用allocateAndCopy函数，先使用分配器分配last-first个元素的空间，然后调用之前提到过的uninitialized_copy函数把[first, last)区间的元素拷贝到start_的位置

// 非整数版本
template<class T, class Alloc>
template<class InputIterator>
void vector<T, Alloc>::vector_aux(InputIterator first, InputIterator last, std::false_type){
    allocateAndCopy(first, last);
}

template<class T, class Alloc>
template<class InputIterator>
void vector<T, Alloc>::allocateAndCopy(InputIterator first, InputIterator last){
    start_ = dataAllocator::allocate(last - first);
    finish_ = TinySTL::uninitialized_copy(first, last, start_);
    endOfStorage_ = finish_;
}

vector_aux的整数版本会调用allocateAndFillN函数，后者同样是先分配n个元素的空间，然后调用uninitialized_fill_n函数给这n个空间填入相同的整数

// 整数版本
template<class T, class Alloc>
template<class Integer>
void vector<T, Alloc>::vector_aux(Integer n, const value_type& value, std::true_type){
    allocateAndFillN(n, value);
}

template<class T, class Alloc>
void vector<T, Alloc>::allocateAndFillN(const size_type n, const value_type& value){
    start_ = dataAllocator::allocate(n);
    TinySTL::uninitialized_fill_n(start_, n, value);
    finish_ = endOfStorage_ = start_ + n;
}

这里补充下uninitialized_fill_n函数的实现，内部根据value是否是POD调用不同版本的_uninitialized_fill_n_aux，当然这里都是整数了，肯定就是POD类型的，接着调用fill_n给这n个元素填充上x

// POD版本
template<class ForwardIterator, class Size, class T>
ForwardIterator _uninitialized_fill_n_aux(ForwardIterator first,
    Size n, const T& x, _true_type) {
    return fill_n(first, n, x);
}

template<class OutputIterator, class Size, class T>
OutputIterator fill_n(OutputIterator first, Size n, const T& value) {
    for (; n > 0; --n, ++first) {
        *first = value;
    }
    return first;
}

// 非POD版本
template<class ForwardIterator, class Size, class T>
ForwardIterator _uninitialized_fill_n_aux(ForwardIterator first, Size n, const T& x, _false_type) {
    int i = 0;
    for (; i != n; ++i) {
        construct((T*)(first + i), x);
    }
    return (first + i);
}

// 萃取value的型别
template<class ForwardIterator, class Size, class T>
inline ForwardIterator uninitialized_fill_n(ForwardIterator first,
    Size n, const T& x) {
    typedef typename _type_traits<T>::is_POD_type isPODType;
    return _uninitialized_fill_n_aux(first, n, x, isPODType());
}

4、拷贝构造函数

分为左值版本和右值版本，左值版本需要调用前面说过的allocateAndCopy函数，一个一个拷贝过来，右值版本则是直接接管资源

// 左值版本的拷贝构造
vector(const vector& v) {
    allocateAndCopy(v.start_, v.finish_);
}

// 右值版本的拷贝构造
vector(vector&& v) {
    start_ = v.start_;
    finish_ = v.finish_;
    endOfStorage_ = v.endOfStorage_;
    v.start_ = v.finish_ = v.endOfStorage_ = 0;
}

析构函数调用了destroyAndDeallocateAll函数，使用分配器把资源释放掉，先调用destroy释放有元素的空间，再调用deallocate释放分配了但没使用的空间

~vector() {
    destroyAndDeallocateAll();
}

template<class T, class Alloc>
void vector<T, Alloc>::destroyAndDeallocateAll(){
    if (capacity() != 0){
        dataAllocator::destroy(start_, finish_);
        dataAllocator::deallocate(start_, capacity());
    }
}

重载赋值运算符

左值和右值版本，左值版本还是调用allocateAndCopy函数，右值版本先调用destroyAndDeallocateAll把自身的资源析构掉，再接管给定的资源

vector& operator=(const vector& v) {
    if (this != &v) {
        destroyAndDeallocateAll();	// 得先把原来的资源释放掉
        allocateAndCopy(v.start_, v.finish_);
    }
    return *this;
}
vector& operator=(vector&& v) {
    if (this != &v) {
        destroyAndDeallocateAll();
        start_ = v.start_;
        finish_ = v.finish_;
        endOfStorage_ = v.endOfStorage_;
        v.start_ = v.finish_ = v.endOfStorage_ = 0;
    }
    return *this;
}

重载==、!=、[]运算符

!=直接把==取反就行

bool operator==(const vector& v) const {
    if (size() != v.size()){
        return false;
    } else {
        auto ptr1 = start_;
        auto ptr2 = v.start_;
        for (; ptr1 != finish_ && ptr2 != v.finish_; ++ptr1, ++ptr2){
            if (*ptr1 != *ptr2) return false;   // 只要一个不同就直接返回
        }
        return true;
    }
}
bool operator!=(const vector& v) const {
    return !(*this == v);
}

reference operator[](const difference_type i) { 
    return *(begin() + i); 
}

const_reference operator[](const difference_type i) const { 
    return *(cbegin() + i); 
}

常用简单函数

iterator begin(){ return (start_); }
const_iterator begin() const { return (start_); }
const_iterator cbegin() const { return (start_); }
iterator end() { return (finish_); }
const_iterator end() const { return (finish_); }
const_iterator cend() const { return (finish_); }
reverse_iterator rbegin() { return reverse_iterator(finish_); }
const_reverse_iterator crbegin() const { return const_reverse_iterator(finish_); }
reverse_iterator rend() { return reverse_iterator(start_); }
const_reverse_iterator crend() const { return const_reverse_iterator(start_); }


difference_type size() const { return finish_ - start_; }
difference_type capacity() const { return endOfStorage_ - start_; }
bool empty() const { return start_ == finish_; }

reference front() { return *(begin()); }
reference back() { return *(end() - 1); }
pointer data() { return start_; }

void clear() {
    dataAllocator::destroy(start_, finish_);
    finish_ = start_;
}
void swap(vector& v) {
    if (this != &v){
        TinySTL::swap(start_, v.start_);
        TinySTL::swap(finish_, v.finish_);
        TinySTL::swap(endOfStorage_, v.endOfStorage_);
    }
}
void push_back(const value_type& value) {
    insert(end(), value);
}
void pop_back() {
    --finish_;
    dataAllocator::destroy(finish_);
}

resize、reverse、shrink_to_fit

resize既修改capacity大小，也修改size大小，分成三种情况

  • n < size：调用分配器的destroy把[start_ + n, finish_)的元素析构掉
  • n > size && n <= capacity：把超过finish_的那几个元素都填充为val
  • n > capacity：分配新空间，然后把[begin,end)的元素拷贝过来，并且把多出来的赋默认值
void resize(size_type n, value_type val = value_type());

template<class T, class Alloc>
void vector<T, Alloc>::resize(size_type n, value_type val) {
    if (n < size()){
        dataAllocator::destroy(start_ + n, finish_);
        finish_ = start_ + n;
    } else if (n > size() && n <= capacity()){
        auto lengthOfInsert = n - size();
        finish_ = TinySTL::uninitialized_fill_n(finish_, lengthOfInsert, val);
    } else if (n > capacity()){
        auto lengthOfInsert = n - size();
        T *newStart = dataAllocator::allocate(getNewCapacity(lengthOfInsert));
        T *newFinish = TinySTL::uninitialized_copy(begin(), end(), newStart);
        newFinish = TinySTL::uninitialized_fill_n(newFinish, lengthOfInsert, val);

        destroyAndDeallocateAll();
        start_ = newStart;
        finish_ = newFinish;
        endOfStorage_ = start_ + n;
    }
}

reverse只修改capacity大小，不修改size大小
就是简单的重新分配n个空间，把元素拷贝过去，释放掉当前资源

void reserve(size_type n) {
    if (n <= capacity()) return;    // 不用分配新空间，也不去缩小
    T *newStart = dataAllocator::allocate(n);
    T *newFinish = TinySTL::uninitialized_copy(begin(), end(), newStart);
    destroyAndDeallocateAll();

    start_ = newStart;
    finish_ = newFinish;
    endOfStorage_ = start_ + n;
}

shrink_to_fit把没用到的那些空间释放掉，使得size=capacity

void shrink_to_fit() {
    //dataAllocator::deallocate(finish_, endOfStorage_ - finish_);
    //endOfStorage_ = finish_;  // 感觉这样就可以了，不需要分配新空间再拷贝
    T* t = (T*)dataAllocator::allocate(size());
    finish_ = TinySTL::uninitialized_copy(start_, finish_, t);
    dataAllocator::deallocate(start_, capacity());
    start_ = t;
    endOfStorage_ = finish_;
}

insert

insert有3个重载版本

  • 第一个版本是在迭代器的位置插入一个元素，内部调用了第二个版本的n=1的情况
  • 第二个版本是在迭代器的位置插入n个元素
iterator insert(iterator position, const value_type& val) {
    const auto index = position - begin();
    insert(position, 1, val);
    return begin() + index;
}
void insert(iterator position, const size_type& n, const value_type& val) {
    insert_aux(position, n, val, typename std::is_integral<size_type>::type());
}

之后又调用了insert_aux函数

  • 如果剩余空间够用就先把原有的元素往后移，留出空间再插入新元素
  • 否则重新分配空间并拷贝
// 整数版本
template<class T, class Alloc>
template<class Integer>
void vector<T, Alloc>::insert_aux(iterator position, Integer n, const value_type& value, std::true_type) {
    difference_type locationLeft = endOfStorage_ - finish_; // 剩余空间
    difference_type locationNeed = n;

    if (locationLeft >= locationNeed) {     // 如果剩余空间够用
        auto tempPtr = end() - 1;
        for (; tempPtr - position >= 0; --tempPtr){
            construct(tempPtr + locationNeed, *tempPtr);    // 先把原有元素往后移
        }
        TinySTL::uninitialized_fill_n(position, n, value);
        finish_ += locationNeed;
    } else {    // 需要重新分配空间
        reallocateAndFillN(position, n, value);
    }
}

reallocateAndFillN用于重新分配空间并填充元素

  • 先拷贝[begin, position)的元素到新空间
  • 再填充插入的n个元素
  • 最后拷贝[position, end)的元素
  • 释放掉原先的资源
template<class T, class Alloc>
void vector<T, Alloc>::reallocateAndFillN(iterator position, const size_type& n, const value_type& val){
    difference_type newCapacity = getNewCapacity(n);

    T *newStart = dataAllocator::allocate(newCapacity);
    T *newEndOfStorage = newStart + newCapacity;
    T *newFinish = TinySTL::uninitialized_copy(begin(), position, newStart);
    newFinish = TinySTL::uninitialized_fill_n(newFinish, n, val);
    newFinish = TinySTL::uninitialized_copy(position, end(), newFinish);

    destroyAndDeallocateAll();
    start_ = newStart;
    finish_ = newFinish;
    endOfStorage_ = newEndOfStorage;
}
  • 第三个版本是在迭代器的位置插入另一个容器的迭代器区间[first, end)
template <class InputIterator>
void insert(iterator position, InputIterator first, InputIterator last) {
    insert_aux(position, first, last, typename std::is_integral<InputIterator>::type());
}

调用了另一个版本的insert_aux

  • 如果剩余空间足够
    • 插入点之后的元素个数大于要插入的元素个数
      • 先把插入点之后的元素多余的后半部分拷贝到未使用的空间
      • 然后把前半部分采用从后往前填充式的拷贝到后面
      • 再把要要插入的元素拷贝到position的位置
    • 插入点之后的元素个数小于等于要插入的元素个数
      • 如果要插入的元素比[position, finish_)的元素多，就先把多的那后半部分些拷贝过来
      • 然后把[position, finish_)的元素拷贝到这些元素后面
      • 再把要插入元素剩下的前半部分拷贝到position位置
  • 剩余空间不够就重新分配空间
template<class T, class Alloc>
template<class InputIterator>
void vector<T, Alloc>::insert_aux(iterator position, InputIterator first， InputIterator last, std::false_type) {
    difference_type locationLeft = endOfStorage_ - finish_; // 剩下的空间
    difference_type locationNeed = distance(first, last);   // 需要的空间

    if (locationLeft >= locationNeed) { // 剩下的空间足够
        if (finish_ - position > locationNeed) {    // 插入点之后的元素个数大于要插入的元素个数
            TinySTL::uninitialized_copy(finish_ - locationNeed, finish_, finish_);
            std::copy_backward(position, finish_ - locationNeed, finish_);  // 从后往前填充式的拷贝
            std::copy(first, last, position);
        } else {    // 插入点之后的元素个数小于等于要插入的元素个数
            iterator temp = TinySTL::uninitialized_copy(first + (finish_ - position), last, finish_);
            TinySTL::uninitialized_copy(position, finish_, temp);
            std::copy(first, first + (finish_ - position), position);
        }
        finish_ += locationNeed;
    } else {
        reallocateAndCopy(position, first, last);
    }
}

reallocateAndCopy完成分配空间和拷贝

  • 先拷贝原先的[begin, position)
  • 再拷贝另一个容器的[first, last)
  • 最后拷贝原先的[position, end)
  • 并释放原先的空间
template<class T, class Alloc>
template<class InputIterator>
void vector<T, Alloc>::reallocateAndCopy(iterator position, InputIterator first, InputIterator last) {
    difference_type newCapacity = getNewCapacity(last - first);

    T *newStart = dataAllocator::allocate(newCapacity);
    T *newEndOfStorage = newStart + newCapacity;
    T *newFinish = TinySTL::uninitialized_copy(begin(), position, newStart);
    newFinish = TinySTL::uninitialized_copy(first, last, newFinish);
    newFinish = TinySTL::uninitialized_copy(position, end(), newFinish);

    destroyAndDeallocateAll();
    start_ = newStart;
    finish_ = newFinish;
    endOfStorage_ = newEndOfStorage;
}

分配空间前需要计算需要重新分配多少空间，所以需要调用getNewCapacity，并传入了需要增加的空间的数量len

  • 如果要len<=capacity，就让capacity翻倍
  • 否则返回capacity+len
template<class T, class Alloc>
typename vector<T, Alloc>::size_type vector<T, Alloc>::getNewCapacity(size_type len) const {
    size_type oldCapacity = endOfStorage_ - start_;
    auto res = TinySTL::max(oldCapacity, len);
    size_type newCapacity = (oldCapacity != 0 ? (oldCapacity + res) : len);
    return newCapacity;
}

erase

删除迭代器指向的区间，第一个版本调用了第二个版本

  • 把[last, end)的元素拷贝到first的位置，覆盖掉要删除的那些元素
  • [finish, last)的空间也没有释放掉，留着也没事，后面要用的话也是覆盖
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
template<class T, class Alloc>
typename vector<T, Alloc>::iterator vector<T, Alloc>::erase(iterator position) {
    return erase(position, position + 1);
}

template<class T, class Alloc>
typename vector<T, Alloc>::iterator vector<T, Alloc>::erase(iterator first, iterator last) {
    difference_type lenOfTail = end() - last;   // 计算[last,end)的个数
    difference_type lenOfRemoved = last - first;    // 要删除的个数
    finish_ = finish_ - lenOfRemoved;
    for (; lenOfTail != 0; --lenOfTail){
        auto temp = (last - lenOfRemoved);
        *temp = *(last++);
    }
    return (first);
}
文章作者: kunpeng
文章链接: http://example.com/2022/06/12/C-STL-4-2-vector/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 kunpeng !
STL
赏
  目录