AI 助理
备案控制台
开发者社区 计算巢 文章 正文

模拟实现c++中的list模版

2025-02-14 49 发布于河北
版权
举报
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 模拟实现c++中的list模版

一·list简述：
即相当于一个放入任意类型的一个容器，底层就是链表。即是与vector的区别。

二·库内常用接口函数使用：
这里简单介绍一下除了下面要实现的接口函数还有些其他接口函数：

1·reverse():
对于以前的vector和string，它们用的是算法库里的，故括号里还要传迭代器区间，而list库自己实现了，可以不传参：

list lt;
lt.emplace_back(1);
lt.emplace_back(2);
lt.emplace_back(3);
lt.emplace_back(4);

lt.reverse();
list::iterator it = lt.begin();
it = lt.begin();
while (it != lt.end()) {
cout << *it << " ";
it++;
}

2.sort():
对于list库里的sort（）是默认升序。

list ltt;
ltt.emplace_back(5);
ltt.emplace_back(3);
ltt.emplace_back(7);
ltt.emplace_back(10);
ltt.sort();
list::iterator itt = ltt.begin();
while (itt != ltt.end()) {
cout << *itt << " ";
itt++;
}

当然也可以也可以这样完成升降序：

同理，这里其实也可以不创建对象，直接匿名对象也可以。

3.merge():
即把两个list对象按升序拼接起来（前提是两个对象都是有序的，不是的话要提前给它sort一下），最后拼到前者对象，后者对象清空，如：

list lt;
lt.emplace_back(1);
lt.emplace_back(2);
lt.emplace_back(3);
lt.emplace_back(4);
list ltt;
ltt.emplace_back(5);
ltt.emplace_back(3);
ltt.emplace_back(7);
ltt.emplace_back(10);
ltt.sort();
list::iterator it = lt.begin();
lt.merge(ltt);
it = lt.begin();
while (it != lt.end()) {
cout << *it << " ";
it++;
}
cout << endl;

4.unique():
去重复操作，但是要求list对象要有序：

///去重操作：
list lt;
lt.emplace_back(1);
lt.emplace_back(1);
lt.emplace_back(1);
lt.emplace_back(2);
lt.unique();
list::iterator it = lt.begin();
it = lt.begin();
while (it != lt.end()) {
cout << *it << "";
it++;
}
cout << endl;

5·remove():

删除链表中值为val的节点：

//删除指定元素，只删除找到一个即可：
list lt;
lt.emplace_back(5);
lt.emplace_back(2);
lt.emplace_back(4);
lt.emplace_back(2);
lt.remove(2);
list::iterator it = lt.begin();
it = lt.begin();
while (it != lt.end()) {
cout << *it << "";
it++;
}

5.splice():
本意是粘连的意思，可以给某个位置前面粘连一个对象的链表也可以给某个位置前粘连任意一个对象的迭代器区间：

一个对象给另一个对象粘：

list lt;
lt.emplace_back(5);
lt.emplace_back(2);
lt.emplace_back(4);
lt.emplace_back(2);
list ltt;
ltt.emplace_back(5);
ltt.emplace_back(3);
ltt.emplace_back(7);
ltt.emplace_back(10);
list::iterator it = lt.begin();
lt.splice(++lt.begin(), ltt);
it = lt.begin();
while (it != lt.end()) {
cout << *it << " ";
it++;
}

给pos位置前粘一个迭代器区间：

list lt;
lt.emplace_back(5);
lt.emplace_back(2);
lt.emplace_back(4);
lt.emplace_back(2);
list ltt;
ltt.emplace_back(5);
ltt.emplace_back(3);
ltt.emplace_back(7);
ltt.emplace_back(10);
list::iterator it = lt.begin();
lt.splice(it, lt, ++lt.begin(), lt.end());
it = lt.begin();//这里会把242转移粘在5的前面，故要重新给begin赋值
while (it != lt.end()) {
cout << *it << " ";
it++;
}

粘连别人的迭代器区间：

list lt;
lt.emplace_back(5);
lt.emplace_back(2);
lt.emplace_back(4);
lt.emplace_back(2);
list ltt;
ltt.emplace_back(5);
ltt.emplace_back(3);
ltt.emplace_back(7);
ltt.emplace_back(10);
list::iterator it = lt.begin();
lt.splice(++lt.begin(), ltt, ++ltt.begin(), ltt.end());
it = lt.begin();
while (it != lt.end()) {
cout << *it << " ";
it++;
}

三·list的模拟实现相关函数接口：
框架构造：list是吧每个节点连接起来，故首先把节点封装成一个类，接着由于迭代器相当于节点指针，即双向迭代器，只能是++或者--无-，+即还要对迭代器去遍历链表，可以把迭代器封装也成一个类。如：

节点类：

