资讯

精准传达 • 有效沟通

从品牌网站建设到网络营销策划，从策略到执行的一站式服务

网站建设 >

查看其它板块

STLlist模拟实现-创新互联

list 概述

相比于 vector 的连续线性空间，list 采用的是零散的空间，它的好处是每次插入或删除一个元素，就配置或释放一个元素空间。

创新互联专注为客户提供全方位的互联网综合服务，包含不限于网站设计制作、做网站、铁西网络推广、成都小程序开发、铁西网络营销、铁西企业策划、铁西品牌公关、搜索引擎seo、人物专访、企业宣传片、企业代运营等，从售前售中售后，我们都将竭诚为您服务，您的肯定，是我们大的嘉奖；创新互联为所有大学生创业者提供铁西建站搭建服务，24小时服务热线：18980820575，官方网址：www.cdcxhl.com

list 是支持常数时间从容器任何位置插入和移除元素容器，但不支持快速随机访问。list 通常实现为双向链表，与 forward_list 相比，list 的迭代器可以向前移动，但也因此需要在节点中多开辟一个指针变量，在空间上效率稍低。

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

接口总览
namespace qgw {/// @brief list 中每个节点
	/// @tparam T 节点存储的数据的类型
	templatestruct _list_node {_list_node(const T& data = val());	// 节点类的构造函数

		_list_node* _prev;				// 指向前一节点
		_list_node* _next;				// 指向后一节点
		T _data;							// 存储节点数据
	};

	/// @brief list 的迭代器
	/// @tparam T list 数据的类型
	/// @tparam Ref 数据的引用类型
	/// @tparam Ptr 数据的指针类型
	templatestruct _list_iterator {typedef _list_iteratoriterator;
		typedef _list_iteratorself;

		typedef Ptr		pointer;
		typedef Ref		reference;
		typedef _list_nodelist_node;
		
        // 构造函数
        _list_iterator(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);
		self& operator--();
		self operator++(int);

		list_node* _node;	// 指向对应的 list 节点
	};

	templateclass list {public:
		typedef T* pointer;
        typedef const T* const_pointer;
		typedef T& reference;
		typedef const T& const_reference;
		typedef _list_nodelist_node;
		typedef _list_iterator iterator;
		typedef _list_iteratorconst_iterator;

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

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

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

		// 容量
		bool empty() const;
		size_t size() const;

		// 修改器
		void clear();
		iterator insert(iterator pos, const_reference val);
		void push_front(const_reference val);
		void push_back(const_reference val);
		iterator erase(iterator pos);
		void pop_front();
		void pop_back();
		void swap(list& other);

		// 操作
		void splice(iterator pos, list& other);
		void splice(iterator pos, list& other, iterator it);
        void splice(iterator pos, list& other, iterator first, iterator last);
		void merge(list& other);
		void remove(const_reference value);
		void reverse();
		void unique();

	private:
		list_node* _node;	// 指向链表头节点
	};
}
list 的节点

list 的节点我们设计成一个 _list_node 类，里面有三个成员变量，分别为前后指针和数据。

它的构造函数将数据初始化为给定数据，再将前后指针初始化为空即可。

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

list node

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

SGI list 不仅是一个双向链表，还是一个带头的循环链表。

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

empty lilt

析构函数

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

/// @brief 释放资源
~list() {clear();
    delete _node;
    _node = nullptr;
}
拷贝构造函数

用另一容器创建新对象。

先申请一个头节点，然后遍历 other 容器，将 other 中的数据逐一尾插到 *this 中。

/// @brief 用给定容器初始化
/// @param other 用来初始化的容器
list(const list& other) {_node = new list_node; 
    _node->_next = _node;
    _node->_prev = _node;
    for (const auto& e : other) {push_back(e); 
    }
}
复制赋值函数

先创建给定容器的拷贝 tmp，然后交换 *this 和 tmp，最后返回 *this。

/// @brief 替换容器内容
/// @param other 用作数据源的另一容器
/// @return *this
list& operator=(const list& other) {// tmp 出了作用域就销毁了
    listtmp(other);
    swap(tmp);
    // 返回引用可以连续赋值
    return *this;
}
list 的迭代器

