== list.h ==
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include<assert.h>
#include<iostream>
namespace yjc
{
template<class T>
struct list_node // 节点的类，定义成结构体类型，是一个不成文的规定，原因是节点里的数据都是public
{
// 没用用访问限定符修饰，默认public，方便list访问节点（节点要高频的访问）
T _data;
list_node<T>* _next; // 指向的是一个节点，而不是节点里面的数据，所以用list_node<T>*
list_node<T>* _prev;
list_node(const T& x = T()) // 构造函数也妙和list的配合很好
:_data(x)
, _next(nullptr)
, _prev(nullptr)
{}
};
template<class T, class Ref, class Ptr>
struct list_iterator // list的迭代器就不是一个原生指针了，要通过运算符重载来实现
{
typedef list_node<T> Node;
typedef list_iterator<T, Ref, Ptr> Self; // 本质上还是两个类，用模板让编译器实现
Node* _node; // 迭代器的成员是一个指向节点的指针
list_iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}
Self& operator++()
{
_node = _node->_next;
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
};
// 这种写法很冗余，可以用类模板来实现const迭代器
//template<class T>
//struct list_const_iterator
//{
// typedef list_node<T> Node;
// typedef list_const_iterator<T> Self;
// Node* _node;
// list_const_iterator(Node* node) // 构造函数也要匹配
// :_node(node)
// {}
// const T& operator*()
// {
// return _node->_data;
// }
// const T& operator->()
// {
// return _node->_data;
// }
// Self& operator++()
// {
// _node = _node->_next;
// return *this;
// }
// Self& operator--()
// {
// _node = _node->_prev;
// return *this;
// }
// Self operator++(int)
// {
// Self tmp(*this);
// _node = _node->_next;
// return tmp;
// }
// Self operator--(int)
// {
// Self tmp(*this);
// _node = _node->_prev;
// return tmp;
// }
// bool operator!=(const Self& s)
// {
// return _node != s._node;
// }
//};
template<class T>
class list // 注意这边就是list的类了，而不是节点的类
{ // 类模板，太妙啦
typedef list_node<T> Node; // Node是私有的，并且收到访问限定符的限制，类比内部类
public:
typedef list_iterator<T, T&, T*> iterator; // wow这里也很好 所有的迭代器都叫iterator，统一了
// 实现const迭代器
// const int* p1 右定址 修饰指向的内容
// int* const p1 左定值 修饰指针本身
// 明确const迭代器是要修饰指向的内容不能修改
// typedef const list_iterator<T> const_iterator; 错误写法
typedef list_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
return iterator(_head);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
return const_iterator(_head); // 注意返回值也要改
}
void empty_init()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head; // 空链表自己指向自己
}
list()
{
empty_init();
}
list(size_t n, const T& val = T()) // n个val构造
{
empty_init();
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
list(const list<T>& lt)
{
empty_init();
for (auto& e : lt)
{
push_back(e);
}
}
list<T> operator=(list<T> lt)
{
swap(lt);
return *this;
}
~list()
{
clear();
delete _head;
_head = nullptr;
}
void swap(list<T>& tmp) // 给下面打基础的
{
std::swap(_head, tmp._head);
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
void push_back(const T& x)
{
//Node* new_node = new Node(x); // 就是定义了一个Node类型的指针，它指向堆上的一块空间
//_head->_prev = new_node->_next;
//_head->_next = new_node->_prev;
//new_node->_next = _head->_prev;
//new_node->_prev = _head->_next; // 错误写法
// 正确写法
/* Node* new_node = new Node(x);
Node* tail = _head->_prev;
tail->_next = new_node;
new_node->_prev = tail;
new_node->_next = _head;
_head->_prev = new_node;*/
// 直接复用
insert(end(), x);
}
void push_front(const T& x)
{
insert(begin(), x);
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
iterator insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* newnode = new Node(val);
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_prev = prev;
newnode->_next = cur;
cur->_prev = newnode;
return iterator(newnode);
}
iterator erase(iterator pos)
{
assert(pos != end()); // 迭代器比较
Node* del = pos._node;
Node* prev = del->_prev;
Node* next = del->_next;
prev->_next = next;
next->_prev = prev;
delete del; // 迭代器会失效，pos指向的节点被释放
return iterator(next);
}
private:
Node* _head; // 哨兵位,是一个指向节点的指针
};
template <class T>
void swap(list<T> a, list<T> b)
{
a.swap(b); // 不管用户如何调用，都调不到库里的，效率高
}
}
== test.cpp ==
#define _CRT_SECURE_NO_WARNINGS 1
#include"list.h"
#include<iostream>
using namespace std;
//int main()
//{
// yjc::list<int> l1;
// l1.push_back(1);
// l1.push_back(2);
// l1.push_back(3);
// l1.push_back(4);
//
// yjc::list<int>::iterator it = l1.begin();
// for (auto e : l1)
// {
// cout << e << " ";
// }
//
// const yjc::list<int> l2(10, 1);
//
// yjc::list<int>::const_iterator it2 = l2.begin(); // 迭代器不能和上面重名
// while (it2 != l2.end())
// {
// cout << *it2 << " ";
// it2++;
// }
// return 0;
//}
//int main()
//{
// yjc::list<int> l1;
// l1.push_back(1);
// l1.push_back(1);
// l1.push_back(1);
// l1.push_back(1);
// l1.push_front(6);
// for (auto e : l1)
// {
// cout << e << " ";
// }
// cout << endl;
//
// l1.pop_back();
// l1.pop_front();
// for (auto e : l1)
// {
// cout << e << " ";
// }
// cout << endl;
//
// return 0;
//}
//int main()
//{
// yjc::list<int> l1;
// l1.push_back(1);
// l1.push_back(1);
// l1.push_back(1);
// l1.push_back(1);
//
// yjc::list<int>l2(l1);
// for (auto e : l2)
// {
// cout << e << " ";
// }
// cout << endl;
// yjc::list<int> l3 = l1;
// for (auto e : l3)
// {
// cout << e << " ";
// }
//
// return 0;
//}
int main()
{
yjc::list<int> l1;
l1.push_back(1);
l1.push_back(1);
l1.push_back(1);
l1.push_back(1);
yjc::list<int>l2(l1);
for (auto e : l2)
{
cout << e << " ";
}
cout << endl;
yjc::list<int> l3 = l1;
for (auto e : l3)
{
cout << e << " ";
}
// 为什么要实现一个swap，库里面有为啥还要实现
l1.swap(l2); // 这样肯定就是调用自己实现的交换
// 但是别人使用我实现的接口不知道，有可能写成
std::swap(l1, l2); // 如果自己没有实现，就会调用库里的，但是库里的效率底，代价大
// 库实现会先创建空间再拷贝，然后再释放，代价很大
return 0;
}