C++第七讲：STL--list的使用及模拟实现

1.list的使用

list的使用和vector、string中的接口大概相同，我们只会详细讲述list的不同之处

1.1list是什么

list的底层其实是一个带头双向循环链表：

下面我们来看list的使用

1.2构造、析构、赋值运算符重载

int main()
{
//构造
list<int> ls1(3);//就相当于list<int> ls1(3, 0)，表示构造一个容器，其中有三个结点，每一个结点都是0的副本

//赋值运算符重载（内容改变 + 数据改变）
list<int> ls2(4, 2);
cout << ls1.size() << endl;//3
cout << ls2.size() << endl;//4

ls2 = ls1;
cout << ls1.size() << endl;//3
cout << ls2.size() << endl;//3

return 0;
}

1.3迭代器

list实现的迭代器中，begin和end所指向的位置为：

int main()
{
list<int> ls1(3, 2);
list<int>::iterator it = ls1.begin();
while (it != ls1.end())
{
cout << *it << " ";
it++;
}
cout << endl;

//C++11是支持initilizer_list进行构造的
list<int> ls2({ 1, 2, 3, 4, 5 });
list<int>::iterator it1 = ls2.begin();
while (it1 != ls2.end())
{
cout << *it1 << " ";
it1++;
}
cout << endl;

return 0;
}

1.4empty、size、max_size

1.5front、back

1.6assign – 代替

int main()
{
list<int> ls1(3, 2);
list<int>::iterator it = ls1.begin();
while (it != ls1.end())
{
cout << *it << " ";
it++;
}
cout << endl;

//assign的使用（用新的数据、空间代替原来的list）
ls1.assign(2, 1);//迭代器区间、n个val、初始化列表
ls1.assign({ 1, 2, 3, 4 });
it = ls1.begin();
while (it != ls1.end())
{
cout << *it << " ";
it++;
}
cout << endl;

return 0;
}

1.7push_back和emplace_back

我们在刷题的时候可能会看到emplace_back的使用，所以我们在这一先简单了解一下，之后我们会详细讲述该函数的功能

我们先看一下两个函数在使用时的差异：

class Pos
{
public:
//表示坐标
int _row;
int _col;

//我们写一个构造和拷贝构造，如果调用构造或拷贝构造就显示出被调用
Pos(int row, int col)
:_row(row)
, _col(col)
{
cout << "Pos(int row, int col)" << endl;
}
Pos(const Pos& p)
:_row(p._row)
, _col(p._col)
{
cout << "Pos(const Pos& p)" << endl;
}
};
int main()
{
//创建一个Pos类型的对象
list<Pos> ls1;

Pos p1(1, 2);
ls1.push_back(p1);
ls1.push_back(Pos(1, 2));
ls1.push_back({2, 3});

Pos p2(1, 2);
ls1.emplace_back(p2);
ls1.emplace_back(Pos(1, 2));
ls1.emplace_back(2, 3);

return 0;
}

我们再看一下两个函数的性能差异：
我们都知道，当形参传入实参时，会创建一个临时对象，然后临时对象再传入实参，比如double b = 1.0, int& a = b，这时会发生报错，因为传入给a的实际上时b的一个临时对象，所以要加上const修饰

所以说，对于最后一种情况，使用emplace_back的性能会好点，但是其它情况两者性能没什么区别

上面这几个函数都一样，不再讲

1.8emplace

该函数的作用就是构造 + 插入：

int main()
{
list<int> ls1({1, 2, 3, 4, 5});

ls1.emplace(ls1.begin(), 2);
for (auto e : ls1)
{
cout << e << " ";
}
cout << endl;// 2 1 2 3 4 5

return 0;
}

1.9insert、erase、swap、resize、clear

1.10find

在list的库中，并没有实现find，所以我们还是要使用标准库中的find函数：

int main()
{
list<int> ls1({ 1, 2, 3, 4 });
for (auto e : ls1)
{
cout << e << " ";
}
cout << endl;

//找到并删除元素
int x;
cin >> x;
auto it = find(ls1.begin(), ls1.end(), x);
if (it != ls1.end())
{
ls1.erase(it);
}
for (auto e : ls1)
{
cout << e << " ";
}
cout << endl;

return 0;
}

1.11splice

该函数的作用为转移，将list x转移到迭代器指向的position位置、将迭代器指向的i元素转移到list x中的position位置、转移迭代器，要注意的是，因为是转移，如果是将x2中的数据转移到x1中，那么x2就是一个空的list

