feng

started from 11.28.2025

首页·个人博客

List

list是用来补充vector的缺点而存在的.vector的缺点有

  • 头插和中部插入删除效率低,达到\(O(N)\)级,因为需要整体挪动数据.
  • 插入数据时需要增容,增容需要拷贝数据和旧空间的释放导致效率的降低.

优点是vector支持随机访问,间接就很好的支持了排序,二分查找,堆算法等.

List的构造

Pasted image 20260131141723.png

List实际上是一个带头的双向循环链表顺序表和链表

int main()
{
    list<int> l;
    l.push_back(1);
    l.push_back(2);
    l.push_back(3);
    l.push_back(4);
    l.push_front(0);
    l.push_front(-1);
    l.push_front(-2);
    l.push_front(-3);
    for (auto e : l)
    {
        cout << e << " ";
    }
    return 0;
}

对于链表而言,可以实现头插头删和尾插尾删

List的访问

对于链表而言,不再支持随机访问(operator[]).所以链表的访问只能通过迭代器实现.
List的迭代器也有三类,分别为常规迭代器,反向迭代器和const迭代器.

//常规迭代器
list<int>::iterator lt= l.begin();
while (lt != l.end())
{
    cout << *lt << " ";
    lt++;
}
//反向迭代器
list<int>::reverse_iterator rlt = l.rbegin();
while (rlt != l.rend())
{
    cout << *rlt << " ";
    rlt++;
}
//const迭代器
void print_list(const list<int>& l)
{
    list<int>::const_iterator clt = l.begin();
    while (clt != l.end())
    {
        cout << *clt << " ";
        clt++;
    }
}

List的迭代器和之前几个容器并不相同,等模拟实现的时候细说.由于List是不支持随机访问的,所以它的迭代器不能直接用加法访问,
现在我要在链表\(-3\rightarrow -2\rightarrow -1\rightarrow 1\rightarrow2\rightarrow3\)这个链表的-1后面插一个0

l1.insert(l1.begin() + 4, 0);//err

这样是不允许的.因为不支持随机访问,那么要实现这个目标只能使用查找

list<int>::iterator pos = find(l1.begin(), l1.end(), 1);
if(pos!=l1.end())
    l1.insert(pos, 0);

我在执行insert后,迭代器有没有失效?vector.答案是没有,原因是list的插入是创建一个新结点,然后通过修改指针去把这个新结点连接进去,不存在扩容,也不存在新空间.那么迭代器指的位置就是正确的位置,就不会失效.
但是如果现在我要删除链表的偶数,如果直接写也会造成迭代器失效

void test_list2()
{
    list<int> l1;
    l1.push_back(1);
    l1.push_back(2);
    l1.push_back(3);
    l1.push_back(4);
    l1.push_back(5);
    l1.push_back(6);
    l1.push_back(7);
    l1.push_back(8);
    list<int>::iterator it = l1.begin();
    while (it != l1.end())
    {
        if (*it % 2 == 0)
        {
            l1.erase(it);
        }
        it++;
        print_list(l1);
    }
}

当把it这个空间释放后,it指向的位置已经是一个释放的空间了,这个时候再去++就会出问题.所以每次删完需要把让it重新指向正确的空间.调用erase后会返回删除结点的下一个结点,所以把这个返回值传给it即可.

while (it != l1.end())
    {
        if (*it % 2 == 0)
        {
            it=l1.erase(it);
        }
        else
	        it++;
        print_list(l1);
    }

访问操作还有

Pasted image 20260201114226.png

List的容量操作

对于链表而言,并不存在增容操作,容量相关的有

Pasted image 20260201114209.png

empty:判空,size:返回元素个数,max_size没有意义

List的操作接口

List支持头插,头删,尾插,尾删

void push_front (const value_type& val);
void pop_front();
void push_back (const value_type& val);
void pop_back();

以及插入

Pasted image 20260201114451.png

删除

iterator erase (iterator position);
iterator erase (iterator first, iterator last);

这两个接口的位置均是以迭代器的方式传入的.
查找.在list中并没有提供,但是在algorithm里面提供了统一的查找接口