namespace li {
template
struct list_node {
list_node _pre;
list_node _next;
T _val;
list_node(const T _val = T())
:_val(_val)
, _pre(nullptr)
, _next(nullptr) { }

};


        

          
        

        
        

          

          AI 代码解读

迭代器 类：

template
struct list_iterator {
typedef list_node Node;
Node* _node;

    list_iterator( Node* node)
        :_node(node)
    {}


        

          
        

        
        

          

          AI 代码解读

};
它们没有资源产生和释放，故只用写所需要的构造函数即可。

这里的template是为了少写一次const迭代器的类，而多加了对原来的类的模版参数可以实例化出const和普通的迭代器类。

list框架：

template
class list {
public:
typedef list_node Node;
typedef list_iterator iterator;
typedef list_iterator const_iterator;
private:

    Node* _head;
    int _size;

};


        

          
        

        
        

          

          AI 代码解读

1.创建头结点和无参构造：
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_pre = _head;
_size = 0;
}

    list() {
        empty_init();

    }


        

          
        

        
        

          

          AI 代码解读

由于后面等有参构造list的时候也是需要构造出头结点，故可以把它封装成一个empty_init函数。

2·有参构造：
list( initializer_list m)//这个模版化出的m对象可以想象成一个数组
{
empty_init();
for (auto& e : m)
{
push_back(e);
}
}
initializer_list il = { 10, 20, 30 };
li::list llt(il);
//拷贝构造：
li::listlt1({ 1,22,223 });//先是隐式类型转换生成的临时对象再拷贝构造给lt1
//隐式类型转换：
const li::list&lt2={ 1,22,223 };//直接隐式类型转换生成临时对象，由于是给临时对象引用（起别名）故临时对象只能读不能写，故用const
这里可以用 initializer_list这个模版来进行{}的初始化。

3·拷贝构造：
list(const list& lt)
{
empty_init();//创建链表的头结点

        for (auto& e : lt)
        {
            push_back(e);
        }
    }


        

          
        

        
        

          

          AI 代码解读

4·赋值重载的现代版本实现：

    void swap(list<T>& lt)
    {
        std::swap(_head, lt._head);
        std::swap(_size, lt._size);
    }
    list<T>& operator=(list<T> lt)//不是引用传参故不会改变lt；
    {
        swap(lt);
        return *this;
    }


        

          
        

        
        

          

          AI 代码解读

5.析构函数：
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}//利用迭代器遍历链表删除各个节点
~list() {
clear();
delete _head;
_head = nullptr;
}
6·list的迭代器类模版内接口函数的实现：
ref operator*() { 

        return _node->_val;
    }
    ptr operator->() {
        return &(_node->_val) ;
    }
    list_iterator<T,ref, ptr> &operator++(int) {
        list_iterator<T,ref,ptr> tmp = *this;
        ++*this;
        return tmp;
    }
    list_iterator<T,ref, ptr>&operator--(int) {
        list_iterator<T,ref,ptr> tmp = *this;
        --*this;
        return tmp;
    }
    list_iterator<T,ref, ptr>& operator++()
    {
        _node = _node->_next;
        return *this;
    }

    list_iterator<T,ref, ptr>& operator--()
    {
        _node = _node->_pre;
        return *this;
    }

    bool operator!=(const  list_iterator<T,ref,ptr>& s) const
    {
        return _node != s._node;
    }

    bool operator==(const  list_iterator<T,ref,ptr>& s) const
    {
        return _node == s._node;
    }


        

          
        

        
        

          

          AI 代码解读

这里需要说的也就是里面对->的重载运算符函数的实现，这样返回节点内数据的地址作用在哪？

其实是为了：如果这里面的val放的自定义类型如：

struct AA { 

int a1 = 1;
int a2 = 2;


        

          
        

        
        

          

          AI 代码解读

};
这时候这个操作就可以直接访问到val里的a1，a2，而不用再有通过AA的对象再去访问a1和a2。

li::list at;
at.push_back(AA());
at.push_back(AA());
at.push_back(AA());
at.push_back(AA());
li::list::iterator ait = at.begin();

cout << (ait-> a1 )<<" ";//如果是自定义类型则迭代器（也就是节点的指针）可以直接访问到此自定义类型的变量。
//如果没有这个重载：
cout << ((ait._node)->_val.a1 )<< " ";
//重载后把两个->省略成一个
cout << (ait.operator->()->a1) << " ";


        

          
        

        
        

          

          AI 代码解读

7·begin（）和end（）的实现：

这里是list直接访问的，故放在list类模版的函数里。

iterator begin() {
return _head->_next;//隐式类型转换，直接传递对应类的构造参数
}
iterator end() {
return _head;
}
const_iterator begin() const
{
return _head->_next;
}

    const_iterator end() const//对应的迭代器实例化出的普通和const类型
    {
        return _head;
    }


        

          
        

        
        

          

          AI 代码解读

