6.C++ STL之list
源代码
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
灰色的结点是为了实现前闭后开区间
迭代器
//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类型,而是自己本身的类型,这是一个比较好的设计,链表应该指向自己。
- 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才是指针,前者都是非指针,因此要追溯到指针,才能知道所占内存大小 |