关于土豆哥
一只文艺型码农
自定义模板类实现比std::vector更强大的动态数组
自定义模板类实现比std::vector更强大的动态数组

最近闲的没事打算复习下C++,于是写了这么个类。功能上基本和标准库中的vector相似,又多加了几个功能,更加实用一些。因为用了模板类,所以和vector一样,兼容包括自定义类型在内的所有数据类型。

此项目已发布在github,如果有更好的方法欢迎fork和修改~

基本结构

整个实现采用链表的数据结构,因此数组每个元素(链表每个节点)除了数据域以外还需要有两个指针域分别指向前后节点。我将每个节点定义为一个模板类Element。当然这里也可以用struct,但是相比于struct,我更偏爱类。

template <class T> class Element
{
private:
    T content;
    Element *next;
    Element *prev;
public:
    friend class Chain <T>;
    friend class std::ostream;
};

整个动态数组定义为另一个模板类Chain,并将Chain声明为Element类的友元类,因为Element类没有提供公有函数作为接口,所以要将Chain定义为友元类才可以访问Element的私有成员。下面是Chain类的定义。

template <class T> class Chain
{
private:
    Element <T> *first;
    Element <T> *last;
public:
    Chain();
    Chain(const Chain <T> & chain);
    ~Chain();
    void add_front(T input);
    void add_back(T input);
    void del_front();
    void del_back();
    void del(int n);
    void insert(int n, T input);
    void replace(int n, T input);
    void sort(bool(*compare)(T, T));
    void sort();
    void clear();
    void print();
    int count();
    int lookup(T input);
    void operator=(const Chain <T> & chain);
    bool operator==(Chain <T> & chain);
    bool operator!=(Chain <T> & chain);
    T & operator[](int n);
};

从类定义可以看到,这个数组有一个头指针一个尾指针,这两个指针不存储数组内容,并且在构造时被创建。这个动态数组实现了从前后添加和删除元素、删除指定元素、插入元素、替换元素、给类内元素排序、清空数组、输出数组、数组计数、查找指定元素的功能,并能够进行赋值、拷贝构造、比较以及下标访问。

各函数实现

构造函数

构造函数的实现相对简单,只需要创建头尾指针即可。

template<class T>
Chain<T>::Chain()
{
    first = new Element <T>;
    last = new Element <T>;
    first->next = last;
    first->prev = nullptr;
    last->prev = first;
    last->next = nullptr;
}

添加元素

添加元素的函数的思路是先使用new命令创建一个新的Element对象,然后调整Element的指针指向和现有数组元素的指针指向。

//从前插入元素
template<class T>
void Chain<T>::add_front(T input)
{
    Element <T> *tmp = new Element <T>;
    tmp->prev = first;
    tmp->next = first->next;
    tmp->content = input;
    first->next->prev = tmp;
    first->next = tmp;
}
//从后插入元素
template<class T>
void Chain<T>::add_back(T input)
{
    Element <T> *tmp = new Element <T>;
    tmp->prev = last->prev;
    tmp->next = last;
    tmp->content = input;
    last->prev->next = tmp;
    last->prev = tmp;
}

这里需要注意的是,调整指针指向的顺序必须注意。比如,如果在从前插入函数中先将first->next设为tmp,那么就没有指针指向原先的第一个元素了,此时我们就无法完成这个函数。所以,这个调整指针指向的过程,应该先调整tmp的前后指针,再调整原有元素的指针。

从前后删除元素

从前后删除元素的函数和添加函数类似,也需要一个tmp指针来完成。不过这里的tmp指针不需要用new申请新的内存,而是直接将要删除的元素赋给了tmp,之后调整tmp前后元素的指针指向即可。

//从前删除
template<class T>
void Chain<T>::del_front()
{
    if (first->next->next == nullptr)
    {
        return;
    }
    Element <T> *tmp = first->next;
    tmp->next->prev = first;
    first->next = tmp->next;
    delete tmp;
}
//从后删除
template<class T>
void Chain<T>::del_back()
{
    if (first->next->next == nullptr)
    {
        return;
    }
    Element <T> *tmp = last->prev;
    tmp->prev->next = last;
    last->prev = tmp->prev;
    delete tmp;
}

删除指定元素

删除指定元素和从前后删除元素类似,不同的是需要一个int型变量来计数以便找到指定的元素。

template<class T>
void Chain<T>::del(int n)
{
    Element <T> *current = first;
    for (int i = 0; i <= n; i++)
    {
        if (current->next->next == nullptr)
        {
            return;
        }
        current = current->next;
    }
    current->next->prev = current->prev;
    current->prev->next = current->next;
    delete current;
}

