list 是一种双向链表。list 的设计更加复杂一点,好处是每次插入或删除一个元素,就配置或释放一个元素,list 对于空间的运用有绝对的精准,一点也不浪费。而且对于任何位置的元素插入或删除,list 永远是常数空间。注意:list 源码里其实分了两个部分,一个部分是 list 结构,另一部分是 list 节点的结构。也就是说指针变量和数据变量分开定义,目的是是为了给迭代器做铺垫,因为迭代器遍历的时候不需要数据成员的,只需要前后指针就可以遍历该 list。list 的节点结构如下图所示:
__list_node 用来实现节点,数据结构中就储存前后指针和属性。
template
// 前后指针
typedef void* void_pointer;
void_pointer next;
void_pointer prev;
// 属性
T data;
};
基本结构如下图所示:
基本类型
template
typedef __list_iterator
typedef __list_iterator
typedef __list_iterator
// 迭代器是bidirectional\_iterator\_tag类型
typedef bidirectional_iterator_tag iterator_category;
typedef T value_type;
typedef Ptr pointer;
typedef Ref reference;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
…
};
构造函数
template
…
// 定义节点指针
typedef __list_node
link_type node;
// 构造函数
__list_iterator(link_type x) : node(x) {}
__list_iterator() {}
__list_iterator(const iterator& x) : node(x.node) {}
…
};
重载
template
…
// 重载
bool operator==(const self& x) const { return node == x.node; }
bool operator!=(const self& x) const { return node != x.node; }
…
// ++和--是直接操作的指针指向next还是prev, 因为list是一个双向链表
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;
}
};
list 自己定义了嵌套类型满足 traits 编程, list 迭代器是 bidirectional_iterator_tag 类型,并不是一个普通指针。
list 在定义 node 节点时, 定义的不是一个指针:
template
class list {
protected:
typedef void* void_pointer;
typedef __list_node
typedef simple_alloc
public:
// 定义嵌套类型
typedef T value_type;
typedef value_type* pointer;
typedef const value_type* const_pointer;
typedef value_type& reference;
typedef const value_type& const_reference;
typedef list_node* link_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
protected:
// 定义一个节点, 这里节点并不是一个指针.
link_type node;
public:
// 定义迭代器
typedef __list_iterator
typedef __list_iterator
…
};
每个构造函数都会创造一个空的 node 节点,为了保证我们在执行任何操作都不会修改迭代器。list 默认使用 alloc 作为空间配置器,并根据这个另外定义了一个 list_node_allocator,目的是更加方便以节点大小来配置单元。
template
class list {
protected:
typedef void* void_pointer;
typedef __list_node
typedef simple_alloc
其中,list_node_allocator(n) 表示配置 n 个节点空间。以下四个函数,分别用来配置,释放,构造,销毁一个节点。
class list {
protected:
// 配置一个节点并返回
link_type get_node() { return list_node_allocator::allocate(); }
// 释放一个节点
void put_node(link_type p) { list_node_allocator::deallocate(p); }
// 产生(配置并构造)一个节点带有元素初始值
link_type create_node(const T& x) {
link_type p = get_node();
__STL_TRY {
construct(&p->data, x);
}
__STL_UNWIND(put_node(p));
return p;
}
//销毁(析构并释放)一个节点
void destroy_node(link_type p) {
destroy(&p->data);
put_node(p);
}
// 对节点初始化
void empty_initialize() {
node = get_node();
node->next = node;
node->prev = node;
}
};
template
class list {
…
public:
iterator begin() { return (link_type)((*node).next); } // 返回指向头的指针
const_iterator begin() const { return (link_type)((*node).next); }
iterator end() { return node; } // 返回最后一个元素的后一个的地址
const_iterator end() const { return node; }
// 这里是为旋转做准备, rbegin返回最后一个地址, rend返回第一个地址. 我们放在配接器里面分析
reverse\_iterator rbegin() { return reverse\_iterator(end()); }
const\_reverse\_iterator rbegin() const {
return const\_reverse\_iterator(end());
}
reverse\_iterator rend() { return reverse\_iterator(begin()); }
const\_reverse\_iterator rend() const {
return const\_reverse\_iterator(begin());
}
// 判断是否为空链表, 这是判断只有一个空node来表示链表为空.
bool empty() const { return node->next == node; }
// 因为这个链表, 地址并不连续, 所以要自己迭代计算链表的长度.
size\_type size() const {
size\_type result = 0;
distance(begin(), end(), result);
return result;
}
size\_type max\_size() const { return size\_type(-1); }
// 返回第一个元素的值
reference front() { return \*begin(); }
const\_reference front() const { return \*begin(); }
// 返回最后一个元素的值
reference back() { return \*(--end()); }
const\_reference back() const { return \*(--end()); }
// 交换
void swap(list<T, Alloc>& x) { \_\_STD::swap(node, x.node); }
...
};
template
inline void swap(list
x.swap(y);
}
因为 list 是一个循环的双链表, 所以 push 和 pop 就必须实现是在头插入,删除还是在尾插入和删除。在 list 中,push 操作都调用 insert 函数, pop 操作都调用 erase 函数。
template
class list {
…
// 直接在头部或尾部插入
void push_front(const T& x) { insert(begin(), x); }
void push_back(const T& x) { insert(end(), x); }
// 直接在头部或尾部删除
void pop_front() { erase(begin()); }
void pop_back() {
iterator tmp = end();
erase(--tmp);
}
…
};
上面的两个插入函数内部调用的 insert 函数。
class list {
…
public:
// 最基本的insert操作, 之插入一个元素
iterator insert(iterator position, const T& x) {
// 将元素插入指定位置的前一个地址
link_type tmp = create_node(x);
tmp->next = position.node;
tmp->prev = position.node->prev;
(link_type(position.node->prev))->next = tmp;
position.node->prev = tmp;
return tmp;
}
注意:
删除元素的操作大都是由 erase 函数来实现的,其他的所有函数都是直接或间接调用 erase。
list 是链表,所以链表怎么实现删除元素, list 就在怎么操作:很简单,先保留前驱和后继节点, 再调整指针位置即可。
由于它是双向环状链表,只要把边界条件处理好,那么在头部或者尾部插入元素操作几乎是一样的,同样的道理,在头部或者尾部删除元素也是一样的。
template
class list {
…
iterator erase(iterator first, iterator last);
void clear();
// 参数是一个迭代器 修改该元素的前后指针指向再单独释放节点就行了
iterator erase(iterator position) {
link_type next_node = link_type(position.node->next);
link_type prev_node = link_type(position.node->prev);
prev_node->next = next_node;
next_node->prev = prev_node;
destroy_node(position.node);
return iterator(next_node);
}
…
};
…
}
list 内部提供一种所谓的迁移操作(transfer):将某连续范围的元素迁移到某个特定位置之前,技术上实现其实不难,就是节点之间的指针移动,只要明白了这个函数的原理,后面的 splice,sort,merge 函数也就一一知晓了,我们来看一下 transfer 的源码:
template
class list {
…
protected:
void transfer(iterator position, iterator first, iterator last) {
if (position != last) {
(*(link_type((*last.node).prev))).next = position.node;
(*(link_type((*first.node).prev))).next = last.node;
(*(link_type((*position.node).prev))).next = first.node;
link_type tmp = link_type((*position.node).prev);
(*position.node).prev = (*last.node).prev;
(*last.node).prev = (*first.node).prev;
(*first.node).prev = tmp;
}
}
…
};
上面代码的七行分别对应下图的七个步骤:
splice函数: 将两个链表进行合并:内部就是调用的 transfer 函数。
merge 函数: 将传入的 list 链表 x 与原链表按从小到大合并到原链表中(前提是两个链表都是已经从小到大排序了). 这里 merge 的核心就是 transfer 函数。
reverse 函数: 实现将链表翻转的功能:主要是 list 的迭代器基本不会改变的特点, 将每一个元素一个个插入到 begin 之前。
sort 函数: list 这个容器居然还自己实现一个排序,看一眼源码就发现其实内部调用的 merge 函数,用了一个数组链表用来存储 2^i 个元素, 当上一个元素存储满了之后继续往下一个链表存储, 最后将所有的链表进行 merge归并(合并), 从而实现了链表的排序。
赋值操作: 需要考虑两个链表的实际大小不一样时的操作:如果原链表大 : 复制完后要删除掉原链表多余的元素;如果原链表小 : 复制完后要还要将x链表的剩余元素以插入的方式插入到原链表中。
resize 操作: 重新修改 list 的大小,传入一个 new_size,如果链表旧长度大于 new_size 的大小, 那就删除后面多余的节点。
clear 操作: 清除所有节点:遍历每一个节点,销毁(析构并释放)一个节点。
remove 操作: 清除指定值的元素:遍历每一个节点,找到就移除。
unique 操作: 清除数值相同的连续元素,注意只有“连续而相同的元素”,才会被移除剩一个:遍历每一个节点,如果在此区间段有相同的元素就移除之。
list 是一种双向链表。每个结点都包含一个数据域、一个前驱指针 prev 和一个后驱指针 next。
由于其链表特性,实现同样的操作,相对于 STL 中的通用算法, list 的成员函数通常有更高的效率,内部仅需做一些指针的操作,因此尽可能选择 list 成员函数。
优点
缺点
手机扫一扫
移动阅读更方便
你可能感兴趣的文章