首页 > 编程语言 >揭秘 C++ List 容器背后的实现原理，带你构建自己的双向链表

揭秘 C++ List 容器背后的实现原理，带你构建自己的双向链表

时间：2024-09-09 12:24:33浏览次数：9  
标签：node head const iterator List C++ next 链表 prev

本篇博客，我们将详细讲解如何从头实现一个功能齐全且强大的 C++ List 容器，并深入到各个细节。这篇博客将包括每一步的代码实现、解释以及扩展功能的探讨，目标是让初学者也能轻松理解。


一、简介

1.1、背景介绍

在 C++ 中，std::list 是一个基于双向链表的容器，允许高效的插入和删除操作，适用于频繁插入和删除操作的场景。与动态数组不同，list 允许常数时间内的插入和删除操作，支持双向遍历。这篇文章将详细讲解如何实现一个自定义的 List 容器，涵盖模板、迭代器、双向链表的核心技术，并逐步扩展其功能，达到媲美标准库的效果。


1.2、学习目标

通过阅读本文，您将掌握以下技能：

  • 如何从零开始实现一个功能齐全的 C++ List 容器。
  • 理解 C++ 中动态内存分配的机制，并学习如何防止内存泄漏。
  • 学会运算符重载的正确使用方式。
  • 实现 C++ 类的拷贝构造函数、赋值运算符。
  • 深入理解迭代器设计，实现迭代器功能
  • 简化代码逻辑，复用代码

1.3、代码仓库

这篇博客所涉及的所有代码可以从我的代码仓库获得：https://git.lenyiin.com/Lenyiin/List


二、双向链表的基本结构

要实现一个 List 容器，首先要理解双向链表的数据结构。在链表中，每个节点都包含数据和指向前后节点的指针。双向链表的优点是可以在常数时间内从任意位置插入和删除元素，缺点是不能像数组一样高效地随机访问元素。


2.1、基本节点结构

我们首先定义一个表示链表节点的结构体。该结构体包含三个重要成员：存储数据的 data，指向前一个节点的 prev 指针，以及指向下一个节点的 next 指针。我们可以使用一个模板类来实现这一结构，使得 List 能够存储任何类型的元素。

template <class T>
struct __list_node
{
	__list_node<T>* _next;
	__list_node<T>* _prev;
	T _data;

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

template <class T>
class List
{
	typedef __list_node<T> Node;

public:
	// 带头双向循环链表
	// 默认构造
    List()
    {
        _head = new Node;
        _head->_next = _head;
        _head->_prev = _head;
    }
    
    // 析构函数
    ~List()
    {
        clear();
        delete _head;
        _head = nullptr;
    }
    
private:
	Node* _head;
};

详细解释：

  1. 节点结构：每个 __list_node 包含一个数据元素 _data，以及两个指针 _prev 和 _next，分别指向前一个节点和后一个节点。
  2. 构造函数与析构函数：我们初始化链表为空，并在析构函数中清空链表，确保不产生内存泄漏。

2.2、拷贝构造和赋值运算

拷贝构造函数用于创建一个新对象，该对象是通过复制另一个现有对象生成的。对于 List 类，我们需要确保在拷贝时，新对象有自己独立的内存副本。

// 拷贝构造
List(const List<T>& lt)
{
	_head = new Node;
	_head->_next = _head;
	_head->_prev = _head;

	for (const auto& e : lt)
	{
		push_back(e);
	}
}

详细解释：

  • 深拷贝：通过分配新内存来创建新对象的独立副本，而不是简单地复制指针。这样，两个 List 对象可以独立管理各自的内存，避免潜在的内存管理冲突。
// 赋值运算符
List<T>& operator=(const List<T>& lt)
{
	if (this != &lt)
	{
		clear();
		for (const auto& e : lt)
		{
			push_back(e);
		}
	}
	return *this;
}

赋值运算符用于将一个对象的内容复制到另一个已经存在的对象中。为了避免自赋值和内存泄漏，我们需要在实现赋值运算符时特别小心。

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

详细解释：

  • 自赋值检查：在赋值运算符实现中，首先检查是否为自赋值，即 this 指针是否与 lt 相同。如果是自赋值，则无需进行任何操作，直接返回当前对象。
  • 内存管理：在分配新内存之前，记得释放当前对象所持有的旧内存，防止内存泄漏。
  • 深拷贝：与拷贝构造函数类似，通过分配新内存来存储字符串的副本，确保两个对象独立管理各自的内存。

进阶：

