C++系列-list的模拟实现

🌈个人主页：羽晨同学 

💫个人格言:“成为自己未来的主人~”   

构造函数生成

template<class T>
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;

T _data;
ListNode(const T& data = T())
:_next(nullptr)
,_prev(nullptr)
,_data(data)
{}
};

在这个构造函数当中，有几个特别优秀的点需要注意：

•  const &的使用的好处:

1. 使得代码更加高效，具体解释为：如果我们使用&，那么我们可以直接使用传递的值，而不需要再进行构造，生成副本，提高了效率。
2. T（）这个隐式类型对象的使用，如果我们什么都不传的时候，代码会默认使用T（），如果这个时候是值传递，那么我们需要生成一个构造，然后再传递给data，而&的时候，我们可以直接调用。

• T（）的使用

1. 适用于所有类型，因为传入的数据类型不确定，所以我们只能使用T()

迭代器部分代码

template<class T, class Ref , class Ptr>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T, Ref, Ptr> Self;
Node* _node;

在链表中实现迭代器和vector，string中实现迭代器的代码实现不同，这是由于二者之间的底层逻辑不同，无论是string还是vector，它的底层都是连续的，而list不是这样的，所以我们之前使用的那样子就不可以了。

前置++和前置--

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;
}

因为是先使用后++，所以我们先将节点放在一个变量当中。

*和->的实现

Ref operator*()
{
return _node->_data;
}
Ptr operator->()
{
return &_node->_data;
}

 ！=和==功能的实现

bool operator!=(const Self& it)
{
return _node != it._node;
}
bool operator==(const Self& it)
{
return _node = it._node;
}

其实这些主要都是我们运用迭代器的时候所需要实现的代码。

 迭代器补充部分

 

template<class T>
class list
{
typedef ListNode<T> Node;
public:
typedef ListIterator<T, T&, T*>iterator;
typedef ListIterator<T, const T&, const T*>const_iterator;
iterator begin()
{
return iterator(_head->_next);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
iterator end()
{
retrun iterator(_head);
}
const_iterator end() const
{
return const_iterator(_head);
}

 哨兵位节点构造

list()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}

插入删除功能实现

void push_back(const T& x)
{
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
void push_front(const T& x)
{
insert(begin(), x);

}
void pop_front()
{
erase(begin());
}

insert和erase功能实现

iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* newnode = new Node(x);
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* cur = pos._node;
Node* prev = cur->_prev;
Node* next = cur->_next;
prev->_next = next;
next->_prev = prev;
delete cur;
return iterator(next);

}

打印功能

void Func(const list<int>&lt)
{
list<int>::const_iterator it = lt.begin();
while (it !=lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}

测试代码1

void test_list1()
{
list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);
lt1.push_back(4);
lt1.push_back(5);
Func(lt1);
list<int>::iterator it = lt1.begin();
while (it != lt1.end())
{
*it += 10;
cout << *it << " ";
++it;
}
cout << endl;
for (auto e : lt1)
{
cout << e << " ";
}
cout << endl;
}

测试代码2

struct Pos
{
int _row;
int _col;
Pos(int row = 0, int col = 0)
:_row(row)
,_col(col)
{}
};
void test_list2()
{
list<Pos> lt1;
lt1.push_back(Pos(100, 100));
lt1.push_back(Pos(200, 200));
lt1.push_back(Pos(300, 300));
list<Pos>::iterator it = lt1.begin();
while (it != lt1.end())
{
cout << it->_row << ":" << it->_col << endl;
++it;
}
cout << endl;
}

 

原文地址：https://blog.csdn.net/in_seattle/article/details/140576219

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！