【C++】容器篇(二)——List的基本概述以及模拟实现

简介: 【C++】容器篇(二)——List的基本概述以及模拟实现

前言:

在上期,我们学习了STL库中的第一个容器--vector ,今天我将给大家介绍的是 库中的另外一个容器--List。其实,有了之前学习 vector 的知识,对于List 的学习成本就很低了。


(一)基本介绍

1、基本概念

  1. list 是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
  2. list 的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向 其前一个元素和后一个元素。

2、list 与 forward_list 的比较

list与forward_list非常相似,最主要的区别如下:

  • 最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效。

3、特点

与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。

与其他序列式容器相比,list 和 forward_list 最大的缺陷是不支持任意位置的随机访问

  1. 比如:要访问list 的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;
  2. list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这 可能是一个重要的因素)


(二)list的使用

list的文档介绍:文档介绍

list中的接口比较多,此处类似,只需要掌握如何正确的使用,然后再去深入研究背后的原理,已达到可扩展 的能力。以下为list中一些常见的重要接口。


1、list的构造

2、 list iterator的使用

此处,大家可暂时将迭代器理解成一个指针,该指针指向list中的某个节点。

  1. 1. begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动
  2. 2. rbegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动

 

3、list capacity

4、list element access

 

5、list modifiers

  • list中还有一些操作,需要用到时大家可参阅list的文档说明。

6、list的迭代器失效

前面已经跟大家说过,此处大家可将迭代器暂时理解成类似于指针,迭代器失效即迭代器所指向的节点的无效,即该节点被删除了

1、失效时机

因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。

⚔️ 注意 ⚔️

迭代器有两种实现方式,具体应根据容器底层数据结构实现:

  • 1️⃣原生指针:比如:vector的迭代器就是原生指针;
  • 2️⃣将原生指针进行封装,因迭代器使用形式与指针完全相同,迭代器就是自定义类型对原生指针的封装,模拟指针的行为。

2、list与vector迭代器失效对比:

在C++中,当使用STL容器中的元素并且对容器进行修改时,可能会导致迭代器失效。在这种情况下,如果试图继续使用已经失效的迭代器,则程序可能会产生未定义的行为。


1️⃣vector

在使用vector容器时,添加或删除元素可能会导致迭代器失效。

  1. 这是因为vector容器内部使用动态数组实现,当容器中的元素数量超过了其内存分配的大小时,就需要重新分配一块更大的内存,并将原有元素拷贝到新的内存中;
  2. 此时,原有的迭代器就无法正确指向其对应的元素,因为元素的位置已经改变了;
  3. 同样的情况也发生在删除元素时,因为删除元素后,后面的元素会向前移动,导致原有的迭代器失效。

2️⃣list

插入元素不会导致迭代器失效, 删除元素时,只会导致当前迭代 器失效,其他迭代器不受影响。

void Test()
{
     int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
     list<int> ll(array, array+sizeof(array)/sizeof(array[0]));
     auto it = ll.begin();
     while (it != ll.end())
     {
         // erase()函数执行后,it所指向的节点已被删除,因此it无效
         //在下一次使用it时,必须先给其赋值
         ll.erase(it); 
         ++it;
     }
}
// 改正
void Test()
{
     int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
     list<int> ll(array, array+sizeof(array)/sizeof(array[0]));
     auto it = ll.begin();
     while (it != ll.end())
     {
         ll.erase(it++); // it = ll.erase(it);
     }
}

(三)list的模拟实现

要模拟实现list,必须要熟悉list的底层结构以及其接口的含义,通过上面的学习以及之前对vector和string的学习,我相信大家对于这些内容已基本掌握,现在我们来模拟实现list。

1、代码展示

⚔️ 如果大家还有不懂的,可以参考我上一篇文章:vector的基本实现 ⚔️

  • 接下来我直接给出代码(这里实现的风格跟上篇实现vector稍微不一样):
