C++中list的用法是什么，要注意哪些？

这篇文章给大家分享的是C++中list的用法，下文将介绍list的使用及使用要注意的问题，下文示例有一定的参考价值，有需要的朋友可以参考了解，那么接下来一起跟随小编看看吧。

list相较于vector来说会显得复杂，它的好处是在任意位置插入,删除都是一个O(1)的时间复杂度。

一、list的节点

template class T>

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

}
    ;
    

这个是在stl3.0版本下的list的节点的定义，节点里面有一个前指针，一个后指针，有一个数据data。这里只能知道他是一个双向链表，我们可以再稍微看一下list关于它的构造函数。

class list  -->
 list() {
     empty_initialize();
 

  void empty_initialize() {
     
    node = get_node();
    
    node->
    next = node;
    
    node->
    prev = node;

  }

再看一下它的list(),可以看出他调用的empty_initialize（），是创建了一个头结点，并且是一个循环的结构。

综上：list的总体结构是一个带头循环双向链表

二、list的迭代器

迭代器通常是怎么使用的，看一下下面这段代码。

int main()
{
    
	listint>
     l;
    
	l.push_back(1);
    
	l.push_back(2);
    
	l.push_back(3);
    
	l.push_back(4);
    
	l.push_back(5);
    
	l.push_back(6);
    

	listint>
    ::iterator it = l.begin();

	while (it != l.end())
	{
    
		cout  *it  " ";
    
		it++;

	}
    
	cout  endl;
    
	return 0;

}
    

我们从list int > 当中定义一个iterator对象，然后让他去访问我们的节点

并且他所支持的操作有++，解引用，当然还有 --等等

stl3.0当中的迭代器实现：

templateclass T, class Ref, class Ptr>

struct __list_iterator {
    
  typedef __list_iteratorT, T&
    , T*>
                 iterator;
    
  typedef __list_iteratorT, const T&
    , const T*>
     const_iterator;
    
  typedef __list_iteratorT, Ref, Ptr>
               self;
    

  typedef bidirectional_iterator_tag iterator_category;
    
  typedef T value_type;
    
  typedef Ptr pointer;
    
  typedef Ref reference;
    
  typedef __list_nodeT>
    * link_type;
    
  typedef size_t size_type;
    
  typedef ptrdiff_t difference_type;
    

  link_type node;


  __list_iterator(link_type x) : node(x) {
}

  __list_iterator() {
}
    
  __list_iterator(const iterator&
 x) : node(x.node) {
}
    

  bool operator==(const self&
 x) const {
     return node == x.node;
 }
    
  bool operator!=(const self&
 x) const {
     return node != x.node;
 }

  reference operator*() const {
     return (*node).data;
 }
    

#ifndef __SGI_STL_NO_ARROW_OPERATOR
  pointer operator->
() const {
     return &
    (operator*());
 }
    
#endif /* __SGI_STL_NO_ARROW_OPERATOR */

  self&
 operator++() {
     
    node = (link_type)((*node).next);
    
    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;

  }
    

大家感兴趣可以先看看上面的，我们先用一个简述版的来带大家简要实现一下

	templateclass T>

	class __list_node
	{
    
	public:
		__list_node(const T&
 val = T())//用一个全缺省比较好
			:_next(nullptr)
			,_pre(nullptr)
			,node(val)
		{
}
    
	public:
		__list_nodeT>
    * _next;
    
		__list_nodeT>
    * _pre;
    
		T node;

	}
    ;
    

	templateclass T>

	class __list_itertaor//这里是迭代器
	{
    
	public:
		typedef __list_nodeT>
      Node;

		__list_itertaor(Node* node)
		{
    
			_node = node;

		}
    

		bool operator!=(const __list_itertaorT>
    &
 it)
		{
    
			return _node != it._node;

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

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

		}
    
	private:
		Node* _node;

	}
    ;
    

这里的实现是不完整的，但是很适合说明问题。通过我们去重载opertaor++，和重载opertaor*，可以让我们像指针一样去访问一个节点，让我们可以跟vector和string一样用同样的接口就能实现对数据的访问，这是非常厉害的一个技术。

注意点：

我们通过对节点的操作，重载了operator++等接口实现了对一个节点的访问，访问的时候实际上也就是创建迭代器对象，对我们的数据进行访问，所以我们封装的时候是将节点的指针进行封装。

list相比vector，正因为他们的底层结构不相同，list的迭代器在插入操作和接合操作（splice）都不会造成迭代器失效，只有删除的时候，只有那个被删除元素的迭代器失效，而不影响后面的，而vector就统统失效了。

2.1、模板参数为什么是三个

2.2 const 迭代器

有这样一种情况，我们需要const对象去遍历，假如我们有个函数叫做print_list（const list int > & lt）;

传参： 其中传参中const是因为不会对对象进行修改，加引用是因为不用深拷贝，提高效率。

功能： 这个函数就是去打印链表里面的内容的。但是按照我们上面的实现，会出现什么问题呢。

这很正常，在const迭代器就去生成const迭代器对象，在vector，string这些迭代器就是原生指针的时候我们只需要typedef const T* const_iterator,那如果我们在我们生成的list也做类似的操作，来看看结果。

结果我们发现，好像没多大问题，但是我们尝试修改const迭代器里面的内容时，却发现能修改成功。const迭代器怎么能修改里面的数据呢？这就有问题了！！！说明我们的有一个巨大的隐患在里面。

2.3 修改方法

最简单的方法当然就是再写多一个迭代器，把__list_iterator换成__list_const_iterator 之类的，但是我们认真观察的话，实际上这两个类很多东西是重复的，只有在operator*，operator-> 时所需要的返回值，我们需要找到一种方法去让const对象的返回值也是const对象，答案就是添加多两个个模板参数。

以下以添加一个模板参数为例，实现一个Ref operator*()；

templateclass T>

	class __list_node
	{
    
	public:
		__list_node(const T&
 val = T())//用一个全缺省比较好
			:_next(nullptr)
			,_pre(nullptr)
			,node(val)
		{
}
    
	public:
		__list_nodeT>
    * _next;
    
		__list_nodeT>
    * _pre;
    
		T node;

	}
    ;
    

	templateclass T,class Ref>

	class __list_itertaor
	{
    
	public:
		typedef __list_nodeT>
      Node;

		__list_itertaor(Node* node)
		{
    
			_node = node;

		}
    

		bool operator!=(const __list_itertaorT,Ref>
    &
 it)
		{
    
			return _node != it._node;

		}
    
		__list_itertaorT,Ref>
    &
 operator++()
		{
    
			_node = _node->
    _next;
    
			return *this;

		}

		Ref operator*()//返回Ref，返回值就有区别啦
		{
    
			return _node->
    node;

		}
    
	private:
		Node* _node;

	}
    ;
    

	templateclass T>

	class list
	{
    
		typedef __list_nodeT>
      Node;
    
	public:
		typedef __list_itertaorT,T&
    >
     iterator;
    
		typedef __list_itertaorT, const T&
    >
     const_iterator;
//修改
		iterator begin()
		{
    
			return iterator(_node->
    _next);

		}

		iterator end()
		{
    
			return iterator(_node);

		}

		const_iterator begin()const
		{
    
			return const_iterator(_node->
    _next);

		}

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

		}

		list()
		{
    
			_node = new Node;
    
			_node->
    _next = _node;
    
			_node->
    _pre = _node;

		}
    
		void push_back(const T&
 val)
		{
    
			Node* newnode = new Node(val);
    
			Node* tail = _node->
    _pre;
    
			tail->
    _next = newnode;
    
			newnode->
    _pre = tail;
    
			newnode->
    _next = _node;
    
			_node->
    _pre = newnode;

		}
    
	private:
		Node* _node;

	}
    ;
    

一图了解：也就是我们的测试端test函数中定义list int > ::const_iterator cit= l.begin(); 的时候迭代器对象就会识别到定义的const迭代器，它的第二个模板参数放的就是const T& ，这样子我们operator*（）返回的时候只需要返回第二个模板参数就可以了。

同理，我们要用到的接口operator-> 当中也会有const对象和普通对象调用的情况。

二、美中不足

list上面说的仿佛都是优点

任意位置的O(1)时间的插入删除，迭代器失效的问题变少了。但他又有哪些不足呢

• 不支持随机访问
• 排序的效率慢，库中的sort用的是归并排序–> 快排需要三数取中，对于链表来说实现出来效率也低，所以当链表的元素需要进行排序的时候，我们通常也都会拷贝到vector当中，再用vector当中的排序。
• 同理链表的逆置效率也不高！

三、迭代器的分类

迭代器从功能角度来看的话分为：const迭代器/普通迭代器 + 正反向。

从容器底层结构角度分为：单向，双向，随机。

• 单向： 单链表迭代器（forward_list）/哈希表迭代器；这些只支持单向++；
• 双向： 双链表迭代器/map迭代器；这些支持的++/- -操作；
• 随机迭代器： string/vector/deque；这些是支持++/- -/+/-操作的，类似原生指针一般。

我们来看一下部分函数的，比如sort当中的模板参数写成RandomAccessIterator，就是想要明示使用者他这里需要的是一个随机的迭代器，在它的底层会调用到迭代器的+操作，所以这个时候如果你传的是一个双向或者单向的迭代器就不行了！！

//sort的函数声明
template class RandomAccessIterator>
    
  void sort (RandomAccessIterator first, RandomAccessIterator last);
    
custom (2)	
template class RandomAccessIterator, class Compare>
    
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);
    