  • 也可以复用拷贝构造函数，直接交换拷贝构造的数据
// 进阶写法
List<T>& operator=(List<T> lt)
{
	std::swap(_head, lt._head);
	return *this;
}

2.3、基础功能：添加和删除元素

双向链表的主要优势在于可以在常数时间内插入和删除元素。我们将实现 push_back 和 push_front 函数用于分别在链表尾部和头部插入元素，同时实现 pop_back 和 pop_front 用于删除元素。

2.3.1、头插、尾插

push_back 函数用于在链表尾部插入新元素。

// 结构设计的优势, 有没有数据, 插入的逻辑都是一样的
void push_back(const T& data)
{
	Node* tail = _head->_prev;
	Node* newnode = new Node(data);
	tail->_next = newnode;
	newnode->_prev = tail;
	newnode->_next = _head;
	_head->_prev = newnode;
}

push_front 函数用于在链表头部插入新元素。

void push_front(const T& data)
{
	Node* cur = _head->_next;
	Node* newnode = new Node(data);

	_head->_next = newnode;
	newnode->_prev = _head;
	newnode->_next = cur;
	cur->_prev = newnode;
}

详细解释：

  1. push_back：因为是带头的双向循环链表，所以不管是空链表还是非空链表，插入逻辑都是一样的。
  2. push_front：类似 push_back，相同的插入逻辑。

2.3.2、头删、尾删

删除操作包括从链表的头部和尾部移除节点，这里分别通过 pop_back 和 pop_front 函数实现。

void pop_back()
{
	Node* tail = _head->_prev;
	Node* prev = tail->_prev;

	delete tail;
	prev->_next = _head;
	_head->_prev = prev;
}

void pop_front()
{
	Node* head = _head->_next;
	Node* next = head->_next;

	delete head;
	_head->_next = next;
	next->_prev = _head;
}

详细解释：

  1. pop_front：从头部删除节点。
  2. pop_back：从尾部删除节点。

三、进阶功能

3.1、双向迭代器的实现

为了让 List 支持 for-each 这样的遍历操作，我们需要实现迭代器。链表的迭代器允许我们像操作数组一样顺序访问链表中的每一个节点。

3.1.1、基本正向迭代器结构

迭代器类封装了对节点的操作，支持解引用和递增操作。

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)
	{
	}

	// 运算符重载
	// *it
	Ref operator*()
	{
		return _node->_data;
	}

	// it ->
	Ptr operator->()
	{
		return &_node->_data;
	}

	// ++it
	Self& operator++()
	{
		_node = _node->_next;
		return *this;
	}

	// it++
	Self operator++(int)
	{
		Self tmp(*this);
		++(*this);
		return tmp;
	}

	// --it
	Self& operator--()
	{
		_node = _node->_prev;
		return *this;
	}

	// it--
	Self operator--(int)
	{
		Self tmp(*this);
		--(*this);
		return tmp;
	}

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

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

详细解释：

  1. __list_iterator类：封装了指向节点的指针，并实现了解引用操作符 * 和递增操作符 ++，使得可以通过 for 循环遍历链表。

3.1.2、iterator && const_iterator

typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

iterator begin()	// 返回头节点的下一个节点
{
	return iterator(_head->_next);
}

iterator end()	// 返回头节点
{
	return iterator(_head);
}

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

const_iterator end() const
{
	return const_iterator(_head);
}

详细解释：

  1. begin 和 end：begin 返回指向头节点下一个节点的迭代器，end 返回指向头的迭代器，表示链表的结束。

3.1.3、反向迭代器结构

有时候，我们需要从后向前遍历链表。为此，我们可以实现反向迭代器，允许从尾部向头部遍历。反向迭代器与正向迭代器迭代方向相反，但逻辑不变。

我们继续完善反向迭代器，使其支持与普通迭代器相同的操作，包括前置和后置递减（--）、比较操作符等。这样，链表可以从尾部向头部遍历，增强了容器的灵活性。

template <class T, class Ref, class Ptr>
struct __list_reverse_iterator
{
	typedef __list_node<T> Node;
	typedef __list_reverse_iterator<T, Ref, Ptr> Self;

	Node* _node;

	// 默认构造
	__list_reverse_iterator(Node* node)
		: _node(node)
	{
	}

	// 运算符重载
	// *it
	Ref operator*()
	{
		return _node->_data;
	}

	// it ->
	Ptr operator->()
	{
		return &_node->_data;
	}

