C++入门小馆: 深入了解STLlist

嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的passion。准备好和我一起冲进代码的奇幻宇宙了吗？Let's go！

我的博客：yuanManGan

我的专栏：C++入门小馆 C言雅韵集 数据结构漫游记  闲言碎语小记坊 题山采玉 领略算法真谛

了解使用list:

list的这些接口相信大家已经很熟练了。

只不过我们没有重载流运算符，和下标访问运算符。

模拟实现list类：

我们实现的list是双向循环链表。

我们还是来看看stl源码吧：

我们list中要构造一个类来表示节点，之前用c语言实现时也是用struct来实现节点node，这里我们可以使用class也可以使用struct，但我们选择struct来实现，使用 struct 而非 class 是出于效率、代码简洁性和设计一致性的考虑。尽管 struct 和 class 在 C++ 中功能几乎相同（仅默认访问权限不同），但选择 struct 更符合节点作为“纯数据聚合体”的定位，同时也延续了 C++ 社区中 struct 用于底层数据结构的传统。

 这里定义的next和prev指针用空指针来定义，而后面使用要进行强转

随便看一下代码，不用理解。

 我们实现时就不用这样设计了我们就直接用node*来实现。

list的成员变量也很简单就一个node对象

再看看初始化:

它把初始化分装成了一个函数。

也就是哨兵位：

这里实现的方式依旧是利用内存池，我们暂时实现就利用new吧。

最后再看看insert。

这里还是一个问题，我们实现模板时，不能将定义和声明定义在两个文件，会在编译时出现错误，但我们可以定义和声明写在同一个文件，这里的insert比较小的就直接写在这里面。

如果认真学习了c语言实现链表的同学看这个应该没有问题，闲话少叙直接开写:

大体结构：

namespace refrain
{template<class T>struct list_node{list_node* _prev;list_node* _next;T data;list_node(const T& x = T()): _prev(nullptr), _next(nullptr), data(x){}};template<class T>class list{typedef list_node<T> Node;public:private:Node _head;size_t _size;};}

这里list_node里面的构造函数，里面给的缺省值给的是匿名对象，但有的同学会说，主ber匿名对象不是只有自定义类型有吗，如果T是int类型呢？因为这种原因，设计C++的祖师爷就将匿名对象加强了，内置类型也有匿名对象。

这里多定义了一个size是为了实现size函数。

实现默认构造函数时我们也多创建一个函数empty_initialize()，方便以后复用。

这里调试看看也是没问题的。

我们为了好实现以后的功能先实现一下push_back,其实我们只要实现了insert就可以复用insert但为了方便先实现push_back吧。

我们tail就是_head的prev，所以实现该操作时间复杂度是O(n)。

void push_back(const T& x)
{// tail newnode _headNode* tail = _head->_prev;Node* newnode = new Node(x);tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;_size++;
}

 

也是没有问题。

接下来就是实现迭代器了，但我们可不可以想vector一样使用原生指针，原生指针解引用就是数值而我们node*解引用后是个结构体还得.data才能找到值，然后++等操作也难实现。这时我们就需要将迭代器封装成类了。

我们只需要操作我们需要的操作的运算符就ok了。 

template<class T>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T> Self;Node* _node;list_iterator(Node* node): _node(node){}T& operator*(){return _node->data;}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int){Self tmp(*this);++*this;return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp(*this);--*this;return tmp;}bool operator==(const self& x) const {return _node == x.node; }bool operator!=(const self& x) const {return _node != x.node; }
};

typedef list_node<T> Node;
typedef list_iterator<T> Self;

重命名这些一是美观，二是等会再说，库里面更喜欢重命名。 

这时iterator类，我们再看看list类里面的iterator吧：

很简单

typedef list_iterator<T> iterator;iterator begin()
{return _head->_next;
}iterator end()
{return _head;
}

 有了迭代器就可以实现范围for就可以实现遍历逻辑。

 假如我们要实现一个打印函数:

出了个什么问题呢？我们没有实现const迭代器就不能使用const。那我们实现一下吧，我们的const的迭代器和普通迭代器有什么区别呢？对const迭代器指向的内容不能修改

typedef const iterator const_iterator;

 这样能不能实现const迭代器呢，const iterator表示迭代器本身不能修改，而指向的内容可以修改。我们只需要改一下重载运算符解引用这个地方就行了。

const T& operator*()
{return _node->data;
}

 只需要改变这一点就能实现const迭代器了，那我们重新定义一个类？这样代码就太冗余了，我们可以将改重载的返回值弄成模板就行了，让编译器帮我们写。

	template<class T, class Ref>struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref> Self;Node* _node;list_iterator(Node* node): _node(node){}Ref operator*(){return _node->data;}
.........................................

 类里面:

const_iterator begin() const
{return _head->_next;
}const_iterator end() const
{return _head;
}

实现出来的print函数就可以正常使用了。

实现完迭代器我们就可以安心的实现插入删除了

insert 

void insert(iterator pos, const T& x)
{//prev newnode curNode* cur = pos->_node;Node* newnode = new Node(x);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;
}

我们就可以采用复用insert来实现头插尾插操作了。 

		void push_back(const T& x){// tail newnode _head/*Node* tail = _head->_prev;Node* newnode = new Node(x);tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;_size++;*/insert(end(), x);}void push_front(const T& x){insert(begin(), x);}

注意实现erase操作时会导致迭代器失效所以要返回下一个位置的迭代器。

注意不能删除哨兵位。

iterator erase(iterator pos)
{assert(pos != end());//prev del nextNode* del = pos->_node;Node* prev = del->_prev;Node* next = del->_next;prev->_next = next;next->_prev = prev;delete del;--_size;return next;//return iterator(next);
}

 一样的复用逻辑:

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

size函数就不用说了：

size_t size()
{return _size;
}

再来写写差点漏掉的析构吧！

先实现一个clear函数

void clear()
{auto it = begin();while (it != end()){it = erase(it);}
}

析构函数:

~list()
{clear();delete _head;_head = nullptr;
}

接下来就是赋值运算符重载，和拷贝构造这些了:

拷贝构造就直接复用咯.

list(list<T>& lt)
{empty_init();while (auto & e : lt){push_back(e);}
}

swap也很简单

void swap(list<T>& lt)
{std::swap(_head, lt->_head);std::swap(_size, lt._size);
}

赋值运算符重载：

list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}

 再来写写大括号构造

list(initializer_list<T> il)
{empty_init();for (auto& e : il){push_back(e);}
}

就实现完了，完结撒花！