比如说reverse函数声明，它的模板参数是BidirectionalIterator，也就是需要一个支持双向的迭代器，这个时候其实我们就可以传随机迭代器和双向迭代器，从上面的迭代器支持的操作可以看到，随机迭代器是支持双向迭代器的所有操作的。

同理，如果是一个需要单向迭代器的地方，我们就可以传一个双向，随机，单向迭代器了！！

std::reverse
template class BidirectionalIterator>
    
  void reverse (BidirectionalIterator first, BidirectionalIterator last);

从stl3.0当中的stl_iterator.h，我们可以看出当中的继承关系。这个我们之后再讲。

注意：difference_type为两个迭代器之间的距离。类型ptrdiff_t为无符号整形。

3.x std::find的一个报错

当我们实现了自己的数据结构，如list，我们如果用库里的std：find查找我们实现的数据结构当中的数据会报错。博主的测试版本为vs2013，在其他版本可能不做检查，不会报错。

void test_list()
	{
    

		listint>
     l;
    
		l.push_back(5);
    
		listint>
    ::iterator it = std::find(l.begin(), l.end(), 5);

	}
    

报错：这里的报错说的是iterator_category不在我们的迭代器当中，这个是对我们迭代器类型的一个检查。

stl_list.h当中为迭代器添加了如下声明来解决这个问题。

解决方案： 我们可以用stl3.0版本下stl_list.h当中的迭代器的声明。也可以用release版本下，都是可以跑过的。

		typedef bidirectional_iterator_tag iterator_category;
    
		typedef T value_type;
    
		typedef Ptr pointer;
    
		typedef Ref reference;
    
		typedef ptrdiff_t difference_type;
    

总结

以上就是关于C++中list的用法的介绍，上述示例具有一定的参考价值，有需要的朋友可以了解看看，希望对大家学习C++中list的用法有帮助，想要了解更多可以继续浏览网络其他相关的文章。

文本转载自PHP中文网

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！