插入元素到指定位置

也和从前后插入元素以及删除元素类似,另外需要一个用于计数的int型变量。

template<class T>
void Chain<T>::insert(int n, T input)
{
    Element <T> *current = first;
    Element <T> *tmp = new Element <T>;
    for (int i = 0; i < n; i++)
    {
        if (current->next->next == nullptr)
        {
            tmp->prev = last->prev;
            tmp->next = last;
            tmp->content = input;
            last->prev->next = tmp;
            last->prev = tmp;
            return;
        }
        current = current->next;
    }
    tmp->prev = current;
    tmp->next = current->next;
    tmp->content = input;
    current->next->prev = tmp;
    current->next = tmp;
}

替换元素

替换元素更简单,只需要定位并赋值,还省去了调整指针的步骤。

template<class T>
void Chain<T>::replace(int n, T input)
{
    Element <T> *current = first;
    for (int i = 0; i <= n; i++)
    {
        if (current->next == nullptr)
        {
            return;
        }
        current = current->next;
    }
    current->content = input;
}

计数函数

用一个int型变量计数并遍历整个数组。

template<class T>
int Chain<T>::count()
{
    int n=0;
    Element <T> *current = first->next;
    while (current->next != nullptr)
    {
        current = current->next;
        n++;
    }
    return n;
}

查找函数

与计数函数类似,多一个比较的过程,返回值查找元素的下标,如果找不到就返回-1。

template<class T>
int Chain<T>::lookup(T input)
{
    int n = 0;
    Element <T> *current = first->next;
    while (current->next != nullptr)
    {
        if (current->content == input)
        {
            return n;
        }
        n++;
        current = current->next;
    }
    return -1;
}

需要注意的是,当这个动态数组被实例化为可比较的数据类型(也就是T类型可比较)时,这一函数才可用。如果想要为自己的自定义数据类型创建一个动态数组并实现查找功能,需要给自己的类重载==运算符。

输出函数

遍历数组并用iostream的cout打印在屏幕上。调用的前提是T类型可以被cout。

template<class T>
void Chain<T>::print()
{
    Element <T> *current = first->next;
    while (current->next != nullptr)
    {
        std::cout << current->content << ' ';
        current = current->next;
    }
    std::cout << endl;
}

清空函数

依然是遍历整个数组,不过稍复杂,需要不断创建临时变量并释放,直到数组只剩下first和last。

template<class T>
void Chain<T>::clear()
{
    while (first->next->next != nullptr)
    {
        Element <T> *tmp = first;
        first = first->next;
        delete tmp;
    }
}

析构函数

析构函数和清空函数几乎一样,不过first和last也要释放。

template<class T>
Chain<T>::~Chain()
{
    while (first->next->next != nullptr)
    {
        Element <T> *tmp = first;
        first = first->next;
        delete tmp;
    }
    delete first;
    delete last;
}

排序函数

因为对于链表而言,遍历比下标访问更方便,所以这里使用的是冒泡排序。

//自定义比较函数作为传入参数
template<class T>
void Chain<T>::sort(bool(*compare)(T, T))
{
    Element <T> *front = first->next;
    if (front->next == nullptr)
    {
        return;
    }
    while (front->next->next != nullptr)
    {
        Element <T> *back = front;
        while (back->prev != nullptr)
        {
            if (compare(back->content, back->next->content))
            {
                T tmp;
                tmp = back->content;
                back->content = back->next->content;
                back->next->content = tmp;
            }
            back = back->prev;
        }
        front = front->next;
    }
}
//无参数
template<class T>
void Chain<T>::sort()
{
    Element <T> *front = first->next;
    if (front->next == nullptr)
    {
        return;
    }
    while (front->next->next != nullptr)
    {
        Element <T> *back = front;
        while (back->prev != nullptr)
        {
            if (back->content > back->next->content)
            {
                T tmp;
                tmp = back->content;
                back->content = back->next->content;
                back->next->content = tmp;
            }
            back = back->prev;
        }
        front = front->next;
    }
}

这里定义了一个无参数的,一个以自定义比较函数作为参数的。当调用无参数排序函数时,会调用T类型的>运算符,所以必须保证T类型的>运算符可用。

下标访问

数组的基本功能之一,通过重载[]运算符实现。和计数函数几乎一样,但返回值是该元素内容的引用。

template<class T>
T & Chain<T>::operator[](int n)
{
    Element <T> *current = first;
    for (int i = 0; i <= n; i++)
    {
        if (current->next->next == nullptr)
        {
            return current->content;
        }
        current = current->next;
    }
    return current->content;
}

