特定容器算法

与其他容器不同,链表类型list与forward_list定义了几个成员函数形式的算法,如下表所示。特别是,它们定义了独有的sort、merge、remove、reverse和unique。通用版本的sort要求随机访问迭代器,因此不能用于list和forward_list,因为这两个类型分别提供双向迭代器和前向迭代器。

链表类型定义的其他算法的通用版本可以用于链表,但代价太高。这些算法需要交换输入序列中的元素。一个链表可以通过改变元素间的链接而不是真正的交换它们的值来传递“交换”元素。因此,这些链表版本的算法的性能比对应的通用版本好很多。

注意:对于list和forward_list应该优先使用成员函数版本的算法而不是通用算法。

list和forward_list成员函数版本的算法

这些操作都返回void

lst.merge(lst2)         将来自lst2的元素合并入lst。lst和lst2都必须是有序的。

lst.merge(lst2,comp)       元素将从lst2中删除。在合并之后,lst2变为空。第一个版本使用<运算符;第二个版本使用给定的比较操作

lst.remove(val)         调用erase删除掉与给定值相等(==)或令一元谓词为真的每个元素

lst.remove_if(pred)

lst.reverse()         反转lst中元素的顺序

lst.sort()           使用<或给定比较操作排序元素

lst.sort(comp)    

lst.unique()           调用erase删除同一值的连续拷贝。第一个版本使用==;第二个版本使用给定的二元谓词

lst.unique(pred)

splice成员

链表类型还定义了splice算法。其描述见下表。此算法是链表数据结构所特有的,因此不需要通用版本。

list和forward_list的splice成员函数的参数

lst.splice(args)或flst.splice_after(args)

(p,lst2)        p是一个指向lst中元素的迭代器,或一个指向flst首前位置的迭代器。函数将lst2的所有元素移动到lst中p之前的位置或是flst中p之后的位置。将元素           从lst2中删除。lst2的类型必须与lst或flst相同,且不能是同一个链表

(p,lst2,p2)        p2是一个指向lst2中位置的有效的迭代器。将p2指向的元素移动到lst中,或将p2之后的元素移动到flst中。lst2可以是与lst或flst相同的链表

(p,lst2,b,e)      b和e必须表示lst2中的合法范围。将给定范围中的元素从lst2移动到lst或flst。lst2与lst(或flst)可以是相同的链表,但p不能指向给定范围中元素

链表特有的操作会改变容器

多数链表特有的算法都与其通用版本很相似,但不完全相同。链表特有版本与通用版本间的一个至关重要的区别是链表版本会改变底层的容器。例如,remove的链表版本会删除指定的元素。unique的链表版本会删除第二个和后继的重复元素。

类似的,merge和splice会销毁其参数。例如,通用版本的remove将合并的序列写给一个给定的目的迭代器:两个输入序列是不变的。而链表版本的merge函数会销毁给定的链表——元素从参数指定的链表中删除,被合并到调用merge的链表对象中。在merge之后,来自两个链表中的元素仍然存在,但它们都已在同一个链表中。

原文地址:https://www.cnblogs.com/wuchanming/p/3918418.html