template<class InputIterator, class T>
InputIterator find (InputIterator first, InputIterator last, const T& val)
{
  while (first!=last) {
    if (*first==val) return first;
    ++first;
  }
  return last;
}

通过迭代器传入查找的范围(左闭右开)和目标值,返回目标位置的迭代器.如果没有找到就返回end()

List的模拟实现

List源码

首先定义了一个结点

struct __list_node {
  typedef void* void_pointer;
  void_pointer next;
  void_pointer prev;
  T data;
};

然后定义链表类(已删减)

class list {
protected:
  typedef void* void_pointer;
  typedef __list_node<T> list_node;
  typedef list_node* link_type;
public:      
  typedef T value_type;
public:
  typedef __list_iterator<T, T&, T*>             iterator;
  typedef __list_iterator<T, const T&, const T*> const_iterator;
protected:
  link_type node;

在链表中定义了一个link_type类型的node,这个node是一个list_node*的指针,指向一个结点.
迭代器的定义如下

struct __list_iterator {
  typedef __list_iterator<T, T&, T*>             iterator;
  typedef __list_iterator<T, const T&, const T*> const_iterator;
  typedef __list_iterator<T, Ref, Ptr>           self;
  link_type node;
}

它底层是一个link_type类型的node,所以本质上还是一个结点指针.但是这个指针和前面学到的迭代器的区别在于它是一个自定义类型的指针.对于链表而言,如果想要访问下一个元素,我们要做的应该是

a=a->next;

并且这个指针是指向结点的,我们希望的是解引用得到的是这个结点的值而不是这个结点,所以我们就可以使用C++入门去重载指针的各个操作.

reference operator*() const { return (*node).data; }
self& operator++() { 
    node = (link_type)((*node).next);//等价于node->next
    //由于next定义为void*类型,所以需要强转成link_type才能幅值到node
    return *this;
  }
  self operator++(int) { 
    self tmp = *this;
    ++*this;
    return tmp;
  }
  self& operator--() { 
    node = (link_type)((*node).prev);
    return *this;
  }
  self operator--(int) { 
    self tmp = *this;
    --*this;
    return tmp;
  }
};

这样它就能够像普通指针去使用.

List模拟实现

链表的结构定义

首先定义一个结点,由于是一个双向循环链表,这个结点需要有前驱和后继,还有构造这个结点的构造函数

struct __list_node
{
	__list_node<T>* _next;
	__list_node<T>* _prev;
	T _data;
	
	__list_node(const T& x=T())
	:_next(nullptr), _prev(nullptr), _data(x)
{}
};

然后定义链表

template<class T>
class list {
	typedef __list_node<T> Node;
public:
private:
	Node* _head;
};

构造函数与析构函数

构造函数:new一个结点给头节点,然后前驱后继分别指向自己来说明是一个空链表

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

对于析构函数,它需要清理掉所有数据,所以可以先写一个清理数据的函数

void clear()
{
	iterator it = begin();
	while (it != end())
	{
		erase(it++);
	}
}

然后析构函数只需要删除头节点即可

~list()
{
	clear();
	delete _head;
	_head = nullptr;
}

拷贝构造,为了实现深拷贝,我们可以创建一个头节点,然后遍历原链表进行尾插.

list(const list<T>& l)
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;
	list<T>::const_iterator it = l.begin();
	while (it != l.end())
	{
		this->push_back(*it);
		it++;
	}
}

赋值

list<T>& operator=(const list<T>& l)
{
	if (this != &l)
	{
		clear();
		for (auto e : l)
		{
			push_back(e);
		}
	}
	return *this;
}

同样的也可以使用String

list<T>& operator=(list<T> l)
{
	swap(_head, l._head);
	return *this;
}

增删查改

1.尾插:void push_back(const T& x)
首先需要找到尾.对于双向循环链表而言,尾其实就是头的前驱

node* tail = _head->_prev;

然后给x创建一个结点

Node* newNode = new Node(x);

然后把newNode连接到tail的后面

tail->_next = newNode;
newNode->_prev = tail;
newNode->_next = _head;
_head->prev = newNode;

所以尾插为

