您的位置: 首页  >  文章  >  6.C++ STL之list

6.C++ STL之list

分类: 文章 • 2024-05-01 10:33:23

源代码

G2.9 sizeof(list)=4 link_node * 一个指针在32位系统是4字节
G4.9 sizeof(list)=8

template<class T,class Alloc=alloc>
class list{
	protected:
		typedef _list_node<T> list_node;
	public:
		typedef list_node* link_type;
		typedef _list_iterator<T,T&,T*> iterator;//模拟指针
	protected:
		link_type node;
		......
};

template <class T>
struct _list_node{
	typedef void* void_pointer;
	void_pointer prev;//指向void 这种指针，需要正确的转型
	void_pointer next;
	T data;
};

template<class T,class Ptr>
struct _list_iterator{
	typedef T value_type;
	typedef Ptr pointer;
	typedef Ref reference;
};
//需要自动进入查看next和pre指针,当++就智能的查看next

6.C++ STL之list
灰色的结点是为了实现前闭后开区间

迭代器

6.C++ STL之list

//G2.9
template<class T,class Ptr>
struct _list_iterator{
	typedef _list_iterator<T,Ref,Ptr> self;
	typedef bidirectional _iterator_tag iterator_category;
	typedef T value_type;
	typedef Ptr pointer;
	typedef Ref reference;
	typedef _list_node<T>* link_type;
	typedef ptrdiff_t difference_type;

	link_type node;
	
	reference operator*() const{ return (*node).date; }
	pointer operator->() const { return &(operator*()); }
	self& operator++(){ 
		node=(link_type)((*node).next);    
		return *this; 
		}
	//前++没有参数
	self operator++(int){ 
		self tmp=*this; //1.记录原值
		++*this; //2.进行操作 
		return tmp;//3.返回原值
	 }
	//后++有参数，但是参数没有意义
	...
};

self tmp=*this; //1.记录原值
  • 此处*this以为会唤起operator*，但是编译器更早遇到=之前将调用assign，用以self tmp的拷贝构造，并且以*this为初值
  • assign调用这个函数_list_iterator(const iterator &x):node(x.node){}
  • 因此*this会更早的解释为参数const iterator &x，所以不会调用operator*()
	++*this; //2.进行操作
  • 此处的++用到前++，即self& operator++()
    self operator++(int)//避免做两次后++
    self& operator++()
  • 操作符向整数看齐，例如
int i(6);
++++i; //即++(++i);
i++++;//不等于(i++)++;不允许

reference operator*() const
{ return (*node).date; }
pointer operator->() const
 { return &(operator*()); }

以下是关于 &(operator*())的解释

//对于&(operator*())
//实例
list<Foo>::iterator ite;
...
*ite;//获得a Foo object
ite->method();
//调用Foo::method()
//相当于 (*ite).method();
//相当于(&(*ite))->method();
ite->field=7;
//赋值 Foo object's field
//only if field is public
//相当于(*ite).field=7;
//相当于(&(*ite))->field=7;
  • iterator是一个类指针，但它并不是真正的指针，它指向的数据被包在里面。需要用*iterator得到数控，然后再&取得数据的真正指针

一个例子：

void destroy(T* pointer);
destroy(&*first);
  • first是通常赋予迭代器的名称，它重载operator*返回对容器的指向元素的引用，然后operator&用于获取迭代器指向的变量的地址。
  • 但是，如果first是指针而不是用户定义的迭代器，则可以直接使用first。请注意，指针可以是迭代器（特别是RandomAccessIterators）。
  • 如果参数已经是一个原始指针，那么&*组合什么都不做。但是，如果参数是具有重载一元运算*符的类类型，则&*不再是无操作。
  • &*模式的经典用法是将“通用”指针转换为原始指针。例如，如果it是与向量元素关联的迭代器，那么&*it将为您提供指向该向量元素的普通原始指针。
typedef _list_iterator<T,Ref,Ptr> self;//G2.9
  • G2.9此处有三个参数类型，应该传入一个参数即可
//G4.9
template<typename _Tp,typename _Alloc=std::allocator<_Tp>>
class list:protected _List_base<_Tp,_Alloc>
{
	public:typedef _List_iterator<_Tp> iterator;
};
//根据_Tp来做引用和指针
template<typename _Tp>
struct _List_iterator
{
	typedef _Tp* pointer;//(3)
	typedef _Tp& reference;//(4)
};

struct _List_node_base{
	_List_node_base* M_next;
	_List_node_base* M_prev;
};
//继承上者
template<typename _Tp>
struct _List_node : public _List_node_base
{
 	_Tp  _M_data;
};
/*
//G2.9
//比如Ref,Ptr,T，都是由外头传进的参数决定类型
template<class T,class Ref,class Ptr>
struct _List_iterator
{
	typedef Ptr pointer;//(3)
	typedef Ref reference;//(4)
};

template<calss T>
struct _list_node{
	typedef void* void_pointer;
	void_pointer prev;
	void_pointer nect;
	T data;
};
*/
  • G4.9 相较于G2.9
  • 模板参数只有一个（易理解）
  • node的结构有其parent
  • node的成员的type较精确
  • 指针不是void类型，而是自己本身的类型，这是一个比较好的设计，链表应该指向自己。

6.C++ STL之list
6.C++ STL之list

  • list<_Tp,A>继承了_List_base<_TP,_A>
  • _List_base<_TP,_A>内含了一个_List_impl<_Tp,_A>【implementation】
  • _List_impl<_Tp,_A>继承了_A<List_node<_Tp>> 【allocator，无意义】
  • _List_impl<_Tp,_A>内含了_List_node_base<_Tp>

G4.9这样的设计相当复杂，而G2.9只有一个class，十分简单

sizeof(list) sizeof(list)
G2.9 G4.9
4 8
一个_list_node指针，不用继续追溯指针的类型内有两个指针，因为一个指针在32位系统内只占4字节 继承父类_List_base,父类的大小取决于数据类型_List_impl,而_List_imple数据类型为_List_node_base,它有两个数据（指针），直到在_List_node_base才是指针，前者都是非指针，因此要追溯到指针，才能知道所占内存大小

相关推荐