#pragma once
namespace zp
{
    template<typename T>
    class List {
    private:
        struct Node
        {
            T _data;
            Node* _prev;
            Node* _next;
            Node(const T& x, Node* p = nullptr, Node* n = nullptr)
            :_data(x)
            , _prev(p)
            , _next(n)
            {}
        };
    public:
        class Iterator
        {
        public:
            Iterator(Node* n = nullptr)
                :node(n)
            {}
            T& operator*()
            {
                return node->_data;
            }
            Iterator& operator++()
            {
                node = node->_next;
                return *this;
            }
            Iterator operator++(int)
            {
                Iterator tmp = *this;
                node = node->_next;
                //++(*this);
                return tmp;
            }
            Iterator& operator--()
            {
                node = node->_prev;
                return *this;
            }
            Iterator operator--(int)
            {
                Iterator tmp = *this;
                node = node->_prev;
                return tmp;
            }
            bool operator==(const Iterator& x) const
            {
                return node == x.node;
            }
            bool operator!=(const Iterator& x) const
            {
                return !(*this == x);
            }
        private:
            Node* node;
            friend class List<T>;
        };
    public:
        List()
            :head(new Node(T()))
            , tail(head)
        {}
        ~List()
        {
            clear();
            delete head;
            head = nullptr;
        }
        void push_back(const T& x)
        {
            insert(end(), x);
        }
        void push_front(const T& x)
        {
            insert(begin(), x);
        }
        void pop_back()
        {
            erase(--end());
        }
        void pop_front()
        {
            erase(begin());
        }
        Iterator begin() const
        {
            return head->_next;
        }
        Iterator end() const
        {
            return tail;
        }
        bool empty() const
        {
            return head->_next == tail;
        }
        void clear()
        {
            while (!empty())
            {
                erase(begin());
            }
        }
        Iterator insert(Iterator it, const T& x)
        {
            Node* tmp = it.node;
            Node* newNode = new Node(x, tmp->_prev, tmp);
            tmp->_prev->_next = newNode;
            tmp->_prev = newNode;
            return newNode;
        }
        Iterator erase(Iterator pos)
        {
            Node* tmp = pos.node;
            Iterator res(tmp->_next);
            tmp->_prev->_next = tmp->_next;
            tmp->_next->_prev = tmp->_prev;
            delete tmp;
            return res;
        }
    private:
        Node* head;
        Node* tail;
    };
    
    void print_list(const list<int>& lt)
    {
        list<int>::const_iterator it = lt.begin();
        while (it != lt.end())
        {
            cout << *it << " ";
            ++it;
        }
        cout << endl;
    }
    void test_1()
    {
        list<int> ll;
        ll.push_back(1);
        ll.push_back(2);
        ll.push_back(3);
        ll.push_back(4);
        ll.push_back(5);
        list<int>::iterator it = ll.begin();
        while (it != ll.end())
        {
            (*it) *= 2;
            cout << *it << " ";
            ++it;
        }
        cout << endl;
        list<int>::iterator pos = find(ll.begin(), ll.end(), 4);
        if (pos != ll.end())
        {
            ll.insert(pos, 10);
        }
        for (auto& e : ll)
        {
            cout << e << " ";
        }
        cout << endl;
        it = ll.begin();
        ++it;
        ll.erase(it);
    }
    void test_2()
    {
        list<int> ll;
        ll.push_back(1);
        ll.push_back(2);
        ll.push_back(3);
        ll.push_back(4);
        ll.push_back(5);
        for (auto e : ll)
        {
            cout << e << " ";
        }
        cout << endl;
        auto pos = ll.begin();
        ++pos;
        ll.insert(pos, 20);
        for (auto e : ll)
        {
            cout << e << " ";
        }
        cout << endl;
        ll.push_back(100);
        ll.push_front(1000);
        for (auto e : ll)
        {
            cout << e << " ";
        }
        cout << endl;
        ll.pop_back();
        ll.pop_front();
        for (auto e : ll)
        {
            cout << e << " ";
        }
        cout << endl;
    }
    void test_3()
    {
        list<int> ll;
        ll.push_back(1);
        ll.push_back(2);
        ll.push_back(3);
        ll.push_back(4);
        ll.push_back(5);
        for (auto e : ll)
        {
            cout << e << " ";
        }
        cout << endl;
        ll.clear();
        for (auto e : ll)
        {
            cout << e << " ";
        }
        cout << endl;
        ll.push_back(0);
        ll.push_back(5);
        ll.push_back(10);
        ll.push_back(15);
        for (auto e : ll)
        {
            cout << e << " ";
        }
        cout << endl;
    }
}
  • 上述代码我定义了一个List类,其中包含了一个嵌套的Node结构体用于表示双向链表的节点。使用模板实现泛型数据类型,可以存储任意类型的数据。List类还包含了一个嵌套的【Iterator】类,用于遍历双向链表。

2、注意事项

1️⃣【】不能实现访问操作

前面已经说过list是链表的结果,因此大家不难理解为什么在list下【】不能访问元素。由于list采用的是链接存储而不是连续存储,所以本质上它不支持下标方式(也就是按偏移量)访问。

 

2️⃣sort()

其次就是list的排序操作,我们还是对比之前学习的vector

在 C++ 中,【list 】和 【vector 】是两种不同的数据结构,它们都提供了 sort() 函数来对其中的元素进行排序。但是,它们的底层实现不同,因此其 sort() 函数的效率也不同

vector

  1. 对于 vector 来说,它是一个基于连续内存空间的动态数组,其元素存储在连续的内存块中,因此可以通过指针算术运算等方式快速访问其中的元素。
  2. 由于其元素是连续存储的,因此对其进行排序时可以使用标准库提供的 std::sort() 算法,该算法时间复杂度为 O(NlogN),其中 N 为元素个数。因此,vectorsort() 函数效率较高。

