1

For an application, I need a data structure that

  • is used to keep small structs (3 ints)
  • needs to be traversed in forward direction only
  • is filled once (size and values known on initialization) and
  • needs to allow deleting elements

It is not necessary that the nodes' is freed immediately upon deletion. I would assume that using a list causes more overhead, due to how it allocates memory. Using vectors is probably also not ideal, because of the deletions.

I thought, the most useful structure could be a linked list on a contiguous piece of memory. Nodes can be deleted by rewriting the nodes' forward/backward pointers, but memory is only freed when the entire list is destroyed. Alternatively, I thought about a vector, equipped with another vector that contains the indices of the next/previous non-deleted element, but that's basically the same I guess.

This doesn't sound like something no-one had used before. Does it have a name? Is there a common implementation, for instance in STL or boost?

Bubaya
  • 615
  • 3
  • 13
  • 2
    You're overthinking this. Use a `std::vector`. – Botje Aug 30 '23 at 09:08
  • Do you really need a linked list for that? You can just use a simple std::vector and instead of a next pointer use a bool flag if it is "alive" or "deleted". Or simply use std::vector. If you don't delete a lot or you delete from the end most of the time, just go with std::vector – simre Aug 30 '23 at 09:09
  • yep, for most applications the simplicity of `std::vector` leads to better performance. `std::deque` does a lot of what you want but only really gives better performance when removing from the beginning and end, not the middle – Alan Birtles Aug 30 '23 at 09:11

2 Answers2

2

Unless you have to keep pointers to elements, you will fare better with std::vector. Forward-iteration and fill-once are obviously fulfilled and they will be much faster than using a linked list.

For deletion, you should use the erase-remove idiom. Let's say you process entries and optionally remove them during the loop. Then write it like this:

#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());
}

This routine will "compact" the vector. For simple structs or any structure that can be moved cheaply, and where the processing is unlikely to cause an exception, this is very fast and efficient.

Of course there are instances in which this pattern does not work well, such as "remove first entry that fulfils condition X" but then you have to be more specific in your algorithmic requirements, access patterns etc.

Homer512
  • 9,144
  • 2
  • 8
  • 25
0

It's standard double linked list from pure C, there exists an infinite number of implementations.

Whether you prefer C++ semantics and something standard you could use boost::intrusive::list

Misha T
  • 56
  • 5
  • I don't see in the docs that boost::intrusive::lists does not allocate each node individually. – Bubaya Aug 30 '23 at 13:10
  • @Bubaya, intrusive containers don't allocate or deallocate it's members by definition. In case of `boost::intrusive::list` you could emplace in container any `boost::intrusive::list_base_hook<>`. Examples of usage here https://theboostcpplibraries.com/boost.intrusive#ex.intrusive_01 – Misha T Aug 30 '23 at 13:20