7.insert的接口函数的实现：
iterator insert(iterator pos, const T& x) {
//在pos和pos前的位置插入数据，故先保存这两个位置。以防后面找不到，然后在连接指针
Node pre = pos._node->_pre ;
Node cur = pos._node;
Node* pnode = new Node(x);
pnode->_next = cur;
cur->_pre = pnode;
pre->_next = pnode;
pnode->_pre = pre;
_size++;
return pnode;
}
这里其实和vector的迭代器不一样，这里插入不会导致迭代器失效，因为它所指向的对象并没有改变，而只是在它前面插入新节点。

8.push_back和push_front的实现：
void push_back(const T& x) {
insert(end(), x);

    }

    void push_front(const T& x) {
        insert(begin(), x);
    }


        

          
        

        
        

          

          AI 代码解读

9·erase的接口函数的实现：
这里如果删除了就会导致迭代器失效，故要利用返回值接收再次使用。

iterator erase(iterator pos) {
assert(pos != end());
Node pre = pos._node->_pre;
Node next = pos._node->_next;
delete pos._node ;
pre->_next = next;
next->_pre = pre;
_size--;
return next;

    }


        

          
        

        
        

          

          AI 代码解读

10·pop_front和pop_back的实现：
void pop_front() {
erase(begin());
}
void pop_back() {
erase(--end());

    }


        

          
        

        
        

          

          AI 代码解读

11·size和empty的实现：
size_t size() const
{
return _size;
}

    bool empty() const
    {
        return _size == 0;
    }


        

          
        

        
        

          

          AI 代码解读

12·front和back的实现：
T& front() {
return begin()._node->_val;
}
const T& front()const {
return begin()._node->_val;
}
T& back() {
return (--end())._node->_val;
}
const T& back()const {
return --end()._node->_val;
}//分别是拿到val可修改与不可修改
13·不同容器利用迭代器打印数据：
//不同容器的打印
template
void con_print(const Container & con) {
typename Container::const_iterator it = con.begin();//告诉未实例化的模版是类型
//auto it = con.begin();
while (it != con.end())
{ 

    cout << *it << " ";
    ++it;
}
cout << endl;


        

          
        

        
        

          

          AI 代码解读

}
14.list实现代码汇总：

include

include

include

using namespace std;
namespace li {
template
struct list_node {
list_node _pre;
list_node _next;
T _val;
list_node(const T _val = T())
:_val(_val)
, _pre(nullptr)
, _next(nullptr) { }

};
template<class T,class ref,class ptr >
struct list_iterator {
    typedef list_node<T> Node;
    Node* _node;

    list_iterator( Node* node)
        :_node(node)
    {}


    ref operator*() {

        return _node->_val;
    }
    ptr operator->() {
        return &(_node->_val) ;
    }
    list_iterator<T,ref, ptr> &operator++(int) {
        list_iterator<T,ref,ptr> tmp = *this;
        ++*this;
        return tmp;
    }
    list_iterator<T,ref, ptr>&operator--(int) {
        list_iterator<T,ref,ptr> tmp = *this;
        --*this;
        return tmp;
    }
    list_iterator<T,ref, ptr>& operator++()
    {
        _node = _node->_next;
        return *this;
    }

    list_iterator<T,ref, ptr>& operator--()
    {
        _node = _node->_pre;
        return *this;
    }

    bool operator!=(const  list_iterator<T,ref,ptr>& s) const
    {
        return _node != s._node;
    }

    bool operator==(const  list_iterator<T,ref,ptr>& s) const
    {
        return _node == s._node;
    }

};

template<class T>
class list {
public:
    typedef list_node<T> Node;
    typedef list_iterator<T,  T&,  T*> iterator;
    typedef  list_iterator<T,const T&,const T*> const_iterator;

    void empty_init()
    {
        _head = new Node;
        _head->_next = _head;
        _head->_pre = _head;
        _size = 0;
    }

    list() {
        empty_init();

    }
    list( initializer_list<T> m)//这个模版化出的m对象可以想象成一个数组
    {
        empty_init();
        for (auto& e : m)
        {
            push_back(e);
        }
    }

    list(const list<T>& lt)
    {
        empty_init();

        for (auto& e : lt)
        {
            push_back(e);
        }
    }
    void swap(list<T>& lt)
    {
        std::swap(_head, lt._head);
        std::swap(_size, lt._size);
    }
    list<T>& operator=(list<T> lt)//不是引用传参故不会改变lt：
    {
        swap(lt);
        return *this;
    }
    void clear()
    {
        auto it = begin();
        while (it != end())
        {
            it = erase(it);
        }
    }
    ~list() {
        clear();
        delete _head;
        _head = nullptr;
    }
    iterator begin() {
        return _head->_next;//隐式类型转换，直接传递对应类的构造参数
    }
    iterator end() {
        return _head;
    }
    const_iterator begin() const
    {
        return _head->_next;
    }