list

  1. 而对于 list 来说,它是一个基于双向链表的容器,其元素并不是连续存储的,因此不能像 vector 那样直接进行指针算术运算访问其中的元素。
  2. 由于其底层实现的原因,list 并没有提供 sort() 函数,但是可以通过调用标准库提供的 std::list::sort() 成员函数来对其中的元素进行排序。
  3. 该函数采用的是归并排序(Merge Sort)算法,时间复杂度为 O(NlogN)。
  4. 由于归并排序需要频繁的进行链表节点的指针操作,因此相较于 vectorsort() 函数而言,listsort() 函数效率较低。

接下来,我们通过代码来简单的看看到底怎么样

  • 代码一:
void test_op()
{
  srand(time(0));
  const int N = 1000000;
  vector<int> v;
  v.reserve(N);
  list<int> lt2;
  for (int i = 0; i < N; ++i)
  {
    auto e = rand();
    v.push_back(e);
    lt2.push_back(e);
  }
  int begin1 = clock();
  sort(v.begin(), v.end()); //对vector进行sort,调用的是算法里的快排
  int end1 = clock();
  int begin2 = clock();
  lt2.sort();               //对list也进行sort
  int end2 = clock();
  printf("vector sort:%d\n", end1 - begin1);
  printf("list sort:%d\n", end2 - begin2);
}

解释说明:

  1. 首先我们给出一个测试用例 N(我这里赋值的为100w),产生了100w 个随机值;
  2. 其中一个放到vector里面,一个放到list里面;
  3. 分别对list和vector进行sort,对比它们的性能看差别有多大
  4. 注意:是在release模式下进行查看

结果如下:

结果:

  • 经过几次反复的验证,我们可以发现,vector的效率比list 的效率打上三四倍的样子,如果在工程里这是一个巨大的差距

  • 代码二:
void test_op()
{
  srand(time(0));
  const int N = 1000000;
  vector<int> v;
  v.reserve(N);
  list<int> lt1;
  list<int> lt2;
  for (int i = 0; i < N; ++i)
  {
    auto e = rand();
    lt1.push_back(e);
    lt2.push_back(e);
  }
  // 拷贝到vector排序,排完以后再拷贝回来
  int begin1 = clock();
  for (auto e : lt1)
  {
    v.push_back(e);
  }
  sort(v.begin(), v.end());
  size_t i = 0;
  for (auto& e : lt1)
  {
    e = v[i++];
  }
  int end1 = clock();
  int begin2 = clock();
  lt2.sort();
  int end2 = clock();
  printf("vector sort:%d\n", end1 - begin1);
  printf("list sort:%d\n", end2 - begin2);
}

解释说明:

  1. 我这里给出两个list;
  2. 对于给出的list1,我们先把它拷贝到vector中,排序完成之后在拷贝回来;
  3. 而对于list2,我们直接进行sort排序;
  4. 对比上述的两个操作,看效率如何

结果如下:

 

结果:

  • 不难发现,list1拷贝到vector里面在排,排序完成之后在拷贝回来都比list2要快,因此不难发现list下sort() 的效率较差。因此很少用,在上述实现中也没有写。

小结

  1. 对于需要频繁进行元素访问操作的情况,建议使用 vector;
  2. 而对于需要频繁进行元素插入、删除和排序等操作的情况,建议使用 list

(四)list与vector的对比


(五)总结

到此,便是本期的全部知识内容了,感谢大家的阅读与支持!!!

 

相关文章
|
2天前
|
存储 C++ 容器
【C++】哈希(模拟实现unordered系列容器)
【C++】哈希(模拟实现unordered系列容器)
|
2天前
|
存储 运维 分布式计算
分布式云容器平台ACK One概述
分布式云容器平台ACK One概述
22 2
|
2天前
|
设计模式 存储 编译器
【C++ STL】容器适配器(Stack & Queue & Priotity_Queue)-- 详解(下)
【C++ STL】容器适配器(Stack & Queue & Priotity_Queue)-- 详解(下)
|
2天前
|
存储 算法 C语言
【C++ STL】容器适配器(Stack & Queue & Priotity_Queue)-- 详解(上)
【C++ STL】容器适配器(Stack & Queue & Priotity_Queue)-- 详解(上)
|
2天前
|
存储 编译器 C++
【C++】List -- 详解(下)
【C++】List -- 详解(下)
|
2天前
|
存储 算法 C++
【C++】List -- 详解(上)
【C++】List -- 详解(上)
|
7天前
|
C++ 容器
|
9天前
|
存储 安全 Java
Java容器类List、ArrayList、Vector及map、HashTable、HashMap
Java容器类List、ArrayList、Vector及map、HashTable、HashMap
|
9天前
|
调度 C++ 容器
【C++】手搓 list 容器
本文我们实现了STL库中重要的list 的模拟实现,其中最重要莫过于迭代器的封装类的书写,这是前所未有的操作(对于我来说,我是第一次使用这种结构)。通过list 的模拟实现也帮我们巩固了类与对象的知识,也强化了指针操作的思路。欢迎大家讨论分析。
14 1
|
1天前
|
存储 程序员 数据安全/隐私保护
C++类
C++类
8 0