上一章：智能指针之使用 (3)

目录

C++里面的容器是怎么实现的呢？我们先不防自己写一个vector试一下。
要实现vector机制，主要要考虑下面几点

（1） 能够动态扩容。
（2） 能够通过下标取值。
（3） 能够通过迭代器进行循环。

首先考虑（1）和（2），其实现非常简单：

template<typename T>
class MyVector
{
    uint32_t capacity_;
    uint32_t length_;
    T* array_;
public:
    MyVector()
        :  capacity_(2), length_(0), array_(new T[capacity_])
    {}
    void push_back(const T& v)
    {
        if (length_ == capacity_)
        {
            extend();
        }
        array_[length_] = v;
        ++length_;
    }

    void remove(const T& v)
    {
        unsigned newIndex = 0;
        for (uint32_t i = 0; i < length_; ++i)
        {
            if (array_[i] == v)
            {
                continue;
            }

            if (newIndex != i)
            {
                array_[newIndex] = array_[i];
            }
            ++newIndex;
        }

        length_ = newIndex;
        if (length_ <= capacity_ / 3)
        {
            shrink();
        }
    }

    uint32_t size() const
    {
        return length_;
    }

    const T& operator[] (uint32_t index)
    {
        return array_[index];
    }

private:
    inline void extend()
    {
        capacity_ = 2 * capacity_;
        rellocate(capacity_);
    }

    inline void shrink()
    {
        if (capacity_ <= 2)
        {
            return ;
        }
        capacity_ = capacity_ / 2;
        rellocate(capacity_);
    }

    inline void rellocate(uint32_t size)
    {
        T* temp = new T[size];
        std::memcpy(temp, array_, sizeof(T) * length_);
        delete [] array_;
        array_ = temp;
    }
};

其中要注意的几个点是：

（1）扩容和缩容时的算法。
（2）扩缩容时内存的移动。
（3）删除元素时，数组的重排列。

此实现几乎没有什么难度。下一节中将讨论迭代器如何实现，这样就能利用STL的所有算法了。

后一章
目录