注意,这个函数的返回值必须是引用类型T&而不是普通类型T,否则通过下标访问对数组元素进行的修改都没有作用。

比较函数

重载==和!=运算符实现比较。只有当两个数组元素数相同且每个元素都相同时才判定为两个数组相同。

template<class T>
bool Chain<T>::operator==(Chain <T>& chain)
{
    if (this->count() != chain.count())
    {
        return false;
    }
    Element <T> *left = first->next;
    Element <T> *right = chain.first->next;
    while (left->next != nullptr)
    {
        if (left->content != right->content)
        {
            return false;
        }
        left = left->next;
        right = right->next;
    }
    return true;
}

template<class T>
bool Chain<T>::operator!=(Chain<T>& chain)
{
    if (this->count() != chain.count())
    {
        return true;
    }
    Element <T> *left = first->next;
    Element <T> *right = chain.first->next;
    while (left->next != nullptr)
    {
        if (left->content != right->content)
        {
            return true;
        }
        left = left->next;
        right = right->next;
    }
    return false;
}

T类型本身必须可以比较才能执行本函数,也就是说T类型的==和!=必须是有效的。

赋值函数

将另一个数组的值完整赋给本数组。原理是先清空,然后遍历另一个数组,把另一个数组每一个元素依次添加到本数组后面。

template<class T>
void Chain<T>::operator=(const Chain<T>& chain)
{
    this->clear();
    Element <T> *source = chain.first->next;
    Element <T> *current = first;
    while (source->next != nullptr)
    {
        Element <T> *tmp = new Element <T>;
        tmp->content = source->content;
        current->next = tmp;
        current = tmp;
        source = source->next;
    }
    current->next = last;
    last->prev = current;
}

拷贝构造函数

如果我们不定义拷贝构造函数,程序照样可以运行,但是有时会出现严重的问题。考虑下面的情况:

Chain <char> *a = new Chain <char>;
a->add_back('a');
Chain <char> b = *a;
delete a;
cout << b[0];

如果我们定义了拷贝构造函数,当然没有问题。但是如果不定义拷贝构造函数,这段代码运行时会报错。因为在编译时,编译器会创建一个默认的浅拷贝构造函数,当运行Chain <char> b = *a;时,默认拷贝构造函数会被用于创建b对象。但是,此时的b数组的元素并不独立占有内存,只是一个指向a数组元素的指针。当a被delete之后,数组b实际上已经被析构了。所以,我们必须自定义深拷贝构造函数,为b申请内存实现深拷贝。

template<class T>
Chain<T>::Chain(const Chain<T> & chain)
{
    first = new Element <T>;
    last = new Element <T>;
    first->next = last;
    first->prev = nullptr;
    last->prev = first;
    last->next = nullptr;
    Element <T> *source = chain.first->next;
    Element <T> *current = first;
    while (source->next != nullptr)
    {
        Element <T> *tmp = new Element <T>;
        tmp->content = source->content;
        current->next = tmp;
        current = tmp;
        source = source->next;
    }
    current->next = last;
    last->prev = current;
}

输出操作符重载

通过重载<<操作符,可以让你的整个数组能够被cout,使用更加方便。不过这个函数并不是Chain类的成员函数,而是ostream类的函数重载,因此需要注意访问权限的问题。在下面的代码中,所调用的全部是Chain类的公有成员函数。

template<class T>
std::ostream& operator<<(std::ostream& os, Chain <T> &chain)
{
    if (chain.count() == 0)
    {
        os << "empty";
    }
    for (int i = 0; i < chain.count(); i++)
    {
        os << chain[i] << ' ';
    }
    os << endl;
    return os;
}

注意事项

在Chain类的定义中使用了Element类,Element类的定义中也使用了Chain类,这里我们需要使用前置声明确保可以顺利调用。我将Element类写在Element.h文件中,并在预处理命令中加入了#include "Chain.h";将Chain类的定义写在了Chain.h文件中,并在定义Chain类的代码前使用template <class T> class Element;作为前置声明。这样,就可以保证互相调用不出问题。

赞赏
除特殊说明外,本站文章均为作者原创,采用 CC BY-NC-SA 3.0 Unported 协议进行许可。

发表评论

textsms
account_circle
email

CAPTCHAis initialing...

自定义模板类实现比std::vector更强大的动态数组
最近闲的没事打算复习下C++,于是写了这么个类。功能上基本和标准库中的vector相似,又多加了几个功能,更加实用一些。因为用了模板类,所以和vector一样,兼容包括自定义类型在内的所有…
扫描二维码继续阅读
2018-03-07