	// ++it
	Self& operator++()
	{
		_node = _node->_prev;
		return *this;
	}

	// it++
	Self operator++(int)
	{
		Self tmp(*this);
		++(*this);
		return tmp;
	}

	// --it
	Self& operator--()
	{
		_node = _node->_next;
		return *this;
	}

	// it--
	Self operator--(int)
	{
		Self tmp(*this);
		--(*this);
		return tmp;
	}

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

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

详细解释：

  1. __list_reverse_iterator类：封装了指向节点的指针，并实现了解引用操作符 * 和递增操作符 ++，使得可以通过 for 循环遍历链表。

3.1.4、reverse_iterator && const_reverse_iterator

typedef __list_reverse_iterator<T, T&, T*> reverse_iterator;
typedef __list_reverse_iterator<T, const T&, const T*> const_reverse_iterator;

reverse_iterator rbegin()	// 返回头节点的下一个节点
{
	return reverse_iterator(_head->_prev);
}

reverse_iterator rend()	// 返回头节点
{
	return reverse_iterator(_head);
}

const_reverse_iterator rbegin() const
{
	return const_reverse_iterator(_head->_prev);
}

const_reverse_iterator rend() const
{
	return const_reverse_iterator(_head);
}

详细解释：

  1. rbegin 和 rend：rbegin 返回指向尾节点的迭代器，rend 返回指向头的迭代器，表示链表的结束。

3.2、模板支持与代码复用

为了使 List 容器能够支持任意类型的元素存储，我们使用 C++ 模板来实现这一功能。通过模板，List 可以适应不同类型的数据，而不需要为每种类型单独实现一个类。

template <typename T>
class List {
    // 内部结构与之前相同
};

模板化后的 List 容器可以在实例化时指定存储的数据类型，如 List<int> 或 List<std::string>。


3.3、插入和删除任意位置的元素

为了使 List 更加灵活，我们还需要支持在链表中任意位置插入和删除元素。我们需要实现 insert 和 erase 函数。这些操作的实现与头部和尾部的插入删除操作类似，但更加通用。通过迭代器，我们可以确定插入或删除的具体位置。

3.3.1、在任意位置插入元素

我们通过传入迭代器的位置，在链表的任意位置插入一个新元素。

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

	// prev newnode cur
	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;
}

详细解释：

  1. insert：在给定的迭代器位置 pos 插入一个新节点。先调整新节点与前后节点的指针关系，再插入节点。

3.3.2、在任意位置删除元素

iterator erase(iterator pos)
{
	assert(pos != end());

	Node* cur = pos._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;
	delete cur;

	prev->_next = next;
	next->_prev = prev;

	return next;
}

详细解释：

  1. erase：删除 pos 位置上的节点，更新前后节点的指针，使其指向彼此，完成删除。

3.3.3、复用任意位置的插入和删除

我们还可以直接复用插入和删除，直接重写头插、尾插、头删、尾删，以简化代码逻辑。

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

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

void pop_back()
{
	erase(--end());
}

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

3.3.4、clear

clear 函数能够清除所有节点

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

四、迭代器兼容性与异常安全

为了让 List 更加健壮，我们需要确保在插入或删除元素时迭代器不会失效。我们还需要考虑异常安全性，确保在操作失败或异常抛出时，链表的状态能够保持一致。

4.1、迭代器失效问题

当链表在操作过程中插入或删除元素时，特别是在 insert 和 erase 操作后，指向旧节点的迭代器可能会失效。为了解决这个问题，我们需要更新受影响的迭代器，或者确保不会对现有的迭代器产生副作用。

4.2、异常安全性

在插入或删除操作时，若发生异常（例如内存分配失败），我们要确保链表不会处于不一致的状态。我们可以通过在执行插入和删除操作时，分阶段更新链表的指针关系，确保每一步都能保持链表结构的完整性。


五、完整实现代码和测试

5.1、List.hpp

新建头文件 List.hpp

#pragma once


#include <iostream>
#include <assert.h>

using namespace std;

namespace Lenyiin
{
	template <class T>
	struct __list_node
	{
		__list_node<T>* _next;	// 指向后一个节点的指针
		__list_node<T>* _prev;	// 指向前一个节点的指针
		T _data;	// 节点存储的数据

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

	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)
		{
		}

		// 运算符重载
		// *it
		Ref operator*()
		{
			return _node->_data;
		}

		// it ->
		Ptr operator->()
		{
			return &_node->_data;
		}