该函数在一般情况下不太常用，但是对于LRU（近期最少使用，如果最近使用过，就将使用的那一个程序向前排）情况很好用:

int main()
{
//LRU
list<int> ls1({ 1, 2, 3, 4, 5 });
for (auto e : ls1)
{
cout << e << " ";
}
cout << endl;
//splice函数不仅可以实现两个list之间的转移，还可以做到在自己的list中进行转移
int x;
while (cin >> x)
{
auto pos = find(ls1.begin(), ls1.end(), x);
if(pos != ls1.end())
{
ls1.splice(ls1.begin(), ls1, pos);
}
for (auto e : ls1)
{
cout << e << " ";
}
cout << endl;
}

return 0;
}

当出现一直循环的情况时，我们可以按ctrl+z进行截断，也可以使用ctrl+c，VS中ctrl+z和ctrl+c都是将流中的标识符设置为结束，这样就不能再提取东西了，而有的编译器下，ctrl+c的作用是直接将程序强制结束，会比较暴力

1.12remove、remove_if

在list中，remove的特别之处在于，remove删除时不用再传入迭代器，而是传入值进行删除：

int main()
{
list<int> ls1({ 1, 2, 3, 4 });

ls1.remove(1);
for (auto e : ls1)
{
cout << e << " ";
}
cout << endl;

return 0;
}

remove_if以后再提

1.13unique

该函数可以对list进行去重操作：

int main()
{
list<int> ls1({ 1, 1, 2, 2, 3, 4, 5 });
for (auto e : ls1)
{
cout << e << " ";
}
cout << endl;

ls1.unique();
for (auto e : ls1)
{
cout << e << " ";
}
cout << endl;//1 2 3 4 5

return 0;
}

1.14merge

merge必须针对于排序好了的list进行使用，然后对这两个list进行合并，合并方法为挑小的放进其中一个list中，这会使另一个list中没有数据：

int main()
{
list<double> first, second;

first.push_back(3.1);
first.push_back(2.2);
first.push_back(2.9);

second.push_back(3.7);
second.push_back(7.1);
second.push_back(1.4);

first.sort();
second.sort();

first.merge(second);//将second中的数据合并到first中
for (auto e : first)
{
cout << e << " ";
}
cout << endl;
for (auto e : second)//second中没有数据
{
cout << e << " ";
}
cout << endl;

return 0;
}

如果想要从大到小进行排序，这样使用：

int main()
{
list<double> first, second;

first.push_back(3.1);
first.push_back(2.2);
first.push_back(2.9);

second.push_back(3.7);
second.push_back(7.1);
second.push_back(1.4);

//less和greater是两个结构体，可以传入sort中判断按从小到大排还是从大到小进行排序
//first.sort(less<double>());
//second.sort(less<double>());
first.sort(greater<double>());
second.sort(greater<double>());

first.merge(second, greater<double>());//将second中的数据合并到first中
for (auto e : first)
{
cout << e << " ";
}
cout << endl;
for (auto e : second)//second中没有数据
{
cout << e << " ";
}
cout << endl;

return 0;
}

1.15库中sort的不同使用

我们可以发现，报错了，这是因为：迭代器其实也分为好几种，不同的迭代器有着不同的使用：

其实sort函数的形参我们就可以看出来迭代器的不同：

1.16reverse

逆置操作

2.list的模拟实现

2.1list模拟实现思路

2.2迭代器的实现

list的迭代器实现起来有点不同，因为list中的迭代器不能只是一个指针，如果只是一个指针的话，那么迭代器++，会找不到下一个结点，所以在这里，我们要将迭代器整合成一个类，在类中完成解引用、++的重载，因为迭代器中的数据会经常使用，按照惯例，我们还使用结构体封装

2.3->问题

我们看下面的代码：

class Pos
{
public:
//表示坐标
int _row;
int _col;

Pos(int row = 1, int col = 1)
:_row(row)
, _col(col)
{
cout << "Pos(int row, int col)" << endl;
}
Pos(const Pos& p)
:_row(p._row)
, _col(p._col)
{
cout << "Pos(const Pos& p)" << endl;
}
};

