Free2000fly's Official Blog

工作中使用 STL 的 vector , set, map, deque 等容器很方便, 很稳定, 但在我的一个关键任务中, 对性能要求特高, 使用 STL 组件将使系统不堪重负.
因此自己写了一个动态数组的 C++ 模板类. 性能的提升效果明显. 下面是源码:

#ifndef __ARRAY_DYNAMIC_H__
#define __ARRAY_DYNAMIC_H__ 1

#pragma once

namespace sage_util {

template<typename T> class ArrayDynamic
{
public:
    ArrayDynamic(unsigned int a_alloc_size = 0)
        : m_used_room (0)
        , m_alloc_size(a_alloc_size)
        , m_pArray (NULL)
    {
        if (m_alloc_size > 0)
        {
            m_pArray = (T*) malloc(sizeof(T) * m_alloc_size);
            if (NULL == m_pArray) {
                m_alloc_size = 0;
            }
        }
    }

    // copy Constructors
    ArrayDynamic(const ArrayDynamic & rhs)
    {
        *this = rhs;
    }

    ~ArrayDynamic()
    {
        clear();
    }

    //=====================================================================

    ArrayDynamic & operator= (const ArrayDynamic & rhs)
    {
        if (this != &rhs)
        {
            clear();
            m_alloc_size = rhs.m_alloc_size;

            if (m_alloc_size)
            {
                m_pArray = (T*) malloc(sizeof(T) * m_alloc_size);

                if (NULL == m_pArray) {
                    m_alloc_size = 0;
                } else {
                    m_used_room = rhs.m_used_room;
                    if (m_used_room) {
                        memcpy(m_pArray, rhs.m_pArray, m_used_room * sizeof(T));
                    }
                }
            }
        }
        return (*this);
    }

    //=====================================================================

    void clear()
    {
        if (m_pArray) {
            free(m_pArray);
            m_pArray = NULL;
        }
        m_alloc_size = 0;
        m_used_room = 0;
    }

    bool push_back(const T & m)        // 推入一个数组元素
    {
        bool bResult = false;

        if (false == (bResult = _expend_space())) {
            return bResult;
        }

        *(m_pArray + m_used_room) = m;

        m_used_room++;

        bResult = true;

        return bResult;
    }

    unsigned int size()            // 得到数组大小
    {
        return m_used_room;
    }

    bool remove(unsigned int nIndex)            // 删除第 nIndex 个元素
    {
        bool bResult = false;

        if((nIndex + 1) <= m_used_room )
        {
            memmove(m_pArray+nIndex, m_pArray + (nIndex+1), sizeof(T)*(m_used_room-(nIndex+1)));
            m_used_room -= 1;
            bResult = true;
        }
        return bResult;
    }

    bool insert(unsigned int & nPos, const T & element)        // 插入一个元素
    {
        bool bResult = false;

        if (false == (bResult = _expend_space())) {
            return bResult;
        }

        if ((nPos + 1) > m_used_room) {
            nPos = m_used_room; // m_used_room ? m_used_room-1 : 0;
        }

        m_used_room ++;
        memmove(m_pArray+(nPos+1), m_pArray+nPos, sizeof(T)*(m_used_room-(nPos+1)));
        *(m_pArray+nPos)=element;

        bResult = true;

        return bResult;
    }

    //=====================================================================

    T & operator[](unsigned int pos)
    {
        return (*(begin() + pos));
    }

    const T & operator[](unsigned int pos) const
    {
        return (*(begin() + pos));
    }

    //=====================================================================

    const T* query(unsigned int nIndex) const               // 查询第 nIndex 个元素的值
    {
        return const_cast<const T *> query(nIndex);
    }

    T* query(unsigned int nIndex)                // 查询第 nIndex 个元素的值
    {
        T * pResult = NULL;
        if ( (nIndex + 1) <= m_used_room ) {
            pResult = m_pArray + nIndex;
        }
        return pResult;
    }

    //=====================================================================

    const T* begin() const
    {
        return (const T*)(m_pArray);
    }

    T* begin()
    {
        return m_pArray;
    }

    //=====================================================================

    const T* end() const
    {
        return (const T*)(m_pArray + m_used_room);
    }

    T* end()
    {
        return (m_pArray + m_used_room);
    }

    //=========================================================

    const T* rbegin() const
    {
        return const_cast<const T*> rbegin();
    }

    T* rbegin()
    {
        return (m_pArray + (m_used_room ? (m_used_room-1) : 0));
    }

    //=====================================================================

    const T* rend() const
    {
        return const_cast<const T*>rend();
    }

    T* rend()
    {
        return m_used_room ? m_pArray-1 : m_pArray;
    }

protected:
    bool _expend_space()
    {
        bool bResult = false;

        if (m_used_room >= m_alloc_size)
        {
            T * pTmp = NULL;
            unsigned int nTmp = (m_alloc_size ? m_alloc_size : 1 ) * 2;

            pTmp = (T*) realloc(m_pArray, sizeof(T) * nTmp);

            if (pTmp) {
                m_alloc_size = nTmp;
                m_pArray = pTmp;
                bResult = true;
            }
        }
        return bResult;
    }

protected:
    T * m_pArray;                   // 定义动态数组
    unsigned int m_used_room;       // 已用空间
    unsigned int m_alloc_size;      // 存储空间大小的值
};

} ; // namespace sage_util