		// ++it
		Self& operator++()
		{
			_node = _node->_next;
			return *this;
		}

		// it++
		Self operator++(int)
		{
			Self tmp(*this);
			++(*this);
			return tmp;
		}

		// --it
		Self& operator--()
		{
			_node = _node->_prev;
			return *this;
		}

		// it--
		Self operator--(int)
		{
			Self tmp(*this);
			--(*this);
			return tmp;
		}

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

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

	template <class T, class Ref, class Ptr>
	struct __list_reverse_iterator
	{
		typedef __list_node<T> Node;
		typedef __list_reverse_iterator<T, Ref, Ptr> Self;

		Node* _node;

		// 默认构造
		__list_reverse_iterator(Node* node)
			: _node(node)
		{
		}

		// 运算符重载
		// *it
		Ref operator*()
		{
			return _node->_data;
		}

		// it ->
		Ptr operator->()
		{
			return &_node->_data;
		}

		// ++it
		Self& operator++()
		{
			_node = _node->_prev;
			return *this;
		}

		// it++
		Self operator++(int)
		{
			Self tmp(*this);
			++(*this);
			return tmp;
		}

		// --it
		Self& operator--()
		{
			_node = _node->_next;
			return *this;
		}

		// it--
		Self operator--(int)
		{
			Self tmp(*this);
			--(*this);
			return tmp;
		}

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

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

	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;
		typedef __list_reverse_iterator<T, T&, T*> reverse_iterator;
		typedef __list_reverse_iterator<T, const T&, const T*> const_reverse_iterator;

		iterator begin()	// 返回头节点的下一个节点
		{
			return iterator(_head->_next);
		}

		iterator end()	// 返回头节点
		{
			return iterator(_head);
		}

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

		const_iterator end() const
		{
			return const_iterator(_head);
		}

		reverse_iterator rbegin()	// 返回头节点的下一个节点
		{
			return reverse_iterator(_head->_prev);
		}

		reverse_iterator rend()	// 返回头节点
		{
			return reverse_iterator(_head);
		}

		const_reverse_iterator rbegin()	const
		{
			return const_reverse_iterator(_head->_prev);
		}

		const_reverse_iterator rend() const
		{
			return const_reverse_iterator(_head);
		}

	public:
		// 带头双向循环链表
		// 默认构造
		List()
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;
		}

		// 拷贝构造
		List(const List<T>& lt)
		{
			_head = new Node;
			_head->_next = _head;
			_head->_prev = _head;

			for (const auto& e : lt)
			{
				push_back(e);
			}
		}

		// 赋值运算符
		//List<T>& operator=(const List<T>& lt)
		//{
		//	if (this != &lt)
		//	{
		//		clear();
		//		for (const auto& e : lt)
		//		{
		//			push_back(e);
		//		}
		//	}
		//	return *this;
		//}

		// 进阶写法
		List<T>& operator=(List<T> lt)
		{
			std::swap(_head, lt._head);
			return *this;
		}

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

		// 析构函数
		~List()
		{
			clear();
			delete _head;
			_head = nullptr;
		}

		// 结构设计的优势, 有没有数据, 插入的逻辑都是一样的
		//void push_back(const T& data)
		//{
		//	Node* tail = _head->_prev;
		//	Node* newnode = new Node(data);
		//	tail->_next = newnode;
		//	newnode->_prev = tail;
		//	newnode->_next = _head;
		//	_head->_prev = newnode;
		//}

		//void push_front(const T& data)
		//{
		//	Node* cur = _head->_next;
		//	Node* newnode = new Node(data);

		//	_head->_next = newnode;
		//	newnode->_prev = _head;
		//	newnode->_next = cur;
		//	cur->_prev = newnode;
		//}

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

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

		//void pop_back()
		//{
		//	Node* tail = _head->_prev;
		//	Node* prev = tail->_prev;

		//	delete tail;
		//	prev->_next = _head;
		//	_head->_prev = prev;
		//}

		//void pop_front()
		//{
		//	Node* head = _head->_next;
		//	Node* next = head->_next;

		//	delete head;
		//	_head->_next = next;
		//	next->_prev = _head;
		//}

		void pop_back()
		{
			erase(--end());
		}

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

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

			// prev newnode cur
			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;
		}

		iterator erase(iterator pos)
		{
			assert(pos != end());

			Node* cur = pos._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;
			delete cur;

			prev->_next = next;
			next->_prev = prev;

			return next;
		}

	private:
		Node* _head;
	};
}

