C++ STL中vector的实现

STL是C++的精髓，其中的vector又是用的最广的一种容器。下面介绍一下vector的一种简单实现（这里参考了Mark Weiss的数据结构C++实现一书），废话不多说，直接上代码，

#include "stdafx.h"
#include <iostream>
#include <string>

using namespace std;

template <typename Object>
class Vector
{
public:
    explicit Vector(int initSize = 0) : theSize(initSize), theCapacity(initSize+SPARE_CAPACITY)
    {
        objects = new Object[theCapacity];
    }
    Vector(const Vector & rhs) : objects(NULL)
    {
        operator=(rhs);
    }
    ~Vector()
    {
        delete [] objects;
    }

    const Vector & operator=(const Vector & rhs)
    {
        if (this != &rhs)
        {
            delete [] objects;
            theSize = rhs.size();
            theCapacity = rhs.theCapacity;

            objects = new Object[capacity()];
            for (int k = 0; k < size(); k++)
                objects[k] = rhs.objects[k];
        }
        return *this;
    }
    void resize(int newSize)
    {
        if (newSize > theCapacity)
            reserve(newSize*2+1);
        theSize = newSize;
    }
    void reserve(int newCapacity)
    {
        if (newCapacity < theCapacity)
            return;

        Object * oldArray = objects;
        objects = new Object[newCapacity];
        for (int k = 0; k < theSize; k++)
            objects[k] = oldArray[k];

        theCapacity = newCapacity;
        delete [] oldArray;
    }

    Object * operator[](int index)
    {
        return objects[index];
    }
    const Object & operator[](int index) const
    {
        return objects[index];
    }
    bool empty() const
    {
        return size() == 0;
    }
    int size() const
    {
        return theSize;
    }
    int capacity() const
    {
        return theCapacity;
    }

    void push_back(const Object & x)
    {
        if (theSize == theCapacity)
            reserve(2*theCapacity+1);
        objects[theSize++] = x;
    }

    void pop_back()
    {
        theSize--;
    }

    const Object & back() const
    {
        return objects[theSize-1];
    }

    typedef Object * iterator;
    typedef const Object * const_iterator;

    iterator begin()
    {
        return &objects[0];
    }

    const_iterator begin() const
    {
        return &objects[0];
    }

    iterator end()
    {
        return &objects[theSize];
    }

    const_iterator end() const
    {
        return &objects[theSize];
    }

    enum
    {
        SPARE_CAPACITY = 16
    };

private:
    int theSize;
    int theCapacity;
    Object * objects;
};

int _tmain(int argc, _TCHAR* argv[])
{
    Vector<string> aVec;
    aVec.push_back("hello");
    aVec.push_back("my name is Lily");
    aVec.push_back("I hope we'll be friends");
    aVec.push_back("Thanks");
    Vector<string>::iterator iter = aVec.begin();
    while (iter != aVec.end())
        cout << *iter++ << endl;
    return 0;
}

先从vector的private成员变量说起，定义theSize，即size()的返回值，该值表明了vector的size大小；theCapacity，即vector的容量，注意它与size不是一个概念，size是指一个容器里面装了多少元素，capacity指该容器目前占用的内存能容纳多少元素，但未必里面就有那么多元素，可能capacity非常大，但size很小；objects指针里面存放的是vector分配内存的地址。当定义一个空的vector时，capacity是多少？在这里是16，请见code的120行定义的SPARE_CAPACITY，以及11行的构造函数，当未指定initSize的时候，我们new一个SPARE_CAPACITY的数组，用来存放Object对象。
下一个需要关注的函数是第44行的reserve()，reserve就是指定vector去分配一个指定大小的内存，当然如果这个指定的大小小于当前vector的capacity，那我们就什么都不做，如果大于当前capacity，我们先new一个new capacity的内存，然后把vector当前保存的元素拷贝到新new的内存中，最后删除之前分配的内存（注意删除数组要用delete [] p的形式，否则会发生内存泄漏）。
接下来我们来看一下迭代器的定义，我们这里把iterator直接定义为指向Object的指针，然后再定义begin(), end()等函数，这几个函数都很简单，直接返回&objects[x]即可。
最后我们看代码79行push_back的定义，这个函数是vector使用者用的最多的操作之一，实现push_back时要考虑vector容量是否已满的情况，如果容量已满，即theSize与theCapacity相等，则reserve一个2倍的capacity加1即可。在这里理论上只要reserve的容量大于当前capacity，那reserve多大的内存都可以，但是如果reserve的内存过小（比如每次只增加一个Object大小的内存，那么以后每次push_back操作都会引起reserve操作，而reserve操作是要涉及new delete动作的，频繁进行会非常耗时），所以一般每次容量已满的话都reserve一个2倍的当前capacity的大小是理想的方法。
测试程序非常简单，定义一个装string对象的vector，然后进行push_back，最后打印出来，显示如下，

hello
my name is Lily
I hope we'll be friends
Thanks

写一个vector对理解C++ STL绝对是非常有帮助的，看似简单的一个vector实际上里面涉及了C++的模板，重载等概念，对于一个C++的新手来说，能写对这些语法并且通过编译就不是一件容易的事，所以学习软件编程最好的方法还是写一些实实在在的程序，大有裨益。