std::forward_list

时间:2023-03-08 15:38:39
std::forward_list

forward_list相比list来说空间利用率更好,与list一样不支持随机访问,若要访问除头尾节点的其他节点则时间复杂度为线性。

在forward_list成员函数里只能访问头节点以及向头节点插入与删除(front/push_front/emplace_front/pop_front)这些操作的时间复杂度都是常数

当然你也可以插入/删除forward_list任何一个节点,这必须牺牲一定的时间(insert_after/emplace_after/erase_after).这些操作首先取得指向

头位置的迭代器,再遍历到你所需要插入位置的前一个element,这个过程的时间复杂度是线性。erase_after若是单个参数则删除所指向element

的后一个element,返回被删除element的后一个迭代器,若是range则是一个开区间,返回range.last。