【list】吃透这篇搞定 C++ list：从接口使用到 STL 源码手写，面试再也不慌
·
list
不支持通过下标访问（operator[ ]），不支持下标加减，支持++和–（访问下一个和前一个）
迭代器的分类
- 按照功能
- iterator
- reverse_iterator
- const iterator
- consr reverse_iterator
- 按照性质：
- 单向（forward iterator)：forward_list/unordered_map/unordered_set——>只支持++
- 双向(bidirectional iterator)：list/map/set——>支持++/–
- 随机（random access iterator）：string/vector/deque——>支持++/–/+/-
sort：只支持随机迭代器
template <class RandomAccessIterator> void sort (RandomAccessIterator first, RandomAccessIterator last);reverse ：支持随机和双向
template <class BidirectionalIterator>void reverse (BidirectionalIterator first, BidirectionalIterator last);find：都可（是InputIterator，是单向迭代器的子类）
emplace_back
- emplace_back和push_back的区别
struct A
{
public:
A(int a1=1,int a2=1)
:_a1(a1)
,_a2(a2)
{ }
private:
int _a1;
int _a2;
};
void test()
{
list<A>lt;
A a(1, 1);
lt.push_back(a);
lt.push_back(A(3, 4));//支持匿名对象
lt.emplace_back(a);
lt.emplace_back(A(3, 4));//支持匿名对象
lt.emplace_back( 3, 4 ); //支持直接传构造A的参数
}
实现中间插入
list 是不支持迭代器的+/-找到下标的，但我们也可以先通过其他方式找到下标，再insert
- 在下标为3的位置前面插入
void test1()
{
list<int>lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
auto it = lt.begin();
int k = 3;
while (k--)
{
it++;
}
lt.insert(it, 66);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
}
int main()
{
test1();
return 0;
}
erase
- 删除4：
- 要判断：
(it!=lt.end())，因为如果find没有找到，会返回最后一个迭代器
- 要判断：
it = find(lt.begin(), lt.end(), 4);
if(it!=lt.end())
{
lt.erase(it);
}
sort排序：升/降
-
升序：
lt.sort( ); -
降序：
greater<int>gt; lt.sort(gt);或者直接写成：
lt.sort(greater<int>())匿名对象
merge：合并链表
- A和B都是有序的才能合并
- A.merge(B)后**，B就没了**
list<int>lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
list<int>lt2;
lt2.push_back(3);
lt2.push_back(4);
lt2.push_back(5);
lt2.push_back(6);
lt.merge(lt2);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
unique：去重
- 必须是有序的才能使用（相同的值都挨在一起）——>先sort再去重
list<int>lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_back(5);
list<int>lt2;
lt2.push_back(3);
lt2.push_back(4);
lt2.push_back(5);
lt2.push_back(6);
lt.merge(lt2);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.unique();
for (auto e : lt )
{
cout << e << " ";
}
cout << endl;
1 2 3 3 4 4 5 5 6
1 2 3 4 5 6
remove：删除
传的是值，不是迭代器
lt.remove(2);
lt.remove(3);
splice：转移元素
3种用法：（被转移的结构的对应元素会消失）
entire list (1) //转移整个链表
void splice (iterator position, list& x);
single element (2) //转移单个迭代器位置的元素
void splice (iterator position, list& x, iterator i);
element range (3) //转移某个范围
void splice (iterator position, list& x, iterator first, iterator last);
举例：
构建一个1,2,3,4,5,6的链表：
list<int>lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt .push_back(5); lt .push_back(6);
- 将某个数字移到开头：
int x = 0; cin >> x; auto it = find(lt.begin(),lt.end(), x); ///void splice (iterator position, list& x, iterator i); lt.splice(lt.begin(), lt, it);
- 将某个数字及其之后的所有数字移到开头：
int x = 0; cin >> x; auto it = find(lt.begin(),lt.end(), x); ///void splice (iterator position, list& x, iterator first, iterator last); lt.splice(lt.begin(), lt, it, lt.end());
实现
list.h
在namespace lcj中，创建class list
- 先实现链表节点
list_node，为一个结构体（类），其中存 内容，上一个节点指针，下一个节点指针 - 实现list类：
list
namespace lcj
{
template<class T>
class list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;
};
template<class T>
class list
{
typedef list_node<T> Node;
public:
private:
Node* _head;
};
}
1.构造函数：
- 创建节点
- 将节点中的前后指针加上
_head = new Node; _head->_next = _head; _head->_prev = _head;
namespace lcj
{
template<class T>
class list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;
};
template<class T>
class list
{
typedef list_node<T> Node;
public:
list()//////////////////////////////////////////////////////////////
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
private:
Node* _head;
};
}
2.实现尾插：
实现size()和empty()
为了计数方便，增加_size
template<class T>
class list
{
typedef list_node<T> Node;
public:
private:
Node* _head;
size_t _size;/////////////////////////////////////////////////////////////
};
push_back
template<class T>
class list
{
typedef list_node<T> Node;
public:
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_head->_size =0;
}
void push_back(const T& x)
{
Node* newnode = new Node(x);
Node* tail = _head->_prev; // 先拿到原来的尾节点
newnode->_next = _head; // 新节点的后继指向头节点
newnode->_prev = tail; // 新节点的前驱指向旧尾
tail->_next = newnode; // 旧尾的后继指向新节点
_head->_prev = newnode; // 头节点的前驱指向新节点
++_size;
}
size_t size() const///////////////////////////
{
return _size;
}
bool empty() const//////////////////////////////
{
return _size == 0;
}
private:
Node* _head;
size_t _size;
};
3.实现迭代器
为什么要自己实现一个迭代器，因为list的节点在内存中不是线性存储的。如果是原来迭代器的一些操作，比如++、–，可能造成访问越界，所以我们要自己实现一个类，从而实现List的迭代器对应的操作
运算符重载函数，是专门为类类型准备的——>参数至少有一个自定义类型：不能参数全是 int、double 这种内置类型， 防止你修改 C++ 原本的语法。
代码+逐句讲解‼️
template<class T>
struct list_iterator//迭代器的类
{
typedef list_node<T> Node;//简化节点名称
Node* _node;//这是整个迭代器这个类中 唯一的成员变量
//为什么要有这个成员变量呢?
//因为我们知道迭代器的作用就是返回一个节点的指针，
//所以我们创造这个成员变量，
//然后呢，在后面的操作中直接对这个指针进行修改，
// 然后可以直接返回它
typedef list_iterator Self; //简化迭代器这个名字，在迭代器最低的类中，就叫self
list_iterator(Node* node)//迭代器这个类的 构造函数——>支持list类中的这样 iterator it(_head->_next);的使用。用来在类外把对应的节点指针变成迭代器
:_node(node)
{ }
T& operator*()//*解引用的运算符重载，直接返回list对应的数据_data
{
return _node->_data;
}
Self operator++()//返回下一个节点的迭代器，返回的是迭代器这个类，
{
_node = _node->_next;
return *this;
}
Self& operator--()
{
_node = _node->_prev;
return *this;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
bool operator==(const Self& s)const
{
return _node == s._node;
}
};
struct 和class：
- struct类，不加访问限定符，纯公有
- class，不加，纯私有
1.为什么list_node用 struct？
节点类是一个纯数据结构，它的三个成员_data、_prev、_next，需要被list类和list_iterator类随时随地直接读写。
2. 为什么list_iterator用 struct？
它的核心成员_node指针，需要被list类的成员函数（begin()、end()、insert()、erase()）直接访问。比如：
``bool operator!=(const Self& s) { return _node != s._node; }
把list_node改为struct
struct list_node
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;
};
test_list1()
void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
push_back上面说了，
接下来，想要实现：list<int>::iterator it = lt.begin();，就要先实现
- 迭代器iterator
- begin函数
-
Iterator是我们自己定义的一个类：
struct list_iterator//迭代器，然后再list这个类中typedef出来的名称-
我们是这样创建list的迭代器的，
list<int>::iterator it = lt.begin();，但看起来这个iterator它是在list类这个类里面的，可是我们知道并不是这样，——>因为
list类内部有一个typedef（类型别名），把外部的list_iterator<T>重命名成了内部的iterator。——>编译器会自动把它翻译成：
list_iterator<int> it = lt.begin();
-
构造函数的对比
-
每一个类都有对应的构造函数
-
构造一个节点的时候
list_node(const T& data = T()) :_data(data) ,_next(nullptr) ,_prev(nullptr) { } -
构造一个list的时候
list() { _head = new Node(T()); _head->_next = _head; _head->_prev = _head; _size = 0; } -
构造一个迭代器的时候
因为我们在实现begin、 and的时候，一般是这样的：
iterator it(_head->_next);return it;，所以迭代器的构造函数要是带参的
list_iterator(Node* node) :_node(node) { }
-
4.前一部分总代码+逐句讲解‼️
指针类型直接转化成了一个iterator这个类类型，相当于内置类型转化成类类型， 条件就是类有对应的构造函数就可以
namespace lcj
{
/////////////////////////////////////////////////////////////////////////////////////////////
template<class T>
struct list_node//节点的类
{
T _data;
list_node<T>* _prev;
list_node<T>* _next;
list_node(const T& data = T())//节点的实现，是一个默认 构造函数， 并且同时支持你传参和不传参都可以生成对应的节点
:_data(data)
,_next(nullptr)
,_prev(nullptr)
{ }
};
/////////////////////////////////////////////////////////////////////////////////////////////
template<class T>
struct list_iterator//迭代器的类
{
typedef list_node<T> Node;//简化节点名称
Node* _node;//这是整个迭代器这个类中 唯一的成员变量，是一个节点的指针。因为像是 ++、--、*这些操作，都需要通过这个指针找到对应的节点(Node* 类型)，然后返回对应的迭代器
typedef list_iterator Self; //在自己这个类中简化自己这个类的名称，然后在后面的++、--中，返回时也写得更方便一些
//传参传的是(_head->_next)这样的节点指针。
//用来在类外把对应的节点指针变成list_iterator迭代器这种类
list_iterator(Node* node)//迭代器这个类的 构造函数——>支持list类中的这样 iterator it(_head->_next);的使用
:_node(node)
{ }
T& operator*()//*的运算符重载，直接返回list对应的_data
{
return _node->_data;
}
Self& operator++()//++的运算符重载，返回对应的迭代器
{
_node = _node->_next;
return *this;
}
bool operator!=(const Self& s)//通过判断迭代器类（list_iterator）创建的对象 中唯一的成员变量_node ，来判断两个迭代器类（list_iterator）是否是相同的迭代 类 对象（list_iterator）
{
return _node != s._node;
}
};
/////////////////////////////////////////////////////////////////////////////////////////////
template<class T>
class list // 链表的类
{
typedef list_node<T> Node;//简化链节的写法
public:
list()// 构造函数，生成一个只有头节点的list
{
_head = new Node(T());
_head->_next = _head;
_head->_prev = _head;
_size = 0;
}
typedef list_iterator<T> iterator;//简化迭代器的写法，符合STL
iterator begin()//通过 节点指针，创造出一个迭代器类（iterator），然后返回这个迭代器类
{
iterator it(_head->_next);
return it;//编译器会做值拷贝，把局部迭代器里的_node指针复制给外面接收的变量
}
iterator end()//指向哨兵头节点（最后一个节点的下一个节点），作为遍历结束的标志，创造出一个迭代器类（iterator），然后返回这个迭代器类
{
return _head;
}
void push_back(const T& x)
{
Node* newnode = new Node(x);//创建节点,并且调用带参构造函数
Node* tail = _head->_prev; // 先拿到原来的尾节点
newnode->_next = _head; // 新节点的后继指向头节点
newnode->_prev = tail; // 新节点的前驱指向旧尾
tail->_next = newnode; // 旧尾的后继指向新节点
_head->_prev = newnode; // 头节点的前驱指向新节点
++_size;
}
size_t size()
{
return _size;
}
bool empty() const
{
return _size == 0;
}
private:
Node* _head;
size_t _size;
};
void test_list1()
{
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
list<int>::iterator it = lt.begin();
while (it != lt.end())
{
cout << *it << " ";
++it;
}
cout << endl;
}
}
5.实现insert
通过insert实现push_front和push_back
void insert(iterator pos, const T& x)
{
Node* cur = pos._node;///这里应该写成.而不是->，因为 pos是个类（结构体），_node是结构体的成员变量
Node* prev = cur->_prev;
Node* newnode = new Node(x);
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
prev->_next = newnode;
++_size;
}
void push_front(const T& x)
{
insert(begin(), x);
}
void push_back(const T& x)
{
insert(end(), x);
}
6.实现erase
通过erase实现pop_back
通过erase实现pop_front
void erase(iterator pos)
{
assert(pos != end());///end是哨兵位头节点
///迭代器只是一个类，想要访问对应的节点需要访问其中的_node成员变量
Node* prev = pos._node->_prev;
Node* next= pos._node->_next;
prev->_next = next;
next->_prev = prev;
delete pos._node;
--_size;
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(begin());
}
7.重载->
想打印一个结构体的类，而且
如下，我定义了一个结构体struct AA，创建了对应的list：list<AA> lta，
想打印，
- 方法一：当然可以先：
list<AA>::iterator it = lta.begin();，找到对应元素的指针（AA类的指针），然后解引用，得到一个AA类，然后通过“.”来访问对应的_a1和_a2 - 方法二：list的迭代器，就是一个结构AA对象的地址——>通过“->”，像访问一个结构体一样访问不行吗？不行🙅♀️，因为这时候list的迭代器并不是地址，而是一个类，所以不能用“->”
struct AA
{
int _a1=1;
int _a2=2;
};
list<AA> lta;
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());
list<AA>::iterator it = lta.begin();
while (it != lta.end())
{
///使用.的方法
cout << (*it)._a1 << " : " << (*it)._a2 << endl;
❌❌❌///使用->的方法：重载
cout<< it->_a1 << " : " << _a2 << endl;
}
cout << endl;
实现
‼️operator->必须返回指向数据的指针，而我之前犯错：返回的了数据本身（_node->_data是T类型，不是T*）。
实际上的访问应该是这样的：
cout << it.operator->()->_a1 << " : " << it.operator->()->_a1 << endl;
it.operator->()返回对应的_data的指针，->_a1相当于就是对结构体指针进行了“->”操作
但是编辑器省略了一个“->”，只需要这样写就行：
cout<< it->_a1 << " : " << it->_a2 << endl;
///list_iterator 模板
template<class T>
struct list_iterator
{
typedef list_node<T> Node;
typedef list_iterator Self;
Node* _node;
T* operator->()/////////////////////////////////////////////////////////////////
{
return & _node->_data; ///operator->必须返回指向数据的指针
}
};
………………
struct AA
{
int _a1=1;
int _a2=2;
};
void test_list1()
{
list<AA> lta;
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());
lta.push_back(AA());
list<AA>::iterator it = lta.begin();
while (it != lta.end())
{
///使用.的方法
cout << (*it)._a1 << " : " << (*it)._a2 << endl;
///使用->的方法：重载
cout<< it->_a1 << " : " << it->_a2 << endl;
++it;
}
cout << endl;
}
8.实现const_iterator
之前我们在实现vector中实现的print_container在这里用不了了，原因是没有实现const迭代器
template<class Container>
void print_container(const Container& con)
{
for (auto e : con)
{
cout << e << " ";
}
cout << endl;
}
更多推荐
7
0- 0
已为社区贡献14条内容
所有评论(0)