自定义数据结构（C++）-创新互联

1. 动态数组

#includetemplateclass MyVector
{
    T* m_p;
    int m_capacity;
    int m_size;

public:
    // 构造函数
    explicit MyVector() :m_p(NULL), m_capacity(0), m_size(0) {}
    explicit MyVector(int capacity) 
        :m_p(NULL), m_size(0) 
    {
        m_capacity = std::max(0, capacity);
    }
    explicit MyVector(int size, const T& value)
        :m_capacity(size), m_size(size)
    {
        m_size = std::max(0, size);

        m_p = new T[m_capacity];
        for (int i = 0; i< m_size; ++i)
            m_p[i] = value;
    }
    MyVector(const MyVector& myVector)
    {
        Ctor_Helper(myVector);
    }
    void operator=(const MyVector& myVector)
    {
        Ctor_Helper(myVector);
    }

    // 析构函数
    virtual ~MyVector()
    {
        if (m_p != NULL)
            delete[] m_p;
    }

    int Capacity()
    {
        return m_capacity;
    }

    int Size()
    {
        return m_size;
    }

    void Reserve(int newCapacity) // 新容量大小不能小于数据个数
    {
        bool paramsIsValid = (0<= newCapacity && m_size<= newCapacity);
        (!!paramsIsValid) || std::cout<< "(错误)第"<< __LINE__<< "行: "<< "Reserve操作, 无效参数\n";
        if (!paramsIsValid) return;

        if (m_capacity == 0)
        {
            m_capacity = newCapacity;
            m_p = new T[m_capacity];
        }
        else
        {
            m_capacity = newCapacity;
            T* tmp_p = new T[m_capacity];
            memcpy(tmp_p, m_p, m_size * sizeof(T));
            delete[] m_p;
            m_p = tmp_p;
        }
    }

    bool Empty()
    {
        return m_size == 0;
    }

    void Print()
    {
        for (int i = 0; i< m_size; ++i)
            std::cout<< m_p[i]<< ' ';
        std::cout<< '\n';
    }

    T& operator[](int idx)
    {
        bool paramsIsValid = (0<= idx && idx< m_size);
        (!!paramsIsValid) || std::cout<< "(错误)第"<< __LINE__<< "行: "<< "[]操作, 下标越界\n";
        if (!paramsIsValid) exit(1);
        return m_p[idx];
    }
    const T& operator[](int idx) const
    {
        bool paramsIsValid = (0<= idx && idx< m_size);
        (!!paramsIsValid) || std::cout<< "(错误)第"<< __LINE__<< "行: "<< "[]操作, 下标越界\n";
        if (!paramsIsValid) exit(1);

        return m_p[idx];
    }

    void Insert(int idx, const MyVector& otherVector, int otherIdx, int cnt)
    {
        Insert_Helper(idx, cnt);

        for (int i = 0; i< cnt; ++i)
            m_p[idx + i] = otherVector[otherIdx + i];
    }
    void Insert(int idx, const MyVector& otherVector, int otherIdx)
    {
        Insert_Helper(idx, otherVector.m_size);
    }
    void Insert(int idx, int cnt, const T& value)
    {
        Insert_Helper(idx, cnt);

        for (int i = 0; i< cnt; ++i)
            m_p[idx + i] = value;
    }
    void Insert(int idx, const T& value)
    {
        Insert(idx, 1, value);
    }
    void Insert(const T& value)
    {
        Insert(m_size, 1, value);
    }

    void Remove(int idx, int cnt)
    {
        bool paramsIsValid = (0<= idx && cnt >= 1 && idx + cnt - 1< m_size);
        (!!paramsIsValid) || std::cout<< "(错误)第"<< __LINE__<< "行: "<< "Remove操作, 无效参数\n";
        if (!paramsIsValid) return;

        for (int i = idx + cnt; i< m_size; ++i)
            m_p[i - cnt] = m_p[i];
        m_size -= cnt;
    }
    void Remove(int idx)
    {
        Remove(idx, 1);
    }
    void Remove() // 移除一个尾部元素
    {
        Remove(m_size - 1, 1);
    }
    void Clear()
    {
        m_size = 0;
    }

private:
    void Ctor_Helper(const MyVector& myVector)
    {
        if (m_p != NULL)
            delete[] m_p;

        m_capacity = myVector.m_capacity;
        m_size = myVector.m_size;
        m_p = new T[m_capacity];
        memcpy(m_p, myVector.m_p, m_size * sizeof(T));
    }
    void Insert_Helper(int idx, int cnt)
    {
        bool paramsIsValid = (0<= idx && cnt >= 1 && idx<= m_size && INT32_MAX - m_size >= cnt);
        (!!paramsIsValid) || std::cout<< "(错误)第"<< __LINE__<< "行: "<< "Insert操作, 无效参数\n";
        if (!paramsIsValid || m_capacity == INT32_MAX) return;

        m_size += cnt;
        if (m_capacity == 0)
        {
            m_capacity = m_size;
            m_p = new T[m_capacity];
        }
        else
        {
            bool addCapacity = false;
            while (m_size >m_capacity)
            {
                int tmp = (m_capacity<< 1);
                if (tmp >m_capacity)
                    m_capacity = tmp;
                else
                    m_capacity = INT32_MAX;

                addCapacity = true;
            }
            if (addCapacity)
            {
                T* tmp_p = new T[m_capacity];
                memcpy(tmp_p, m_p, m_size * sizeof(T));
                delete[] m_p;
                m_p = tmp_p;
            }

            // 从p[idx]到p[m_size - cnt - 1]的所有元素后移cnt位
            for (int i = idx; i< m_size - cnt; ++i)
                m_p[i + cnt] = m_p[i];
        }
    }
};

int main()
{
    MyVectormyVector;

    std::cout<< myVector[-1]<< '\n';
    myVector.Print();
}

  上面程序中[ ]操作下标越界，会直接终止程序(exit(1))。

创新互联 - 托管服务器，四川服务器租用，成都服务器租用，四川网通托管,绵阳服务器托管，德阳服务器托管，遂宁服务器托管，绵阳服务器托管，四川云主机，成都云主机，西南云主机，托管服务器，西南服务器托管，四川/成都大带宽，服务器机柜，四川老牌ＩＤＣ服务商

  用下面的变量来存储T类型的默认值，可以只中断函数不中断程序，但会耗费更多的内存，如果在m_p不为NULL时释放tDefaultValue的内存则会耗费更多的时间。

...代码...
templateclass MyVector
{
    T* m_p;
    int m_capacity;
    int m_size;
    T* tDefaultValue = new T[1]{}; // 存储T类型的默认值
    ...代码...
    T& operator[](int idx)
    {
        bool paramsIsValid = (0<= idx && idx< m_size);
        (!!paramsIsValid) || std::cout<< "(错误)第"<< __LINE__<< "行: "<< "[]操作, 下标越界\n";
        if (!paramsIsValid) return tDefaultValue[0];
        return m_p[idx];
    }
    ...代码...
};
...代码...

安全性与性能，空间与时间，需要在设计的时候进行权衡。

例如：在重载[ ]操作的函数中，我们检测了参数无效的情况，并输出错误提示，[ ]操作函数提前中断；有参构造函数中，我们直接处理了参数无效的情况，没有输出错误提示。而引入tDefaultValue变量可以防止因为一个BUG而导致整个程序跑不起来(虽然并不是一定能成功……)。

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文名称：自定义数据结构（C++）-创新互联
分享URL：http://bzwzjz.com/article/dpeiso.html