forward_list 概述

forward_list 是 C++ 11 新增的容器，它的实现为单链表。

在新昌等地区，都构建了全面的区域性战略布局，加强发展的系统性、市场前瞻性、产品创新能力，以专注、极致的服务理念，为客户提供网站设计制作、网站建设 网站设计制作按需求定制开发,公司网站建设,企业网站建设,品牌网站建设,网络营销推广,成都外贸网站建设公司,新昌网站建设费用合理。

forward_list 是支持从容器中的任何位置快速插入和移除元素的容器，不支持快速随机访问。forward_list 和 list 的主要区别在于，前者的迭代器属于单向的 Forward Iterator，后者的迭代器属于双向的 Bidirectional Iterator。

下面实现的单链表为单向带头循环链表，实现为循环链表只是因为这样实现比较简单，更容易处理 end 的指向。

文章完整代码：ForwardList · 秦1230/STL study

接口总览

namespace qgw {/// @brief forward_list 中每个节点
	/// @tparam T 节点存储的数据类型
	templatestruct _forward_list_node {_forward_list_node(const T& data = T());	// 节点类的构造函数
			
		_forward_list_node* _next;				// 指向后一节点
		T _data;									// 存储节点数据
	};

	/// @brief forward_list 的迭代器
	/// @tparam T forward_list 数据的类型
	/// @tparam Ref 数据的引用类型
	/// @tparam Ptr 数据的指针类型
	templatestruct _forward_list_iterator {typedef _forward_list_iteratoriterator;
		typedef _forward_list_iteratorself;

		typedef Ptr pointer;
		typedef Ref reference;
		typedef _forward_list_nodeforward_list_node;

		// 构造函数
		_forward_list_iterator(forward_list_node* node = nullptr);

		// 各种运算符重载
		bool operator==(const self& x) const;
		bool operator!=(const self& x) const;
		reference operator*() const;
		pointer operator->() const;
		self& operator++();
		self operator++(int);

		forward_list_node* _node;	// 指向对应的 forward_list 节点
	};

	templateclass forward_list {public:
		typedef T* pointer;
		typedef const T* const_pointer;
		typedef T& reference;
		typedef const T& const_reference;
		typedef _forward_list_nodeforward_list_node;
		typedef _forward_list_iterator iterator;
		typedef _forward_list_iteratorconst_iterator;

	public:
		// 默认成员函数
		forward_list();
		forward_list(const forward_list& other);
		forward_list& operator=(const forward_list& other);
		~forward_list();

		// 元素访问
		reference front();
		const_reference front() const;

		// 迭代器
		iterator begin();
		const_iterator begin() const;
		iterator end();
		const_iterator end() const;

		// 容量
		bool empty() const;

		// 修改器
		void clear();
		iterator insert_after(iterator pos, const_reference val);
		void push_front(const_reference val);
		iterator erase_after(iterator pos);
		void pop_front();
		void swap(forward_list& other);

	private:
		forward_list_node* _node;
	};
}

forward_list 的节点

forward_list 节点的设计与 list 的节点类似，只需两个成员变量：一个节点指针和数据。

构造函数将数据初始化为给定数据，再将 _next 指针初始化为空。

/// @brief 节点类的构造函数
/// @param data 用来构造节点的初值
_forward_list_node(const T& data = T())
    : _data(data) {_next = nullptr;
    }

默认成员函数 默认构造函数

因为实现的是的单向带头循环链表，所以要在构造函数创建一个头节点，并将 _next 指针指向自己。

/// @brief 构造一个空链表
forward_list() {_node = new forward_list_node;	// 创建一个头节点
    _node->_next = _node;			// 后面指向自己
}

析构函数

forward_list 的析构函数，先调用 clear 释放数据资源，再 delete 掉头节点即可。

/// @brief 释放资源
~forward_list () {clear();
    delete _node;
    _node = nullptr;
}

forward_list 的迭代器

forward_list 的节点在内存中不是连续存储的，因此不能使用原生指针作为 forward_list 的迭代器。