int main()
{
Mine::list<Pos> lt2;
Pos p1(1, 1);
lt2.push_back(p1);
lt2.push_back(Pos(2, 2));
lt2.push_back({ 3,3 });

Mine::list<Pos>::iterator it2 = lt2.begin();
while (it2 != lt2.end())
{
//*重载时返回的是Pos data，所以*it访问的是Pos的对象，这样我们就可以对它的数据进行访问了
cout << (*it2)._row << ":" << (*it2)._col << endl;//这样是可以执行的

++it2;
}
cout << endl;

return 0;
}

那么可以使用->来访问吗？当然可以，只是我们需要重载一下：

这个重载的实现非常奇怪，而使用起来是这样：

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

int main()
{
Mine::list<Pos> lt2;
Pos p1(1, 1);
lt2.push_back(p1);
lt2.push_back(Pos(2, 2));
lt2.push_back({ 3,3 });

Mine::list<Pos>::iterator it2 = lt2.begin();
while (it2 != lt2.end())
{
cout << (*it2)._row << ":" << (*it2)._col << endl;
//cout << it2->_row << ":" << it2->_col << endl;

//为了可读性，特殊处理，省略了一个->
//第一个->的含义是调用它的重载，第二个->的含义为访问内容
//cout << it2->->_row << ":" << it2->->_col << endl;//err:语法错误
cout << it2->_row << ":" << it2->_col << endl;
cout << it2.operator->()->_row << ":" << it2.operator->()->_col << endl;

++it2;
}
cout << endl;

return 0;
}

2.4迭代器封装问题

对于容器，它们的底层有：数组、链表、树和哈希等等，但是我们可以发现：它们被访问的方式都有迭代器，这些迭代器的底层实现可能不同，但是对于我们使用者而言，却没什么区别，这就是C++中的封装概念：

2.5const_iterator实现问题

我们能不能直接这样写：

肯定不能，因为这里的const迭代器是一个类，不是一个指针的别名，如果直接这样实现的话，我们看下边：

所以我们只能够再实现一个const_iterator：

template<class T>
struct list_const_iterator
{
typedef list_node<T> Node;
typedef list_const_iterator Self;
Node* _node;

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

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

Self& operator++()//前置++
{
_node = _node->_next;
return *this;
}
Self& operator--()//前置--
{
_node = _node->_prev;
return *this;
}
Self operator++(int)//后置++
{
Self ret(*this);
_node = _node->_next;
return ret;
}
Self operator--(int)//后置--
{
Self ret(*this);
_node = _node->_prev;
return ret;
}

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

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

typedef list_const_iterator<T> const_iterator;
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
returnconst_iterator(_head);
}
//n个val的构造
list(int n, const T& val = T())
{
empty_init();
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}

int main()
{
//const对象不能够push_back，因为const对象只有在定义时才有一次初始化的机会
const Mine::list<int> ls1(10, 1);
//ls1.push_back(1); err

Mine::list<int>::const_iterator it = ls1.begin();
while (it != ls1.end())
{
cout << *it << " ";
it++;
}
cout << endl;

return 0;
}

但是，我们会发现：const迭代器的实现和普通的迭代器只有在*和->两个运算符重载时才有所不同，而不同只有它们的返回值，因为这两个都是访问操作符，const的作用就是防止访问的数据进行改变，那么我们可不可以将他们进行合并呢，我们看库是怎么实现的：

我们根据库中的实现自己实现一下：

2.6多个swap问题

这个问题我们之前谈过，就是为什么list中实现了两个swap函数：

3.list的模拟实现代码

#pragma once
#include <assert.h>

namespace Mine
{
//使用struct和class的唯一区别是，struct中的对象默认是public，而class中的默认是private
//这里有一个惯例：如果一个对象中的成员全是全局对象，那么就将它们封装在一个struct中
template<class T>
struct list_node
{
T _data;
list_node<T>* _next;
list_node<T>* _prev;

//默认构造函数，因为后边new出结点时，可能会传参进行初始化对象
list_node(const T& x = T())
:_data(x)
, _next(nullptr)
, _prev(nullptr)
{}
};

//迭代器的实现
//typedef list_iterator<T, T&, T*> iterator;
//typedef list_iterator<T, const T&, const T*> const_iterator;
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;
}

Self& operator++()//前置++
{
_node = _node->_next;
return *this;
}
Self& operator--()//前置--
{
_node = _node->_prev;
return *this;
}
Self operator++(int)//后置++
{
Self ret(*this);
_node = _node->_next;
return ret;
}
Self operator--(int)//后置--
{
Self ret(*this);
_node = _node->_prev;
return ret;
}

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

