最新消息:想得多,做的少。一天到晚瞎鸡巴搞。

STL自问自答之list

大概数据结构与算法 阿虚 17浏览 0评论

.      使用list需要包含头文件<list>,实际list实现是存放在<stl_list.h>当中。

list有哪些操作

通过构造函数插入

list();
//申请n块内存,并初始化value
list(size_type n, const T& value);
list(int n, const T& value);
list(long n, const T& value);
//申请n块内存,并初始化为空
explicit list(size_type n);
//拷贝fisrt到last内容
list(const T* first, const T* last);
list(const_iterator first, const_iterator last);
list(const list<T, Alloc>& x);

插入函数

iterator insert(iterator position, const T& x);
iterator insert(iterator position);
inline void insert(iterator position, const T* first, const T* last);
inline void insert(iterator position, const_iterator first, const_iterator last);
inline void insert(iterator position, size_type n, const T& x);
inline void insert(iterator position, int n, const T& x);
inline void insert(iterator position, long n, const T& x);
void push_front(const T& x);
void push_back(const T& x);

移除函数

iterator erase(iterator position);
iterator erase(iterator first, iterator last); 
void clear(); 
void pop_front();
void pop_back();
void remove(const T& value);

其他list管理函数

void swap(list<T, Alloc>& x); 
void resize(size_type new_size, const T& x);
void resize(size_type new_size);
bool empty() const;
size_type size() const; 
size_type max_size() const;
 
void splice(iterator position, list& x);
void splice(iterator position, list&, iterator i);
void splice(iterator position, list&, iterator first, iterator last); 
void unique();
void merge(list& x); 
void reverse(); 
void sort();

list迭代器操作

//list所使用的内存存储节点
typedef __list_node<T> list_node;
typedef list_node* link_type;

//list所使用的的迭代器类型
typedef __list_iterator<T, T&, T*>             iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;

//迭代器操作
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
reference front();
const_reference front() const;
reference back();
const_reference back() const;

list的内存管理

.      list是由一个双向链表,每次插入新的节点时只需要从内存池中获取一块sizeof(T)大小的内存即可,并且双线链表把内存正确的串联起来即可。

vector和list的区别

.     vector插入时会判断是否还存在可用空间,存在则直接插入到buffer的尾部。否则从内存池获取一块更大的(当前所占用空间*2)的空间然后在走一遍【从内存管理中获取所需要大小的新的内存空间,将旧空间内容数据挪动到新空间上,将旧buffer内存空间交还给内存池管理。】

.     list插入真正是用多少吃多少,不会出现向vector那样如果当前不够但是还需要新的空间就直接切一块大于当前自身的2倍来占用。并且每次插入新节点的时候不会像vector那样挪动数据,所以插入效率更高,因为是双向链表只需要轻松的挪动一下next和prev指针所指向的位置即可。

.     对于高性能的STL来说如果vector的模板类型是基础类型,那么STL的“traits”萃取功能可以直接通过memmove之类的系统库来做,但是如果是的“类”类型那么只能通过循环遍历方式慢慢的一个一个将内的原有数据重新构造回来。list就没有这样做的需求了,因为是散乱在内存块中的管理也是由操作指针数据。动指针也快很多。

迭代器区别

.     和vector不同,vector的迭代器直接是T类型的指针T*,因为vector是一大块内存存储那么可以很轻松的通过[inedx]来移动获取数据。

.     list的迭代器时和list区分开来的。list的所有节点数据是存储在__list_node结构体当中。list的迭代器有个专门的迭代器类__list_iterator。这个类重载了各种运算符。

template <class T>
struct __list_node 
{
    typedef void* void_pointer;
    void_pointer next;
    void_pointer prev;
    T data;
};

template<class T, class Ref, class Ptr>
struct __list_iterator 
{
    typedef __list_iterator<T, T&, T*>             iterator;
    typedef __list_iterator<T, const T&, const T*> const_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 size_t size_type;
    typedef ptrdiff_t difference_type;

    link_type node;
    
    inline __list_iterator();
    inline __list_iterator(link_type x);    //←←←←在这里
    inline __list_iterator(const iterator& x);

    inline bool operator==(const self& x) const;
    inline bool operator!=(const self& x) const;
    inline reference operator*() const; 
    inline pointer operator->() const;
    inline self& operator++();
    inline self operator++(int);
    inline self& operator--();
    inline self operator--(int);
};

template <class T, class Alloc>
list<T, Alloc>::iterator list<T, Alloc>::begin() 
{ 
	return (link_type)((*node).next); 
}

.     以begin()来说,list里面节点存储是使用的__list_node,因为iterator是使用的__list_iterator,不过__list_iterator是支持__list_node的构造(上面标红)。因为__list_iterator是专门用来做迭代器的类,所以各种运算符的重载操作也是对__list_node节点做操作的。

转载请注明:虚无 » STL自问自答之list

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址