5.2、List.cpp

新建源文件 List.cpp

#include "List.hpp"

using namespace Lenyiin;

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

void print_reverse(const List<int>& lt)
{
    List<int>::const_reverse_iterator it = lt.rbegin();
    while (it != lt.rend())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

// 测试遍历
void test_1()
{
    List<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);

    // iterator
    cout << "iterator \t\t遍历: ";
    List<int>::iterator it = lt.begin();
    while (it != lt.end())
    {
        cout << *it << " ";
        it++;
    }
    cout << endl;

    // const_iterator
    cout << "const_iterator \t\t遍历: ";
    print(lt);

    // for
    cout << "for \t\t\t遍历: ";
    for (auto& it : lt)
    {
        cout << it << " ";
    }
    cout << endl;

    cout << "for const \t\t遍历: ";
    for (const auto& it : lt)
    {
        cout << it << " ";
    }
    cout << endl;

    // reverse iterator
    cout << "reverse iterator \t遍历: ";
    List<int>::reverse_iterator rit = lt.rbegin();
    while (rit != lt.rend())
    {
        cout << *rit << " ";
        rit++;
    }
    cout << endl;

    // const reverse iterator
    cout << "const reverse iterator \t遍历: ";
    print_reverse(lt);
}

// 测试插入删除
void test_2()
{
    List<int> lt;
    lt.push_back(1);
    lt.push_back(2);
    lt.push_back(3);
    lt.push_back(4);
    lt.push_back(5);

    print(lt);

    lt.erase(lt.begin());
    print(lt);

    lt.pop_back();
    print(lt);

    lt.pop_front();
    print(lt);

    lt.push_front(100);
    print(lt);
}

void test_3()
{
    // 默认构造
    List<int> lt1;
    lt1.push_back(1);
    lt1.push_back(2);
    lt1.push_back(3);
    lt1.push_back(4);
    lt1.push_back(5);
    print(lt1);

    // 拷贝构造
    List<int> lt2(lt1);
    print(lt2);
    lt2.push_back(6);
    lt2.push_back(7);
    lt2.push_back(8);
    lt2.push_back(9);
    lt2.push_back(10);
    print(lt2);

    // 赋值运算
    lt1 = lt2;
    print(lt1);
}

// 模板
struct Date
{
    int _year;
    int _month;
    int _day;

    Date(int year = 0, int month = 1, int day = 1)
        : _year(year), _month(month), _day(day)
    {}
};

void test_4()
{
    List<Date> lt;
    lt.push_back(Date());
    lt.push_back(Date(2022, 2, 22));
    lt.push_back(Date(2024, 9, 8));

    List<Date>::iterator it = lt.begin();
    while (it != lt.end())
    {
        // cout << *it << " ";
        // operator->   operator*
        cout << it->_year << "-" << it->_month << "-" << it->_day << endl; // 更喜欢这么去用
        cout << (*it)._year << "-" << (*it)._month << "-" << (*it)._day << endl;
        it++;
    }
    cout << endl;
}

int main()
{
    test_1();
    //test_2();
    //test_3();
    //test_4();

    return 0;
}

六、总结与优化

通过这篇文章，我们实现了一个功能完备的双向链表 List 容器。我们的 List 容器具备如下特点：

  1. 模板支持：允许存储任意类型的数据。
  2. 动态扩容：无需预定义容器大小，链表能够根据需求动态增长。
  3. 迭代器与反向迭代器：支持双向遍历，并与标准库中的 std::list 类似。
  4. 插入与删除：支持在任意位置插入和删除元素，适用于频繁的动态修改操作。
  5. 异常安全与迭代器兼容性：通过合理的内存管理，确保操作的健壮性。

本文通过逐步构建实现了一个强大的 List 容器，这一 List 实现适用于需要高效插入和删除操作的场景，并且能够与 STL 的标准容器互相借鉴。这篇文章通过详细的代码解释和逻辑推导，带领读者逐步实现了一个媲美 C++ 标准库 std::list 的双向链表。学习与实现这样的数据结构，能够帮助我们更加深入理解 C++ 容器的设计与实现思路，也为日后实现更多复杂的数据结构打下坚实的基础。



希望这篇博客对您有所帮助，也欢迎您在此基础上进行更多的探索和改进。如果您有任何问题或建议，欢迎在评论区留言，我们可以共同探讨和学习。更多知识分享可以访问我的个人博客网站 ： https://blog.lenyiin.com/ 。本博客所设计的代码也可以访问我的 git 仓库获取 ：https://git.lenyiin.com/Lenyiin/List

