顺序存储线性表的分析（八）

        我们在前面讲解了 SeqList  线性表的相关特性，下来我们来分析下它的效率。如下

template < typename T >
class SeqList : public List<T>
{
protected:
    T* m_array;        // 顺序存储空间
    int m_length;      // 当前线性表长度
public:
    bool insert(int i, const T& e);    // O(n)
    bool remove(int i);                // O(n)
    bool set(int i, const T& e);       // O(1)
    bool get(int i, T& e) const;       // O(1)
    int length() const;                // O(1)
    void clear();                      // O(1)
    
    // 顺序存储线性表的数组访问方式
    T& operator[] (int i);             // O(1)
    T& operator[] (int i) const;       // O(1)
    
    // 顺序存储空间的容量 
    virtual int capacity() const = 0;
};

        那么问题来了，两个长度相同的 SeqList ，插入和删除操作的平均耗时是否相同呢？插入操作的大O表示法是 O(n + 5)，等价于O(n)；而删除操作是 O(n-1) ，等价于 O(n)。从时间复杂度上来说，它们是相同的。我们再来想下，插入一个 int 类型的数字和插入一个 string 类型的字符串，两个效率能一样吗？数字肯定是效率非常高的，但是字符串就涉及到字符串的 copy 了，因此效率肯定肯定没有数字的高。

        接下来我们来看看下面代码正确吗？为什么？

StaticList<int*, 5> s1;
StaticList<int*, 5> s2;

for(int i=0; i<s1.capacity(); i++)
{
    s1.insert(0, new int(i));
}

s2 = s1;

for(int i=0; i<s1.capacity(); i++)
{
    delete s1[i];
    delete s2[i];
}

        我们咋一看，感觉这段代码没问题。申请了两个 StaticList 类型的指针数组，然后再在 s1 中插入元素，将 s1  赋值给 s2，最后删除两个指针数组。我们仔细想想，在 s1 赋值给 s2 的时候，s2 同时也指向了 s1 数组的地址，再次进行两个相同地址的释放，难道代码不会出错吗？肯定会啊。我们再来看看下面这段代码正确吗？

void func()
{
    DynamicList<int> d1(5);
    DynamicList<int> d2 = d1;
    
    for(int i=0; i<d1.capacity(); i++)
    {
        d1.insert(i, i);
        d2.insert(i, i*i);
    }
    
    for(int i=0; i<d1.capacity(); i++)
    {
        cout << d1[i] << endl;
    }
}

        我们在定义 d2 的时候，进行了拷贝构造，那么后面的插入操作便会出现问题。会将 d2 的操作覆盖掉 d1 的结果，因此会出现我们不想看到的结果。

        那么对于容器类型的类，我们可以考虑禁用，方法是将它们都声明为 protected 属性就行。那么我们之前的 List 类代码就可以优化为这样

template < typename T >
class List : public Object
{
protected:
    List(const List&);
    List& operator= (const List&);
public:
    List() {}
    virtual bool insert(const T& e) = 0;
    virtual bool insert(int i, const T& e) = 0;
    virtual bool remove(int i) = 0;
    virtual bool set(int i, const T& e) = 0;
    virtual bool get(int i, T& e) const = 0;
    virtual int length() const = 0;
    virtual void clear() = 0;
};

        将拷贝构造和赋值操作声明为 protected，那么就不会出现上面的问题了。我们来看看下面的代码正确吗？

int main()
{
    StaticList<int, 5> list;
    
    for(int i=0; i<list.capacity(); i++)
    {
        list[i] = i * i;
    }
    
    return 0;
}

        在这份代码中，我们将线性表当成数组来使用了，线性表必须先插入元素，才能使用操作符 [] 访问元素。顺序存储结构线性表提供了数组操作符重载，通过重载能够快捷方便的获取目标位置处的数据元素，再具体的使用方式上类似数组，但是由于本质不同，不能代替数组使用。那么我们就有必要来开发一个数组类了。数组类的结构如下所示

        通过今天的学习，总结如下：1、线性表作为容器类，应该避免拷贝构造和拷贝赋值；2、顺醋存储线性表可能被当成数组误用。