#endif  // __ARRAY_DYNAMIC_H__

使用方法也很简单, 下面是示例:

#include<iostream>

using namespace std;

void main()
{
    ArrayDynamic<int> intArray;
    intArray.push_back(1);
    intArray.push_back(2);
    intArray.push_back(3);
    intArray.push_back(4);
    intArray.push_back(5);
    intArray.push_back(6);
    intArray.push_back(7);
    intArray.push_back(8);
    intArray.push_back(9);

    intArray.remove(3);
    cout<<intArray.begin()<<endl;
    cout<<intArray.end()<<endl;
    int* ite=NULL;
    for(ite=intArray.begin(); ite!=intArray.end(); ite++)
    {
        printf("%d ",*ite);
    }
    printf("\n");

    intArray.remove(7);
    cout<<intArray.begin()<<endl;
    cout<<intArray.end()<<endl;
    for(ite=intArray.begin(); ite!=intArray.end(); ite++)
    {
        printf("%d ",*ite);
    }

    printf("\n");

    for(ite=intArray.rbegin(); ite!=intArray.rend(); ite--)
    {
        printf("%d ", *ite);
    }
    printf("\n");

    intArray.clear();

    unsigned int ntm = 0;
    intArray.insert(ntm, 888);

    ntm = 0;
    intArray.insert(ntm, 999);

    ntm = 0;
    intArray.insert(ntm, 111);

    intArray[2] = 4;

    printf("%d \n", intArray[2]);

    for(ite=intArray.begin(); ite!=intArray.end(); ite++)
    {
        printf("%d ", *ite);
    }
    printf("\n");
}

以下测试代码

#include<iostream>
#include <windows.h>
#include <vector>

#include "arraydynamic.h"

using namespace std;
using namespace sage_util;

#define REPEAT_COUNT 100000000

void main()
{
    DWORD dwStart = 0;
    int i = 0;

    {
        // 用于预分配内存, 使得有足够的 cache, 以利公平
        vector<int> vint;
        vint.reserve(REPEAT_COUNT);
        vint.push_back(1);
    }

    cout << "\n============================" << endl;

    {
        ArrayDynamic<int> intArray(REPEAT_COUNT);
        dwStart = GetTickCount();
        for ( i = 0; i < REPEAT_COUNT; i ++)
            intArray.push_back(i);
        cout << GetTickCount() - dwStart << endl;
    }

    {
        vector<int> vint;
        vint.reserve(REPEAT_COUNT);
        dwStart = GetTickCount();
        for (i = 0; i < REPEAT_COUNT; i ++)
            vint.push_back(i);
        cout << GetTickCount() - dwStart << endl;
    }

    cout << "============================" << endl;
}

得到的结果为:

free2000fly 技术心得