标签：node,head,const,iterator,List,C++,next,链表,prev
From： https://blog.csdn.net/mmlhbjk/article/details/142035714

相关文章

  • 如何实现标准库般强大的 C++ Vector？：从动态扩容到移动语义到迭代器全覆盖
    在C++中，std::vector是最常用的动态数组容器。它具有高效的内存管理、动态扩容、随机访问等特点。在这篇博客中，我们将从零开始，实现一个功能强大、灵活、并且具有高性能的Vector类，具备std::vector的大部分功能，包括动态扩容、迭代器、模板支持、随机访问等，尽可能模仿C+......
  • C++里面的iostream是什么东西？
    小弟不才，看了百度的介绍更乱了。。我刚接触c++，我感觉很有意思，今天看c++primer里面介绍过iostream。但是怎么看都不懂。代码里面也出现了#include<iostream>。我想请教一下，iostream是个库，可不可以理解成是一个仓库，里面装的都是C的代码？另外，IO是不是iostream的缩写？ C++编译系统提......
  • C++学习笔记（曾经我看不懂的代码2:基于范围的for循环、auto使用、stl容器、template模
    不知不觉c++程序设计：标准库已经看了一大半了，学到了很多，很多曾经在网上和在书上看到却看不懂的代码，在看完标准库中的大半内容以后，都能大致的理清代码的含义。代码模板一：for(auto&a:arr)1、基于范围的for循环：a为迭代变量，arr为迭代范围，&表示引用。写一个例子：#include<ios......
  • C++ iostream、iomanip 头文件详解
    C++iostream、iomanip头文件详解首先，我们来看看iostream。相信大家都知道iostream，这个库可以说是最常用的几个库之一了。iostream库提供了输入输出流。比如cin、cout，都是在iostream里的。所以，我们经常会用到iostream这个库。iostream这个名字很好理解，InputOutputStream，输......
  • C/C++中extern函数使用详解
    extern可以置于变量或者函数前,以标示变量或者函数的定义在别的文件中,提示编译器遇到此变量和函数时在其他模块中寻找其定义。此外extern也可用来进行链接指定目录一、定义和声明的区别二、extern用法2.1extern函数2.2extern变量2.3在C＋＋文件中调用C方式编译的函数三、通俗讲......
  • Android开发 - Map 键值对链表的使用解析
    创建和初始化MapHashMap：常用的实现类，基于哈希表Map<String,Integer>map=newHashMap<>();LinkedHashMap：保持插入顺序的实现类Map<String,Integer>map=newLinkedHashMap<>();TreeMap：基于红黑树，按键的自然顺序或提供的比较器排序Map<String,Integer>map=......
  • C++ 模板进阶知识——stdenable_if
    目录C++模板进阶知识——std::enable_if1.简介和背景基本语法使用场景2.`std::enable_if`的基本用法示例：限制函数模板只接受整数类型3.SFINAE和std::enable_if示例：使用SFINAE进行函数重载SFINAE的优点应用场景4.在类模板中使用std::enable_if示例：根据类型......
  • 南沙信奥赛C++陈老师解一本通题: 1326：【例7.5】 取余运算（mod）
    ​【题目描述】【输入】输入b，p，k的值。【输出】【输入样例】2109【输出样例】2^10mod9=7 #include<iostream>#include<stdlib.h>usingnamespacestd;longlongb,p,k,ans=1;intmain(){ cin>>b>>p>>k; for(inti=1;i<=p;i++) { ans*=b;......
  • [C++ Daily] 确保类复制了所有应该复制的成员
    确保类复制了所有应该复制的成员结果:源代码:#include<iostream>#include<string>#include<vector>/***copy操作应该包含对象内的所有成员变量及所有父类的成员变量,*此种可以通过调用对应的拷贝构造与拷贝赋值操作完成*////@briefsimpleterminalprint......
  • 南沙信奥赛C++陈老师解一本通题: 1171：大整数的因子
    ​ 【题目描述】已知正整数k满足2≤k≤9，现给出长度最大为30位的十进制非负整数c，求所有能整除c的k。【输入】一个非负整数c，c的位数≤30。【输出】若存在满足 c%k==0的k，从小到大输出所有这样的k，相邻两个数之间用单个空格隔开；若没有这样的k，则输出"none"。【输入样......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99