fbl::
提供了两个主要的容器系列,即“顺序容器”
和关联容器
有序容器是一种容器,其中的元素的枚举顺序为
根据用户向特定来源添加元素或从中移除元素的方式
容器。fbl::
定义了两种类型的有序容器。
SinglyLinkedList
是一个仅支持正向的有序容器 迭代。DoublyLinkedList
是一个有序容器,支持双向 迭代。
有序容器和关联容器之间的主要区别 决定着向容器添加元素和从容器中移除元素的方式。 本指南的这一部分将向您介绍如何在 以及从有序容器中移除
请参阅设置 build 依赖项 要使用各种容器类型,必须添加该文件
向有序容器添加元素
SinglyLinkedList
提供了两种向容器添加元素的方法。
它们是:
DoublyLinkedList
也支持这些方法,但还添加了以下内容
方法。
与往常一样,如果
该容器类型使用的节点状态已经是容器的成员。
使用托管指针类型时,用户可以为容器提供自己的
通过值提供指针实例来引用对象,或者可以
使用 std::move
将其引用转移至容器。
将元素推送到按顺序排列的容器中
推送方法的行为符合预期,会添加新元素并将其设为新元素 序列中的前部或后部元素(即,第一个或 枚举顺序中的最后一个元素)。例如:
struct Tag1 {};
struct Tag2 {};
class Obj : public fbl::RefCounted<Obj>,
public fbl::ContainableBaseClasses<
fbl::TaggedDoublyLinkedListable<fbl::RefPtr<Obj>, Tag1>,
fbl::TaggedDoublyLinkedListable<fbl::RefPtr<Obj>, Tag2>
> {
public:
explicit Obj(int val) : val_(val) {}
int val() const { return val_; }
private:
const int val_;
};
TaggedDoublyLinkedList<fbl::RefPtr<Obj>, Tag1> stack_like;
TaggedDoublyLinkedList<fbl::RefPtr<Obj>, Tag2> queue_like;
for (int i = 0; i < 5; ++i) {
fbl::RefPtr<Obj> obj_ref = fbl::AdoptRef(new Obj(i));
stack_like.push_front(obj_ref); // Copy our reference
queue_like.push_back(std::move(obj_ref)); // Transfer our reference
}
// Prints "4 3 2 1 0 "
for (const auto& obj : stack_like) { printf("%d ", obj.val()); }
printf("\n");
// Prints "0 1 2 3 4 "
for (const auto& obj : queue_like) { printf("%d ", obj.val()); }
printf("\n");
将元素插入按顺序排列的容器中
insert
和 insert_after
均在
排名紧随其前 (insert
) 或紧随其后
(insert_after
) 迭代器。begin()
或 end()
都可以作为
insert
的迭代器,其功能等同于仅指定
push_front
或 push_back
。使用insert_after
不引用元素的迭代器,因此 insert_after
只会
当容器为非空时接受容器的 begin()
,并且永远不会
接受 end()
。继续上一个示例:
queue_like.insert(queue_like.begin(), fbl::MakeRefCounted<Obj>(100));
queue_like.insert(queue_like.end(), fbl::MakeRefCounted<Obj>(500));
for (auto iter = queue_like.begin(), iter != queue_like.end(); ++iter) {
if (iter->val() == 2) {
queue_like.insert(iter, fbl::MakeRefCounted<Obj>(200));
queue_like.insert_after(iter, fbl::MakeRefCounted<Obj>(300));
break;
}
}
// Prints "100 0 1 200 2 300 3 4 500 "
for (const auto& obj : queue_like) { printf("%d ", obj.val()); }
printf("\n");
使用 splice
合并有序容器
最后,splice
将获取所提供列表的内容,并将其拼接成
另一个列表中迭代器前面的位置。完成后,
源列表将为空,因为已将它的所有元素
目标列表。源列表和目标列表必须是不同的列表
但必须是相同类型的列表(例如,两者必须使用相同的
节点存储)。begin()
和 end()
都是目标位置中的有效目标
。前者会将源元素附加到目标元素,
而后者会附加相应代码上一个示例即将完成:
TaggedDoublyLinkedList<fbl::RefPtr<Obj>, Tag2> tmp;
tmp.push_front(fbl::MakeRefCounted<Obj>(-1));
tmp.push_front(fbl::MakeRefCounted<Obj>(-2));
queue_like.splice(queue_like.begin(), tmp);
tmp.push_back(fbl::MakeRefCounted<Obj>(1000));
tmp.push_back(fbl::MakeRefCounted<Obj>(2000));
queue_like.splice(queue_like.end(), tmp);
tmp.push_back(fbl::MakeRefCounted<Obj>(50));
tmp.push_back(fbl::MakeRefCounted<Obj>(60));
for (auto iter = queue_like.begin(), iter != queue_like.end(); ++iter) {
if (iter->val() == 300) {
queue_like.splice(iter, tmp);
break;
}
}
// Prints "-2 -1 100 0 1 200 2 50 60 300 3 4 500 1000 2000 "
for (const auto& obj : queue_like) { printf("%d ", obj.val()); }
printf("\n");
从有序容器中移除元素
SinglyLinkedList
提供了三种从容器中移除元素的方法。
它们是:
pop_front()
erase_next(Iter)
clear()
DoublyLinkedList
也支持这些方法,但还添加了以下内容
方法。
pop_back(Ptr)
erase(Iter or Obj&)
除了 clear()
之外,所有这些方法都会返回
将容器的指针类型返回给用户,同时返回用户对
对象(当使用托管指针时)指向用户。在活动中
指定位置没有元素,则返回 nullptr
。在具体使用 erase_next
的情况下,传递无效的
迭代器。迭代器必须至少引用容器中的某个元素。
最后,擦除操作适用于元素的迭代器,
是列表的成员,或者对对象本身具有 T&
样式引用。
并非必须使用迭代器发现对象,才能直接
已清除。
继续前面部分所加星标的示例:
// Remove the object with val "-2" and hold a reference to it in |removed|.
auto removed = queue_like.pop_front();
// Remove the object with val "2000" and drop the reference, allowing the object
// to destruct.
queue_like.pop_back();
// Begin refers to the "-1" element, so erase_next will remove the "100" element
queue_like.erase_next(queue_like.begin());
// remove all of the elements in the list that are not in ascending order,
// relative to the previous element. Hold a reference to element 200 as we pass
// it.
fbl::RefPtr<Obj> e200;
for (auto iter = queue_like.begin(); iter.IsValid(); ) {
auto tmp = iter++;
if (iter->IsValid() && (tmp->val() > iter->val())) {
queue_like.erase(iter);
iter = tmp;
} else if (tmp->val() == 200) {
e200 = tmp.CopyPointer();
}
}
// List is now "-1 0 1 200 300 500 1000". Remove 200 from the list using the
// object reference we held instead of an iterator.
queue_like.erase(*e200);
// Finally, just clear the list.
queue_like.clear();