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

目錄

C++里面的容器是怎么實現(xiàn)的呢？我們先不防自己寫一個vector試一下。
要實現(xiàn)vector機制，主要要考慮下面幾點

（1） 能夠動態(tài)擴容。
（2） 能夠通過下標取值。
（3） 能夠通過迭代器進行循環(huán)。

首先考慮（1）和（2），其實現(xiàn)非常簡單：

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）擴縮容時內(nèi)存的移動。
（3）刪除元素時，數(shù)組的重排列。

此實現(xiàn)幾乎沒有什么難度。下一節(jié)中將討論迭代器如何實現(xiàn)，這樣就能利用STL的所有算法了。

后一章
目錄