由于 forward_list 是一个单向链表，迭代器必须具备后移的能力，所以 forward_list 提供的是 Forward Iterator。

构造函数

forward_list 的迭代器中成员变量只有一个节点指针，将其初始化为给定的节点指针。

/// @brief 迭代器的构造函数
/// @param node 用来构造的节点
_forward_list_iterator(forward_list_node* node = nullptr) {_node = node;
}

operator==

两个 forward_list 迭代器的比较，实际上比较的是迭代器所指向的节点，指向同一节点即为两迭代器相同。

/// @brief 判断两迭代器指向的节点是否相同
/// @param x 用来比较的迭代器
/// @return 相同返回 true，不同返回 false
bool operator==(const self& x) const {return _node == x._node;
}

operator!=

operator!= 的实现可以借助 operator==，直接调用判断是否相等的函数，然后返回相反的结果。

/// @brief 判断两迭代器指向的节点是否不同
/// @param x 用来比较的迭代器
/// @return 不同返回 true，相同返回 false
bool operator!=(const self& x) const {return !operator==(x);
}

operator*

当我们对一个指针进行解引用时会发生什么，我们会得到指针指向的数据。同理，我们对迭代器进行解引用，得到的是迭代器中节点指针所指向变量的值。

/// @brief 获取指向节点中的数据值
/// @return 返回指向节点数据的引用
reference operator*() const {return (*_node)._data;
}

operator->

假如我们有如下数据类：

// 有一个 Person 类，里面有身高和体重两个成员
struct Person {double height;
	double weight;
};

此时，我们的数据不再是单一的变量了，而是一个结构体变量。我们想读取其中的数据，该怎么操作呢？

Person p1 = {165, 105 };
Person* p = &p1;
cout<< (*p).height<< endl;	// 获取身高数据
cout<< p->weight<< endl;		// 获取体重数据

我们可以先对直接解引用得到一个 Person 对象，再用 . 操作符访问其中的变量。

当然我们也可以选择对 Person* 使用 ->操作符访问结构体内的变量。

于是乎，operator->的功能也就很清晰了。当我们对迭代器使用 ->时我们可以直接访问节点中的变量。也就是说，我们有一迭代器 iter，其中迭代器中存储的数据类型为 Person，当我们使用iter->height时，可以直接获取到身高。

/// @brief 获取节点中数据的地址
/// @return 返回节点指向的数据的地址
pointer operator->() const {return &(operator*());
}

看了实现你可能会疑惑iter->获得的明明是结构体的指针，后面应该再跟一个 ->箭头才对。是的没错，确实应该是这样，不过iter->->height的可读性比较差，所以编译器会在编译时自动为我们添加一个箭头。

operator++

operator++ 运算符的作用是让迭代器指向 forward_list 中下一节点。因为 forward_list 是单链表不能向前移动，所以不用实现 operator--。

前置实现的思路是：通过迭代器中的节点指针找到下一节点，然后赋值给迭代器中的节点指针。

后置实现的思路是：先拷贝一份当前位置的迭代器，然后调用前置 ++，最后返回临时变量。

需要注意的是：前置 ++ 返回的是前进后迭代器的引用，后置 ++ 返回的是一个临时变量。

/// @brief 前置 ++
/// @return 返回前进一步后的迭代器
self& operator++() {_node = _node->_next;
    return *this;
}

/// @brief 后置 ++
/// @param  无作用，只是为了与前置 ++ 进行区分，形成重载
/// @return 返回当前的迭代器
self operator++(int) {self tmp = *this;
    ++(*this);
    return tmp;
}

元素访问 front

front 获取容器首元素的引用，调用 begin 得到首元素的迭代器，再解引用即可。

因为 forward_list 的迭代器只能单向移动，故不能快速获得链表中最后一个节点。

/// @brief 返回容器首元素的引用
/// @return 首元素的引用
reference front() {return *begin();
}

// 与上面唯一不同就是用于 const 容器
const_reference front() const {return *begin();
}

迭代器

begin