list 的节点在内存中不是连续存储的，因此不能使用原生指针作为 list 的迭代器。list 的迭代器必须有能力指向 list 的节点，并能够正确的递增、递减、取值、成员存取等操作。正确的操作是指：递增时指向下一节点，递减时指向上一节点，取值时取的是节点的数据值，成员取用的是节点的成员。

由于 STL list 是一个双向链表（double linked-list），迭代器必须具备前移、后移的能力，所以 list 提供的是 Bidirectional Iterators。

list iterator

构造函数

list 的迭代器中成员变量只有一个节点指针，将其指向给定节点即可。

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

判断两迭代器指向的节点是否为同一个，直接比较迭代器中节点的指针即可。切记不能比较指针中的值，因为不同节点的值可能相同。

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

!= 的比较方法和 == 一样。

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

迭代器是模仿指针的，让我们可以像使用指针一样。因此可以对迭代器进行解引用操作，该操作得到的是迭代器中节点指针指向的数据，并且返回引用，因为有可能修改该数据。

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

->运算符的重载稍显复杂，让我们先看下面这个场景。

也就是 list 中存储的是自定义类型，自定义类型中又有多个成员变量，我们想取出指定的成员变量，当然这里用 . 也可以做到。

// 有一个学生类，里面有姓名和学号两个成员
struct Stu {string name;
    string id;
};

lists;
Stu s1 = {"qgw", "001" };
Stu s2 = {"wlr", "002" };
s.push_back(s1);
s.push_back(s2);
list::iterator ptr = s.begin();
// 输出第一个学生的姓名和学号
cout<< (*ptr).name<< endl;
cout<< s.begin()->id<< endl;
/// @brief 获取节点中数据的地址
/// @return 返回节点指向的数据的地址
pointer operator->() const {return &(operator*());
}

看到这你可能会疑惑，operator->返回的是节点的数据的地址，也是说上面s.begin()->得到的是一个地址，那这条语句是怎么执行的？

实际上这里确实应该有两个箭头像这样s.begin()->->id，但这种方式的可读性太差了，所以编译器对此做了优化，在编译为我们添加一个箭头。

operator++

operator++ 运算符的作用十分清晰，就是让迭代器指向链表中下一节点。

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

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

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

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

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

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

后置实现的思路是：先保存当前位置迭代器，然后调用前置 --，最后返回临时变量。

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

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

front 获取第一个元素的引用，直接用 begin 获取指向第一个元素的迭代器，再解引用即可。

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

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

end 获取最后一个元素的引用，先用 end 获取最后一个元素下一位置的迭代器，再回退一步，然后解引用就可以了。

/// @brief 返回容器中最后一个元素的引用
/// @return 最后元素的引用
reference back() {return *(--end());
}

const_reference back() const {return *(--end());
}
迭代器

在 begin 和 end 实现之前，我们先来看下 list 的示意图，下图为有 3 个元素的链表：

circular linked list

begin

begin 获取的是首元素的迭代器，根据上图，begin 的实现也就非常清晰了，直接返回头节点的下一位置即可。

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

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

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

/// @brief 返回指向 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();
}
size

size 函数的作用是返回容器中元素的数量。

在 C++ 11 前，该函数的复杂度可能是常数的，也可能是线性的。从 C++ 11 起该函数的复杂度为常数。

下面代码的时间复杂度是线性的，要想改成常数也很简单，只需要在 list 中开辟一个成员变量记录个数即可。

/// @brief 返回容器中的元素数
/// @return 容器中的元素数量
size_t size() const {size_t sz = 0;
    auto it = begin();
    while (it != end()) {++it;
        ++sz;
    }
    return sz;
}
修改器 insert

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

插入的思路比较清晰：

  1. 插入节点的 _next 指向 pos 位置的节点
  2. 插入节点的 _prev 指向 pos 前一位置的节点
  3. pos 前一位置的节点的 _next 指向插入的节点
  4. pos 位置节点的 _prev 指向插入的节点