void push_back(const T& x)
{
	Node* tail = _head->_prev;
	Node newNode = new Node(x);
	tail->_next = newNode;
	newNode->_prev = tail;
	newNode->_next = _head;
	_head->_prev = newNode;
}

2.插入insert

void insert(iterator pos,const T&val)
{
	Node* cur = pos._node;
	Node* newnode = new Node(val);
	cur->_prev->_next = newnode;
	newnode->_prev = cur->_prev;
	newnode->_next = cur;
	cur->_prev = newnode;
}

那么尾插就可以复用了

void push_back(const T& x)
{
	insert(end(),x);
}

对于迭代器来说,end()实际上是最后一个位置的下一个位置,也就是头节点,所以在end()前插入就是尾插.
3.头插,也是直接复用insert

void push_front(const T& x)
{
	insert(begin(),x);
}

4.erase

iterator erase(iterator pos)
{
	assert(pos != end());
	Node* cur = pos._node;
	Node* next = cur->_next;
	Node* prev = cur->_prev;
	prev->_next = next;
	next->_prev = prev;
	delete cur;
	return iterator(next);
}

5.尾删,直接复用erase

void pop_back()
{
	erase(iterator(_head->_prev));
}

6.头删

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

迭代器

迭代器的本质是一个node指针,所以我们先定义出来

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 operator++()
{
	_node = _node->_next;
	return *this;
}
__list_iterator operator++(int)
{
	__list_iterator tmp(*this);
	_node = _node->_next;
	return tmp;
}
__list_iterator operator--()
{
	_node = _node->_prev;
	return *this;
}
__list_iterator operator--(int)
{
	__list_iterator tmp(*this);
	_node = _node->_prev;
	return tmp;
}

还有相等与不相等,实际上判断的是底下的指针是否相等

bool operator!=(const __list_iterator<T>& it)
{
	return _node != it._node;
}
bool operator==(const __list_iterator<T>& it)
{
	return _node == it._node;
}

完成迭代器的定义后还我们要在链表类中使用它.所以还需要在链表类中定义迭代器,使用begin和end去构造迭代器

public:
	typedef __list_iterator<T> iterator;
	iterator begin()
	{
		return iterator(_head->_next);
	}
	iterator end()
	{
		return iterator(_head);
	}

对于迭代器来说,我们模拟的是指针的行为,假如我们的list用来存储了一个自定义类型

class Date()
{
private:
	_Year;
	_Month;
	_Day;
}

现在我们利用迭代器遍历的时候为了能够访问Date的成员,我们需要

it->_Year;

所以就需要对->进行重载

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

但是这里依然不太对.我调用it->实际上调用的是

it.operator->();

那么返回的实际上是

it.Date;

所以我要访问_Year应该写成

it->->_Year;

但是为了可读性,编译器会帮我们做优化,优化为

it->_Year;

实际上也可以写成

(*it)._Year;

然后是const迭代器,我们直接把begin和end加上const修饰

iterator begin() const
{
	return iterator(_head->_next);
}
iterator end() const
{
	return iterator(_head);
}

然后调用

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

我们发现可以正常打印,但是如果我在这里面对*it进行修改时仍然可以进行修改,也就是说const没有发生作用,因为调用begin返回的是个普通迭代器,而不是const迭代器.所以我们还需要定义一个const类型的迭代器.对于const类型迭代器来说,和普通迭代器没有什么区别, 除了operator*和operator->的返回值需要是const类型.我们完全可以直接把之前的代码拷贝一份,但是代码就太过冗余,所以我们可以通过调整模板参数来实现.

template <class T,class Ref,class Ptr>

我们定义三个模板参数T,Ref,Ptr,然后在链表中调用的时候定义两种迭代器,一种是普通迭代器,一种是const迭代器,通过传入不同的参数来对迭代器类型进行区分.

__list_iterator<T,T&,T*>
__const_list_iterator<T,const T&,const T*>

最终获得完整的迭代器部分代码

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;
	}
	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)
	{
		return _node != it._node;
	}
	bool operator==(const Self& it)
	{
		return _node == it._node;
	}
};
//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;
//....
← 上一篇:
下一篇: →