Ptr operator->()
{
return &_node->_data;
}
};
//template<class T>
//struct list_const_iterator
//{
//typedef list_node<T> Node;
//typedef list_const_iterator Self;
//Node* _node;

//list_const_iterator(Node* node)
//:_node(node)
//{}

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

//Self& operator++()//前置++
//{
//_node = _node->_next;
//return *this;
//}
//Self& operator--()//前置--
//{
//_node = _node->_prev;
//return *this;
//}
//Self operator++(int)//后置++
//{
//Self ret(*this);
//_node = _node->_next;
//return ret;
//}
//Self operator--(int)//后置--
//{
//Self ret(*this);
//_node = _node->_prev;
//return ret;
//}

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

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

反向迭代器的实现
//template<class T>
//struct list_reserve_iterator
//{
////反向迭代器中仍然也是一个Node
//typedef list_node<T> Node;
//typedef list_reserve_iterator Self;
//Node* _node;

//list_reserve_iterator(Node* node)
//:_node(node)
//{}

//T& operator*()
//{
//return _node->_data;
//}
//Self& operator++()
//{
//_node = _node->_prev;
//return *this;
//}
//Self& operator--()
//{
//_node = _node->_next;
//return *this;
//}
//Self operator++(int)
//{
//Self tmp(*this);
//_node = _node->_prev;
//return tmp;
//}
//Self operator--(int)
//{
//Self tmp(*this);
//_node = _node->_next;
//return tmp;
//}

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

/
//重点：
template<class T>
class list
{
typedef list_node<T> Node;
private:
Node* _head;

public:
typedef list_iterator<T, T&, T*> iterator;
typedef list_iterator<T, const T&, const T*> const_iterator;
//typedef list_reserve_iterator<T> reserve_iterator;

iterator begin()
{
return iterator(_head->_next);
}
iterator end()
{
returniterator(_head);
}
const_iterator begin() const
{
return const_iterator(_head->_next);
}
const_iterator end() const
{
returnconst_iterator(_head);
}
//reserve_iterator rbegin()
//{
//return reserve_iterator(_head->_prev);;
//}
//reserve_iterator rend()
//{
//return reserve_iterator(_head);
//}

void empty_init()
{
_head = new Node();
_head->_next = _head;
_head->_prev = _head;
}
list()
{
empty_init();
}
//析构函数
iterator erase(iterator pos)
{
assert(pos != end());

//需要保存pos位置的上一个结点，以及下一个结点
Node* del = pos._node;
Node* prev = del->_prev;
Node* next = del->_next;

prev->_next = next;
next->_prev = prev;
delete del;
return iterator(next);
}
void clear()
{
auto it = begin();
while (it != end())
{
it = erase(it);
}
}
~list()
{
clear();

delete _head;
_head = nullptr;
}

//尾插
void push_back(const T& x)
{
/*Node* newnode = new Node(x);
Node* ptail = _head->_prev;
newnode->_prev = ptail;
newnode->_next = _head;

ptail->_next = newnode;
_head->_prev = newnode;*/

insert(end(), x);
}
//头插
void push_front(const T& x)
{
insert(begin(), x);
}
//n个val的构造
list(int n, const T& val = T())
{
empty_init();
for (size_t i = 0; i < n; i++)
{
push_back(val);
}
}
//解决浅拷贝问题
list(const list<T>& ls)
{
//直接尾插即可
empty_init();
for (auto e : ls)
{
push_back(e);
}
}
//赋值运算符重载
list<T>& operator=(list<T> ls)
{
swap(ls);
return *this;
}
//头删
void pop_front()
{
erase(begin());
}
//尾删
void pop_back()
{
erase(--end());
}
//在pos位置进行插入
iterator insert(iterator pos, const T& val = T())
{
Node* newnode = new Node(val);
Node* pcur = pos._node;
Node* prev = pcur->_prev;

newnode->_prev = prev;
newnode->_next = pcur;
prev->_next = newnode;
pcur->_prev = newnode;

return iterator(newnode);
}
//list类中实现的交换
void swap(list<T>& ls)
{
std::swap(_head, ls._head);
}
};

//库中的swap
template <class T>
void swap(T& a, T& b)
{
T c(a); a = b; b = c;
}
//自己定义的全局swap
template <class T>
void swap(list<T>& ls1, list<T>& ls2)
{
ls1.swap(ls2);
}
}

原文地址：https://blog.csdn.net/2301_79761834/article/details/142989310

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