    const_iterator end() const
    {
        return _head;
    }

    iterator  insert(iterator pos, const T& x) {
        //在pos和pos前的位置插入数据，故先保存这两个位置。以防后面找不到，然后在连接指针
        Node* pre = pos._node->_pre ;
        Node* cur = pos._node;
        Node* pnode = new Node(x);
        pnode->_next = cur;
        cur->_pre = pnode;
        pre->_next = pnode;
        pnode->_pre = pre;
        _size++;
        return pnode;
    }
    void push_back(const T& x) {
        insert(end(), x);

    }

    void push_front(const T& x) {
        insert(begin(), x);
    }
    iterator erase(iterator pos) {
        assert(pos != end());
        Node* pre = pos._node->_pre;
        Node* next = pos._node->_next;
        delete pos._node ;
        pre->_next = next;
        next->_pre = pre;
        _size--;
        return next;

    }

    void pop_front() {
        erase(begin());
    }
    void pop_back() {
        erase(--end());

    }
    size_t size() const
    {
        return _size;
    }

    bool empty() const
    {
        return _size == 0;
    }


    // List Access
    T& front() {
        return begin()._node->_val;
    }
    const T& front()const {
        return begin()._node->_val;
    }
    T& back() {
        return (--end())._node->_val;
    }
    const T& back()const {
        return --end()._node->_val;
    }
private:


    Node* _head;
    int _size;

};


        

          
        

        
        

          

          AI 代码解读

}

//不同容器的打印
template
void con_print(const Container & con) {
typename Container::const_iterator it = con.begin();
//auto it = con.begin();
while (it != con.end())
{ 

    cout << *it << " ";
    ++it;
}
cout << endl;


        

          
        

        
        

          

          AI 代码解读

}

文章标签：
容器
C++
算法
关键词：
C++ list
C++模版
羑悻的小杀马特
+关注
61文章
目录
打赏
0
21
23
1
142
分享
相关文章
羑悻的小杀马特
|
1月前
|
算法 编译器 C++
模拟实现c++中的vector模版
模拟实现c++中的vector模版
羑悻的小杀马特
59 28
ephemerals__
|
3月前
|
编译器 C语言 C++
【c++丨STL】list模拟实现（附源码）
本文介绍了如何模拟实现C++中的`list`容器。`list`底层采用双向带头循环链表结构，相较于`vector`和`string`更为复杂。文章首先回顾了`list`的基本结构和常用接口，然后详细讲解了节点、迭代器及容器的实现过程。 最终，通过这些步骤，我们成功模拟实现了`list`容器的功能。文章最后提供了完整的代码实现，并简要总结了实现过程中的关键点。 如果你对双向链表或`list`的底层实现感兴趣，建议先掌握相关基础知识后再阅读本文，以便更好地理解内容。
ephemerals__
71 1
ephemerals__
|
3月前
|
算法 C语言 C++
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构，适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码，读者可以更好地理解如何使用这些接口。最后，作者总结了`list`的特点和适用场景，并预告了后续关于`list`模拟实现的文章。
ephemerals__
109 7
蓝易云
|
3月前
|
存储 编译器 C++
C++ initializer_list&&类型推导
在 C++ 中，`initializer_list` 提供了一种方便的方式来初始化容器和传递参数，而右值引用则是实现高效资源管理和移动语义的关键特性。尽管在实际应用中 `initializer_list&&` 并不常见，但理解其类型推导和使用方式有助于深入掌握现代 C++ 的高级特性。
蓝易云
35 4
半截诗
|
5月前
|
存储 搜索推荐 C++
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器2
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器
半截诗
121 2
白子寰
|
5月前
|
存储 算法 C++
【C++打怪之路Lv10】-- list
【C++打怪之路Lv10】-- list
白子寰
38 1
半截诗
|
5月前
|
存储 C++ 容器
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器1
【C++篇】深度剖析C++ STL：玩转 list 容器，解锁高效编程的秘密武器
半截诗
102 5
徐霞客320
|
5月前
|
存储 C++ 容器
C++入门9——list的使用
C++入门9——list的使用
徐霞客320
35 1
半截诗
|
5月前
|
存储 编译器 C++
【C++篇】揭开 C++ STL list 容器的神秘面纱：从底层设计到高效应用的全景解析（附源码）
【C++篇】揭开 C++ STL list 容器的神秘面纱：从底层设计到高效应用的全景解析（附源码）
半截诗
123 2
是店小二呀
|
5月前
|
C++
【C++】C++ STL 探索：List使用与背后底层逻辑（三）
【C++】C++ STL 探索：List使用与背后底层逻辑
是店小二呀
85 2