/// @brief 插入元素到容器中的指定位置
/// @param pos 	将内容插入到 pos 之前
/// @param val 要插入的元素值
/// @return 指向被插入 val 的迭代器
iterator insert(iterator pos, const_reference val) {list_node* tmp = new list_node(val);	// 创建要插入的节点
    tmp->_next = pos._node;					// (1)
    tmp->_prev = pos._node->_prev;			// (2)
    (pos._node->_prev)->_next = tmp;		// (3)
    pos._node->_prev = tmp;					// (4)
    return tmp;
}
push_front

push_front 的作用是在第一个元素之前插入一个节点，直接调用 insert 在 begin 之前插入就行。

/// @brief 添加给定元素 val 到容器起始
/// @param val 要添加的元素值
void push_front(const_reference val) {insert(begin(), val);
}
push_back

push_back 的作用是在容器的最后添加一个节点，直接调用 insert 在 end 之前插入就行。

/// @brief 添加给定元素 val 到容器尾
/// @param val 要添加的元素值
void push_back(const_reference val) {insert(end(), val);
}
erase

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

list erase

删除的思路也很清晰：

  1. 将 pos 前一节点的 _next 指针指向 pos 的下一节点
  2. 将 pos 下一节点的 _prev 指针指向 pos 的前一节点
  3. delete 释放掉 pos 所指向的节点
/// @brief 从容器擦除指定的元素
/// @param pos 指向要移除的元素的迭代器
/// @return 最后移除元素之后的迭代器
iterator erase(iterator pos) {list_node* nextNode = pos._node->_next;		// 记录 pos 指向节点的下一节点
    list_node* prevNode = pos._node->_prev;		// 记录 pos 指向节点的前一节点
    prevNode->_next = nextNode;					// (1)
    nextNode->_prev = prevNode;					// (2)
    delete (pos._node);
    return (iterator)nextNode;
}
pop_front

pop_front 移除容器第一个元素，也就是 begin 指向的节点。

/// @brief 移除容器首元素
void pop_front() {erase(begin());
}
pop_back

pop_back 移除容器最后一个节点，也就是 end 指向的前一个节点。

/// @brief 移除容器的末元素
void pop_back() {erase(--end());
}
clear

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

采用遍历的方式调用 erase 删除每一个节点。

/// @brief 从容器擦除所有元素
void clear() {iterator it = begin();
    while (it != end()) {it = erase(it);
    }
}
swap

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

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

在实现该函数之前，先来看下 list 内部的一个函数 transfer。

list 内部提供一个迁移操作（transfer）：将某连续范围的元素迁移都某个特定位置之前。

这个函数比上面所写的要复杂的多，要对着图仔细思考。

/// @brief 将 [first, last) 范围的所有元素移动到 pos 之前
/// @param pos 将内容移动到 pos 之前
/// @param first 范围起始位置
/// @param last 范围结束位置
void transfer(iterator pos, iterator first, iterator last) {if (pos != last) {last._node->_prev->_next = pos._node;		// (1)
        first._node->_prev->_next = last._node;		// (2)
        pos._node->_prev->_next = first._node;		// (3)
        list_node* tmp = pos._node->_prev;			// (4)
        pos._node->_prev = last._node->_prev;		// (5)
        last._node->_prev = first._node->_prev;		// (6)
        first._node->_prev = tmp;					// (7)
    }
}

transfer

有了上面的函数，splice 的实现也就非常简单了，下面共有三个重载实现：

根据要转移的元素选择调用不同的函数。

/// @brief 将 other 接合于 pos 所指位置之前，两者不能是同一 list
/// @param pos 将内容插入到它之前
/// @param other 要从它转移内容的另一容器
void splice(iterator pos, list& other) {if (!other.empty()) {transfer(pos, other.begin(), other.end());
    }
}

/// @brief 将 it 所指元素接合到 pos 所指位置之前
/// @param pos 	将内容插入到它之前
/// @param other 要从它转移内容的另一容器
/// @param it 从 other 转移到 *this 的元素
void splice(iterator pos, list& other, iterator it) {// 取得一个 [i, j) 的范围，使得能调用 transfer
    iterator j = it;
    ++j;
    // 检查是否有必要执行
    // pos == it 时说明 pos 和 it 指向的是同一节点
    // pos == j 时说明，it 刚好在 pos 之前
    if (pos == it || pos == j) {return;
    }
    transfer(pos, it, j);
}

