hello~ 很高兴见到大家! 这次带来的是C++中关于list容器这部分的一些知识点,如果对你有所帮助的话,可否留下你的三连呢?
个 人 主 页: 默|笙
接上次的博客<list的使用>
一、做好实现list前的准备工作
由于模板的特殊，声明和定义不分离,即把它们放在一个文件里(.h)。
模板的实例化需要看到完整定义，而分文件编译机制导致无法让编译器在使用模板的地方获取定义，导致无法生成实例代码，链接失败。
1.1 节点
- 与底层为数组的vector不同，list这个模板的底层是链表，是由一个一个的节点组成的，我们首先要实现的就是节点。
- 我们可以将节点所需变量打包成一个类，其包含一个存储数据的变量和两个指针。由于我们需要经常访问这个类的成员变量，我们用struct实现。
- 同时不要忘了用模板实现。
template<class T>
struct list_node//节点
{
T _data;
list_node<T>* _next;//指向前一个节点的指针
list_node<T>* _prev;//指向后一个节点的指针
list_node(const T& x = T())//构造节点
:_data(x)
,_next(nullptr)
,_prev(nullptr)
{}
};
- 关于节点构造函数里的 const T& x = T()：c++规定，T()，若T为自定义类型，则会调用默认构造函数，若为内置类型，则会进行零初始化，将值设置为0 或 nullptr。
- 为了在任何时候节点都能被初始化（无论是设置头节点还是push_back一个节点），我们用全缺省默认构造函数。
1.2 实现iterator迭代器
1.实现基本框架（普通迭代器）
- 在之前vector的实现里，我们直接将指针重命名为迭代器iterator（vector博客）。这是因为vector的底层是数组，*解引用能直接拿到数据，++能移动到后一个位置，- -能移动到前一个位置，运用指针就能达到预期目的。
- 但在list里，我们能够直接接触的只有节点，节点的指针解引用，拿到的不会是我们想要的数据，而是节点本身，++与- -也不会达到预期效果，节点指针不能成为我们的迭代器。
- 那么我们可以类封装节点指针来实现迭代器，通过重载运算符来控制迭代器的行为（重载++与- -实现跳转到前一个或后一个节点，重载*实现访问数据）。
则有：
template<class T>
struct __list_iterator
{
typedef list_node<T> Node;
Node* _node;
__list_iterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_data;
}
//前置++
__list_iterator<T>& operator++()
{
_node = _node->_next;
return *this;
}
//后置++
__list_iterator<T> operator++(int)
{
__list_iterator<T> tmp(*this);
_node = _node->_next;
return tmp;
}
//前置--
__list_iterator<T>& operator--()
{
_node = _node->_prev;
return *this;
}
//后置--
__list_iterator<T> operator--(int)
{
__list_iterator<T> tmp(*this);
_node = _node->_prev;
return tmp;
}
//!=
bool operator!=(const __list_iterator<T>& it)const
{
return _node != it._node;
}
//==
bool operator==(const __list_iterator<T>& it)const
{
return _node == it._node;
}
};
注：这里的 this 是迭代器指针，也就是__list_iterator*，而*this是迭代器。
- *重载：我们的预期是解引用直接得到数据，重载*函数让其被调用时返回数据便可，这里返回数据的引用）。
- 前置++与前置- -重载：改变迭代器的指向然后返回迭代器的引用（避免拷贝）就行。
- 后置++与后置- -重载：由于需要返回的是改变之前的迭代器，需要先把所指节点改变之前的迭代器拷贝存一份，这里迭代器变量名称设置为tmp，迭代器所指节点改变之后再返回tmp。这里不能返回引用，因为tmp离开这个作用域就会销毁。
迭代器这个类不需要实现析构函数，拷贝构造函数和赋值重载函数。前者是因为它没有资源需要释放，它只是目前指向/管理这个节点，这个节点并不属于它；后面两个是因为我们需要的就是浅拷贝，指向同一块空间，不需要进行深拷贝。
- != 与 ==：分辨两个迭代器所指向的节点是否是不同或相同节点便可。
2. 常量迭代器的添加
- 在一些场景比如创建Print函数时，仅仅是遍历，我们不能允许改变迭代器所指的节点的值，这需要我们使用到常量迭代器。
- 常量迭代器如何实现？只需要修改*重载函数的返回值就行，加上const修饰。
- 常量迭代器不是本身不可修改，而是它指向的数据不能被修改。
const T& operator*()
{
return _node->_data;
}
接下来，我们来看一段加上常量迭代器过后的代码：
template<class T>
struct __list_iterator
{
typedef list_node<T> Node;
Node* _node;
__list_iterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_data;
}
//2
const T& operator*()
{
return _node->_data;
}
};
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef __list_iterator<T> iterator;
//1
typedef const __list_iterator<T> const_iterator;
private:
};
这里省略了很多代码，留下了主要的部分。这个代码里存在着两处问题。
- 1处的错误：将 const __list_iterator类型重定义为 const_iterator，也就是常量迭代器。注意，const这里修饰的是 __list_iterator这个类型本身，意思是这个迭代器它本身不能修改，而不是说迭代器它所指向的数据不能被修改，这不符合我们的预期。
- 假如没有上面的错误，仅有2处，也存在着问题：这里虽然两个*重载函数构成重载，但是只有被const修饰的迭代器才能够调用上面的const *函数，然后又回到了上面的问题，这也是迭代器本身不可修改，做不到迭代器的基本功能遍历。
- 正确方法应该是再创建一个常量迭代器的类，与上面普通迭代器的类区别开来。
如下：
//普通迭代器
template<class T>
struct __list_iterator
{
typedef list_node<T> Node;
Node* _node;
__list_iterator(Node* node)
:_node(node)
{}
T& operator*()
{
return _node->_data;
}
//前置++
__list_iterator<T>& operator++()
{
_node = _node->_next;
return *this;
}
//后置++
__list_iterator<T> operator++(int)
{
__list_iterator<T> tmp(*this);
_node = _node->_next;
return tmp;
}
//前置--
__list_iterator<T>& operator--()
{
_node = _node->_prev;
return *this;
}
//后置--
__list_iterator<T> operator--(int)
{
__list_iterator<T> tmp(*this);
_node = _node->_prev;
return tmp;
}
//!=
bool operator!=(const __list_iterator<T>& it)const
{
return _node != it._node;
}
//==
bool operator==(const __list_iterator<T>& it)const
{
return _node == it._node;
}
};
//常量迭代器
template<class T>
struct __list_const_iterator
{
typedef list_node<T> Node;
Node* _node;
__list_iterator(Node* node)
:_node(node)
{}
const T& operator*()
{
return _node->_data;
}
//前置++
__list_iterator<T>& operator++()
{
_node = _node->_next;
return *this;
}
//后置++
__list_iterator<T> operator++(int)
{
__list_iterator<T> tmp(*this);
_node = _node->_next;
return tmp;
}
//前置--
__list_iterator<T>& operator--()
{
_node = _node->_prev;
return *this;
}
//后置--
__list_iterator<T> operator--(int)
{
__list_iterator<T> tmp(*this);
_node = _node->_prev;
return tmp;
}
//!=
bool operator!=(const __list_iterator<T>& it)const
{
return _node != it._node;
}
//==
bool operator==(const __list_iterator<T>& it)const
{
return _node == it._node;
}
};
template<class T>
class list
{
typedef list_node Node;
public:
typedef __list_iterator iterator;
//重命名常量迭代器
typedef __list_const_iterator const_iterator;
private:
};
- 但上面的代码稍微有些冗长，且两个迭代器几乎完全一样，这里我们可以增加一个模板参数，将它们整合为同一个模板类，最终使得这两个迭代器变成这个模板类的不同实例。
如下：
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;
}
//前置++
Self& operator++()
{
_node = _node->_next;
return *this;
}
//后置++
Self operator++(int)
{
Self tmp(*this);
_node = _node->_next;
return tmp;
}
//前置--
Self& operator--()
{
_node = _node->_prev;
return *this;
}
//后置--
Self operator--(int)
{
Self tmp(*this);
_node = _node->_prev;
return tmp;
}
//!=
bool operator!=(const Self& it)const
{
return _node != it._node;
}
//==
bool operator==(const Self& it)const
{
return _node == it._node;
}
};
template<class T>
class list
{
typedef list_node Node;
public:
typedef __list_iterator<T, T&> iterator;
typedef __list_iterator<T, const T&> const_iterator;
private:
};
- 这里通过增加Res模板参数来实现迭代器模板类，除此之外，在模板类里，还将__list_iterator<T, Ref> 重命名为Self，这样可以方便以后代码的维护，比如增加一个模板参数时，只用动这里一个地方就行了。
3.->重载函数
接下来看一段代码：
//这是一个类：
struct Pos
{
int _row;
int _col;
Pos(int row = 0, int col = 0)
:_row(row)
, _col(col)
{}
};
//我们尝试打印一下存储这个Pos类型的list<Pos>,假设list已经实现
int main()
{
mosheng::list<Pos> lt1;
lt1.push_back({1,1});//隐式类型转换
lt1.push_back({2,2});
lt1.push_back({3,3});
lt1.push_back({4,4});
auto it = lt1.begin();
while (it != lt1.end())
{
//cout << (*it)._row << ":" << (*it)._col << endl;
cout << it->_row << ":" << it->_col << endl;
++it;
}
cout << endl;
return 0;
}
- 会出现（其中mosheng是list实现所在的命名空间）：
- 这是因为我们重载了*，但是还没有重载->，所以我们无法成功打印。接下来让我们来进行实现：
//operator->() 的返回类型必须是 T* 或迭代器，无论 T 是否为指针类型
T* operator->()
{
return &_node->_data;
}
- 将其放入迭代器类模板里，代码能够正常运行。
我们能够发现一个有趣现象：根据重载函数，返回的应该是Pos*，而上面代码的 it->_row，它少了一个->，实际应该是it->->row（写的时候不能写两个）。第一个箭头是迭代器运算符重载得到Pos*，第二个取Pos里的row。省略一个->是编译器的特殊处理，为了增强可读性。
为了实例化常量迭代器，我们再增添一个模板参数。
template<class T, class Ref, class Ptr>
struct __list_iterator
{
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;
}
}
class list
{
typedef list_node<T> Node;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
}
//省略中间一部分
二、实现list
由于链表的实现比较简单没有什么需要单独拿出来讲的内容，这里就跳过了。
template<class T>
class list
{
typedef list_node<T> Node;
public:
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;
//创造头节点函数
void empty_Init()
{
_head = new Node;
_head->_prev = _head;
_head->_next = _head;
}
//默认构造函数
list()
{
empty_Init();
}
//拷贝构造函数
list<T> (const list<T>& lt)
{
empty_Init();
for (const auto& e : lt)
{
push_back(e);
}
}
//初始化列表构造函数
list(initializer_list<T> il)
{
empty_Init();
for (const auto& e : il)
{
push_back(e);
}
}
//清除链表节点，留下头节点
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
_size = 0;
}
//析构函数
~list()
{
clear();//清除所有节点
delete _head;//清除头节点
_head = nullptr;
}
//交换
void swap(list<T>& lt)
{
std::swap(_head, lt._head);
std::swap(_size, lt._size);
}
//赋值重载函数（现代写法）
list<T>& operator=(list lt)
{
swap(lt);
return *this;
}
//begin()
iterator begin()
{
return iterator(_head->_next);
}
const_iterator begin()const
{
return cosnt_iterator(_head->_next);
}
//end()
iterator end()
{
return iterator(_head);
}
const_iterator end()const
{
return const_iterator(_head);
}
//在指定位置插入
iterator insert(iterator pos, const T& x)
{
Node* cur = pos._node;
Node* newnode = new Node(x);
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_next = cur;
newnode->_prev = prev;
cur->_prev = newnode;
_size++;
return iterator(newnode);
}
//删除指定位置
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* next = cur->_next;
Node* prev = cur->_prev;
prev->_next = next;
next->_prev = prev;
delete cur;
cur = nullptr;
_size--;
return iterator(next);
}
//尾插
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());
}
//节点个数
size_t size()
{
return _size;
}
private:
Node* _head;
size_t _size = 0;
};
}
今天的分享就到此结束啦,如果对读者朋友们有所帮助的话,可否留下宝贵的三连呢~~
如果可以, 那就让我们共同努力, 一起走下去!