begin 获取的是首元素的迭代器，根据上图，直接返回头节点的下一位置即可。

/// @brief 返回指向 forward_list 首元素的迭代器
/// @return 指向首元素的迭代器
iterator begin() {// 根据节点指针构造迭代器
    return iterator(_node->_next);
}

// const 版本供 const 容器使用
const_iterator begin() const {return const_iterator(_node->_next);
}

end

end 获取的是最后一个元素下一个位置的迭代器，根据上图就是 _node 所指向的节点。

/// @brief 返回指向 forward_list 末元素后一元素的迭代器
/// @return 指向最后元素下一位置的迭代器
iterator end() {// 调用 iterator 构造函数
    return iterator(_node);
}

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

容量 empty

begin 和 end 指向相同，说明链表此时只有一个头节点，链表为空。

/// @brief 检查容器是否无元素
/// @return 若容器为空则为 true，否则为 false
bool empty() const {return begin() == end();
}

修改器 insert_after

根据 STL 的习惯，插入操作会将新元素插入于指定位置之前，而非之后。然而 forward_list 是一个单向链表，它没有任何方便的方法可以定位出前一个位置，它必须从头找。因此，forward_list 中提供的插入操作，是插入在指定位置之后。

下图为：只有 0、1 两个元素的单链表，在 0 之后插入元素值为 2 的节点的示意图。

插入的过程非常简单：

1. 创建一个要插入的节点
2. 插入节点的 _next 指向 pos 后一位置的节点
3. pos 的 _next 指向要插入的节点

/// @brief 在容器中的指定位置后插入元素
/// @param pos 内容将插入到其后的迭代器
/// @param val 要插入的元素值
/// @return 指向被插入元素的迭代器
iterator insert_after(iterator pos, const_reference val) {forward_list_node* tmp = new forward_list_node(val);	// 创建要插入的节点
    tmp->_next = pos._node->_next;							// (1)
    pos._node->_next = tmp;									// (2)
    return tmp;
}

push_front

push_front 的作用是在容器起始处插入元素。

直接调用 insert_after 插入就行，需要注意的是，insert_after 是在给定位置之后插入，所以应传入头节点对应的迭代器位置。

/// @brief 头插给定元素 val 到容器起始
/// @param val 要头插的元素值
void push_front(const_reference val) {// end() 返回头节点位置的迭代器，在这之后插入是头插
	insert_after(end(), val);
}

erase_after

下图为：有三个元素 0、1、2 的链表，删除 pos 指向节点之后节点（值为 1）的示意图。

删除的过程非常简单：

1. 记录 pos 的下一节点 nextNode
2. 将 pos 的 _next 指向 nextNode 的下一个节点
3. delete 释放掉 nextNode 所指向的节点

/// @brief 从容器移除 pos 后面一个元素
/// @param pos 指向要被移除元素前一个元素的迭代器
/// @return 最后移除元素之后的迭代器
iterator erase_after(iterator pos) {forward_list_node* nextNode = pos._node->_next;		// 记录 pos 指向节点的下一节点
    pos._node->_next = nextNode->_next;					// (1)
    delete (nextNode);
    return (iterator)(pos._node->_next);
}

pop_front

pop_front 移除容器的首元素，也就是 end 指向的下一节点。

/// @brief 移除容器首元素
void pop_front() {erase_after(end());
}

clear

clear 用于清空容器所有数据，不清理头节点。

要注意 erase_after 删除给定位置下一个节点，end 的下一个是第一个元素，这样以次删除直到容器为空，即只剩一个头节点。

/// @brief 从容器擦除所有元素
void clear() {while (!empty()) {erase_after(end());
    }
}

swap

swap 用来交换两个 forward_list容器，不用交换 forward_list 中每个元素的值，直接交换 _node 指针即可。

/// @brief 将内容与 other 的交换
/// @param other 要与之交换内容的容器
void swap(forward_list& other) {std::swap(_node, other._node);
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

标题名称：STLforward-创新互联
分享链接：http://kswjz.com/article/jdsps.html