小数据的链表-解网

问：

对于一个应用程序，我需要一个数据结构

用于保持小结构体（3 ints）
只需要向前遍历
填充一次（初始化时已知的大小和值）和
需要允许删除元素

删除节点后不必立即释放节点。我认为使用 a 会导致更多的开销，因为它如何分配内存。由于删除，使用向量可能也不理想。list

我想，最有用的结构可能是连续内存上的链表。可以通过重写节点的正向/后退指针来删除节点，但只有当整个列表被销毁时，内存才会被释放。或者，我想到了一个向量，它配备了另一个向量，其中包含下一个/上一个未删除元素的索引，但我猜这基本上是一样的。

这听起来不像是以前没有人使用过的东西。它有名字吗？是否有通用的实现，例如在 STL 或 boost 中？

C++ 列表容器

你真的需要一个链表吗？您可以只使用简单的 std：：vector，如果它是“alive”或“deleted”，则使用布尔标志而不是下一个指针。或者直接使用 std：：vector。如果你不删除很多，或者你大部分时间都是从末尾删除的，那就用std：：vector吧

0赞 Alan Birtles 8/30/2023

是的，对于大多数应用程序来说，简单性会带来更好的性能。做了很多你想要的东西，但只有在从头到尾而不是中间删除时才能真正提供更好的性能std::vectorstd::deque

答：

2赞 Homer512 8/30/2023 #1

除非您必须保留指向元素的指针，否则使用 .前向迭代和一次填充显然是可以实现的，它们将比使用链表快得多。std::vector

对于删除，您应该使用擦除-删除成语。假设您处理条目，并选择在循环期间删除它们。然后这样写：

#include <algorithm>
#include <vector>

struct Foo {
  int a, b, c;
};

void process(std::vector<Foo>& entries) {
    entries.erase(std::remove_if(entries.begin(), entries.end(),
          [](Foo& entry) -> bool {
              do_something(entry);
              bool remove_this = check_remove(entry);
              return remove_this;
          }), entries.end());
}

此例程将“压缩”向量。对于简单的结构或任何可以廉价移动的结构，以及处理不太可能导致异常的情况，这是非常快速和有效的。

当然，在某些情况下，这种模式不能很好地工作，例如“删除满足条件 X 的第一个条目”，但您必须在算法要求、访问模式等方面更加具体。

0赞 Misha T 8/30/2023 #2

它是来自纯 C 的标准双链表，存在无限数量的实现。

无论你喜欢C++语义还是标准语义，你都可以使用boost：：intrusive：：list

小数据的链表

Linked list for small data

评论

评论