/// @brief 将 [first, last) 内的所有元素接合于 pos 所指位置之前
/// @param pos 将内容插入到它之前
/// @param first 起始位置
/// @param last 结束位置
void splice(iterator pos, list& other, iterator first, iterator last) {if (first != last) {transfer(pos, first, last);
    }
}
merge

merge 函数和归并排序中的合并操作类似，该函数的作用是：合并两个已递增排序的链表。

/// @brief 合并两个递增链表，合并到 *this 上
/// @param other 要合并的另一容器
void merge(list& other) {iterator first1 = begin();
    iterator end1 = end();
    iterator first2 = other.begin();
    iterator end2 = other.end();

    while (first1 != end1 && first2 != end2) {if (*first2< *first1) {iterator next = first2;
            transfer(first1, first2, ++next);
            first2 = next;
        } else {++first1;
        }
    }
    if (first2 != end2) {// 将 other 链表剩余元素合并到 *this 中
        transfer(first1, first2, end2);
    }
}
remove

remove 用来删除 list 中值等于 val 的元素，直接遍历链表，找到就删除。

/// @brief 移除等于 val 元素
/// @param val 要移除的元素的值
void remove(const T& val) {iterator first = begin();
    iterator last = end();
    while (first != last) {iterator next = first;
        ++next;
        if (*first == val) {erase(first);
        }
        first = next;
    }
}
reverse

reverse 的作用是逆转容器中的元素顺序。

该函数的思路简单，从第 2 个元素开始，以次头插到链表头部。

/// @brief 将 *this 的内容逆置
void reverse() {// 空链表或只有一个元素直接返回
    if (_node->_next == _node || _node->_next->_next == _node) {return;
    }

    iterator first = begin();
    ++first;
    while (first != end()) {iterator old = first;			// 第一次循环时指向第 2 个元素
        ++first;						// 第一次循环时指向第 3 个元素
        transfer(begin(), old, first);
    }
}
unique

unique 用来移除数值相同的连续元素，只保留一个。

该函数利用的是双指针的思想，first 和 next 分别指向前后两个元素，相同就删除后一个。

/// @brief 移除数值相同的连续元素
void unique() {iterator first = begin();
    iterator last = end();
    if (first == last) {return;
    }

    iterator next = first;
    while (++next != last) {// 此时 next 指向 first 下一个节点
        if (*first == *next) {// 连续的相同，就删除后一个
            erase(next);
        } else {// 不相同 first 向 end 移动
            first = next;
        }
        // 使 next 再次指向 first
        // 这样再进 while 时，++next 又使 next 指向 first 下一个
        next = first;
    }
}

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


本文名称：STLlist模拟实现-创新互联
本文链接：http://www.cdkjz.cn/article/dejdsc.html
返回首页 了解更多建站资讯

相关资讯

多年建站经验

多一份参考，总有益处

联系快上网，免费获得专属《策划方案》及报价

咨询相关问题或预约面谈，可以通过以下方式与我们联系

大客户专线   成都：13518219792   座机：028-86922220

在线咨询 提交需求
友情链接 交换友情链接
广安网站建设兴发搬家成都做网站西部信息中心简阳威斯达宇绵阳电信机房达州做网站网络整合营销官网SEO排名恒温恒湿空调机组

成都网站建设公司地址：成都市青羊区太升南路288号锦天国际A座10层 建设咨询028-86922220

成都快上网科技有限公司-四川网站建设设计公司 | 蜀ICP备19037934号 Copyright 2020,ALL Rights Reserved cdkjz.cn | 成都网站建设 | © Copyright 2020版权所有.

专家团队为您提供成都网站建设,成都网站设计,成都品牌网站设计,成都营销型网站制作等服务,成都建网站就找快上网！ | 成都网站建设哪家好？ | 网站建设地图