做着做着发现需要有一个类似于C++ STL里面的vector那样的数据结构,但是本人比较懒,不想去搬STL的源代码重新编译了(估计又会一大堆error……),于是就自己写了个轻量级的vector。

这个vector的实现原理和STL中的vector类似,都采用了线性存储和动态表技术,并自动在capacity不足时分配2倍的新空间,然后把原空间的数据copy过去后释放原空间。不过出于对速度的考虑,我没有支持在数据规模减小到不足阈值时自动缩减空间以节约内存。根据算法导论中的平摊分析原理,该vector对于push_back操作的平均时间复杂度是O(1)。

该vector也支持insert和erase操作,可以随机增加和删除元素,不过时间复杂度就是O(n)了。

以下为完整的代码实现,可以直接拿去用:

#ifndef __VECTOR_H__
#define __VECTOR_H__

#include <malloc.h>

template<class T>
class vector
{
public:
    vector()
    {
        _capacity = 16;
        _pdata = (T*)malloc(_capacity*sizeof(T));
        _last = 0;
    }

    vector(int n)
    {
        _capacity = n - 1;
        _capacity |= _capacity >> 1;
        _capacity |= _capacity >> 2;
        _capacity |= _capacity >> 4;
        _capacity |= _capacity >> 8;
        _capacity |= _capacity >> 16;
        _capacity++;
        _pdata = (T*)malloc(_capacity*sizeof(T));
        _last = 0;
    }

    ~vector()
    {
        if (_pdata != NULL)
            free(_pdata);
    }

    int size() { return _last; }

    bool push_back(const T& x)
    {
        if (_capacity > _last + 1)
        {
            _pdata[_last] = x;
            _last++;
        }
        else
            return false;

        if (_capacity == _last + 1)    // reach the end, reallocate
            reallocate();

        return true;
    }

    void pop_back()
    {
        if (_last > 0)
            _last--;
    }

    bool insert(int index, const T& x)
    {
        if (_capacity > _last + 1)
        {
            memcpy(_pdata+index+1, _pdata+index, (_last-index)*sizeof(T));
            _pdata[index] = x;
            _last++;
        }
        else
            return false;

        if (_capacity == _last + 1)    // reach the end, reallocate
            reallocate();

        return true;
    }

    void erase(int index)
    {
        memcpy(_pdata+index, _pdata+index+1, (_last-index-1)*sizeof(T));
        _last--;
    }

    void clear()
    {
        _last = 0;
    }

    T& operator[](int index)
    {
        return _pdata[index];
    }

private:
    void reallocate()
    {
        _capacity = _capacity << 1;
        T* old = _pdata;
        _pdata = (T*)malloc(_capacity*sizeof(T));
        if (_pdata != NULL)
        {
            memcpy(_pdata, old, (_last+1)*sizeof(T));
            if (old != NULL)
                free(old);
        }
    }

    T* _pdata;
    int _capacity;
    int _last;
};

#endif

其中的malloc.h是PSP SDK自带的头文件,其中提供了malloc函数。

===========cotaku的分割线===========

竟然一坑就坑了小半年……不过这学期确实够忙就是了,选了三门BT课啊T_T

下次真的可以开始探讨矩阵变换了……不过貌似已经快忘光了(拖走)

» 转载请注明来源及链接:未来代码研究所

Related Posts:

Leave a Reply

World Line
Time Machine
Friendly Links
Online Tools