Custom allocators as alternatives to vector of smart pointers?

Question

This question is about owning pointers, consuming pointers, smart pointers, vectors, and allocators.

I am a little bit lost on my thoughts about code architecture. Furthermore, if this question has already an answer somewhere, 1. sorry, but I haven't found a satisfying answer so far and 2. please point me to it.

My problem is the following:

I have several "things" stored in a vector and several "consumers" of those "things". So, my first try was like follows:

std::vector<thing> i_am_the_owner_of_things;
thing* get_thing_for_consumer() {
    // some thing-selection logic
    return &i_am_the_owner_of_things[5]; // 5 is just an example
}

...

// somewhere else in the code:
class consumer {
    consumer() {
       m_thing = get_thing_for_consumer();
    }

    thing* m_thing;
};

In my application, this would be safe because the "things" outlive the "consumers" in any case. However, more "things" can be added during runtime and that can become a problem because if the std::vector<thing> i_am_the_owner_of_things; gets reallocated, all the thing* m_thing pointers become invalid.

A fix to this scenario would be to store unique pointers to "things" instead of "things" directly, i.e. like follows:

std::vector<std::unique_ptr<thing>> i_am_the_owner_of_things;
thing* get_thing_for_consumer() {
    // some thing-selection logic
    return i_am_the_owner_of_things[5].get(); // 5 is just an example
}

...

// somewhere else in the code:
class consumer {
    consumer() {
       m_thing = get_thing_for_consumer();
    }

    thing* m_thing;
};

The downside here is that memory coherency between "things" is lost. Can this memory coherency be re-established by using custom allocators somehow? I am thinking of something like an allocator which would always allocate memory for, e.g., 10 elements at a time and whenever required, adds more 10-elements-sized chunks of memory.

Example:
initially:
v = ☐☐☐☐☐☐☐☐☐☐
more elements:
v = ☐☐☐☐☐☐☐☐☐☐ 🡒 ☐☐☐☐☐☐☐☐☐☐
and again:
v = ☐☐☐☐☐☐☐☐☐☐ 🡒 ☐☐☐☐☐☐☐☐☐☐ 🡒 ☐☐☐☐☐☐☐☐☐☐

Using such an allocator, I wouldn't even have to use std::unique_ptrs of "things" because at std::vector's reallocation time, the memory addresses of the already existing elements would not change.

As alternative, I can only think of referencing the "thing" in "consumer" via a std::shared_ptr<thing> m_thing, as opposed to the current thing* m_thing but that seems like the worst approach to me, because a "thing" shall not own a "consumer" and with shared pointers I would create shared ownership.

So, is the allocator-approach a good one? And if so, how can it be done? Do I have to implement the allocator by myself or is there an existing one?

Medawar

Do multiple consumer use the same thing? Because if not, wouldn't it be more appropriate to move the ownership from the vector to the consumer? – Heteropolar

do you know maximum number of things ahead? If yes the call reserve on a vector and there will not be a reallocation of elements. – Dorman

Yes, multiple consumers can use the same thing. That's the point, the ownership shall not be moved to the consumer. – Medawar

I doubt it is possible to give you a decent feedback without having a clues what is the thing and how it behaves. – Dorman

@MarekR Yes, that would maybe be an option. But it can never be a clean solution because on one hand, you want this upper bound to be as tight as possible. And what if you, in some rare situation, need more? – Medawar

@MarekR The "thing" lives longer than the "consumer" and there can be an arbitrary number of "things". And regardless of how often the owning vector is reallocated, the m_thing pointers must remain valid. – Medawar

How big thing is? Does it accept callbacks? Or is does it behave like a structural type? Do multiple consumers communicate using thing (do consumer changes thing)? Does it contain other pointers? – Dorman

@MarekR You can assume the worst for thing: Multiple consumers can change it, and it can even cointain other pointers. – Medawar

Can you go for a different approach as for example: do_something_on_thing(functor, consumer)? This would call the function of a consumer directly on the thing in the vector instead of assigning a thing to a consumer. – Heteropolar

If multiple consumers need to access the same thing, the prudent approach is to use a vector of some kind of pointers. Allocate each thing independently, and pass the pointer to the consumers. The pointers may be plain pointers or, better, std::shared_ptr<>s, because you effectively have shared ownership: You must not delete a thing as long as one of its consumers is still alive. – Utricle

@MikevanDyke That's an interesting point, but consumer needs to keep the pointer to thing in order to check at some later point in time whether it needs to update itself based on the changes that happened to thing. (I wanted to leave out these information because the question should be on point and not cluttered with unneccessary detail.) – Medawar

Are things only added or removed to the ends of the owner and never added or removed from the middle? If so you can use std::deque. – Chkalov

@j00hi, would you say that your goal is similar to the service locator pattern? – Watercolor

"The downside here is that memory coherency between "things" is lost." - why is it important? – Watercolor

@IgorG Memory coherency is (or can be) important when there are hundreds of things and an update shall be performed on all of these hundreds of things. Having them in the same cache line(s) can lead to significantly increased performance. – Medawar

Answer 1

If you are able to treat thing as a value type, do so. It simplifies things, you don't need a smart pointer for circumventing the pointer/reference invalidation issue. The latter can be tackled differently:

• If new thing instances are inserted via push_front and push_back during the program, use std::deque instead of std::vector. Then, no pointers or references to elements in this container are invalidated (iterators are invalidated, though - thanks to @odyss-jii for pointing that out). If you fear that you heavily rely on the performance benefit of the completely contiguous memory layout of std::vector: create a benchmark and profile.
• If new thing instances are inserted in the middle of the container during the program, consider using std::list. No pointers/iterators/references are invalidated when inserting or removing container elements. Iteration over a std::list is much slower than a std::vector, but make sure this is an actual issue in your scenario before worrying too much about that.

Bybidder

These are some good points to consider, thanks! How is memory managed in a std::deque? Isn't it also some kind of linked list or does it store memory contiguously? – Medawar

It stores memory in contiguous chunks. That makes it kind of a hybrid between std::list and std::vector. Have a look at this thread for more info on std::deque. – Bybidder

@Medawar Its both, it uses a sort of linked lists of blocks type of layout. The downside is that on most implementations the blocksize is really small and none-growing - the small size can usually be alleviated to some extent by a macro define - but again should be as a result of profiling and not speculation. – Ostrich

That behavior of std::deque is actually exactly what I was looking for when I was asking about custom allocators in my question. I'll leave the question open for just a bit longer, hoping that someone can point me to some more information about custom allocators for this case, because I've asked for these in my question title. Otherwise, thanks a lot. The information in this answer and its comments is very concise and helpful. – Medawar

@Medawar you might also want check out "circular buffer" (not in std) - depending on needs. – Ostrich

Nitpick, but is it not so that iterators are in fact invalidated on std::deque::push_back and std::deque::push_front, but not references to the actual elements? Worth mentioning, so that someone does not store an iterator expecting it to remain valid after insertion at the back. – Touchback

@Touchback You're right, thanks for the excellent hint. I'll correct the answer. – Bybidder

Answer 2

There is no single right answer to this question, since it depends a lot on the exact access patterns and desired performance characteristics.

Having said that, here is my recommendation:

Continue storing the data contiguously as you are, but do not store aliasing pointers to that data. Instead, consider a safer alternative (this is a proven method) where you fetch the pointer based on an ID right before using it -- as a side-note, in a multi-threaded application you can lock attempts to resize the underlying store whilst such a weak reference lives.

So your consumer will store an ID, and will fetch a pointer to the data from the "store" on demand. This also gives you control over all "fetches", so that you can track them, implement safety measure, etc.

void consumer::foo() {
    thing *t = m_thing_store.get(m_thing_id);
    if (t) {
        // do something with t
    }
}

Or more advanced alternative to help with synchronization in multi-threaded scenario:

void consumer::foo() {
    reference<thing> t = m_thing_store.get(m_thing_id);
    if (!t.empty()) {
        // do something with t
    }
}

Where reference would be some thread-safe RAII "weak pointer".

There are multiple ways of implementing this. You can either use an open-addressing hash table and use the ID as a key; this will give you roughly O(1) access time if you balance it properly.

Another alternative (best-case O(1), worst-case O(N)) is to use a "reference" structure, with a 32-bit ID and a 32-bit index (so same size as 64-bit pointer) -- the index serves as a sort-of cache. When you fetch, you first try the index, if the element in the index has the expected ID you are done. Otherwise, you get a "cache miss" and you do a linear scan of the store to find the element based on ID, and then you store the last-known index value in your reference.

Touchback

Accessing a 'thing' by ID brings some new problems: what if a given ID is reused by another thing (like in the ABA problem), what if a consumer needs RAII but the 'thing' isn't there come destruction time, is the performance of that fetch-by-id method important? – Watercolor

@IgorG true, but there are decent battle-proven defaults for these. For the ID, use ever-increasing sequence + interlocked increment (lock xadd) via std::atomic. As for the ownership of thing: with this solution the consumer may never own thing, the store owns it. So no consumer is allowed to assume that thing will exist at any time, it must always be checked. That is also what guarantees the memory-safety, but you must design around this principle. The performance of fetch-by-id will probably be important. If done correctly, ex. open-addressing hash table, it will be very fast. – Touchback

I like this answer (and do not understand why it has been downvoted) because it offers a different, yet viable approach to the problem. Isn't this approach exactly what APIs like OpenGL or Vulkan do when referring to resources? I mean, I don't know how they handle it internally, but I can imagine them to handle it like proposed in this answer since they always return consecutive numbers for handles which point to resources like textures or GPU-buffers. Those numbers are also referred to as "names" of a resource. – Medawar

Answer 3

What about stable_vector from boost? It is a

hybrid between vector and list, providing most of the features of vector except element contiguity

It provides std::vector's random access, constant time insertion/deletion at the end of the sequence and linear time insertion/deletion elsewhere. Most importantly, iterators and references to boost::container::stable_vector's elements are valid as long as the element is not erased.

Cochrane

Answer 4

IMO best approach would be create new container which will behave is safe way.

Pros:

• change will be done on separate level of abstraction
• changes to old code will be minimal (just replace std::vector with new container).
• it will be "clean code" way to do it

Cons:

• it may look like there is a bit more work to do

Other answer proposes use of std::list which will do the job, but with larger number of allocation and slower random access. So IMO it is better to compose own container from couple of std::vectors.

So it may start look more or less like this (minimum example):

template<typename T>
class cluster_vector
{
public:
    static const constexpr cluster_size = 16;

    cluster_vector() {
       clusters.reserve(1024);
       add_cluster();
    }

    ...

    size_t size() const {
       if (clusters.empty()) return 0;
       return (clusters.size() - 1) * cluster_size + clusters.back().size();
    }

    T& operator[](size_t index) {
        thowIfIndexToBig(index);
        return clusters[index / cluster_size][index % cluster_size];
    }

    void push_back(T&& x) {
        if_last_is_full_add_cluster();
        clusters.back().push_back(std::forward<T>(x));
    }

private:
    void thowIfIndexToBig(size_t index) const {
        if (index >= size()) {
            throw std::out_of_range("cluster_vector out of range");
        }
    }

    void add_cluster() {
       clusters.push_back({});
       clusters.back().reserve(cluster_size);
    }

    void if_last_is_full_add_cluster() {
       if (clusters.back().size() == cluster_size) {
           add_cluster();
       }
    }

private:
    std::vector<std::vector<T>> clusters;
}

This way you will provide container which will not reallocate items. It doesn't meter what T does.

Dorman

Downvote: suggesting to "roll your own" (when standard solutions exist) – Ostrich

you mean std::list? It is not like std::list. – Dorman

Answer 5

[A shared pointer] seems like the worst approach to me, because a "thing" shall not own a "consumer" and with shared pointers I would create shared ownership.

So what? Maybe the code is a little less self-documenting, but it will solve all your problems. (And by the way you are muddling things by using the word "consumer", which in a traditional producer/consumer paradigm would take ownership.)

Also, returning a raw pointer in your current code is already entirely ambiguous as to ownership. In general, I'd say it's good practice to avoid raw pointers if you can (like you don't need to call delete.) I would return a reference if you go with unique_ptr

std::vector<std::unique_ptr<thing>> i_am_the_owner_of_things;
thing& get_thing_for_consumer() {
    // some thing-selection logic
    return *i_am_the_owner_of_things[5]; // 5 is just an example
}

Humes

No, shared pointers are there to express ownership. And the "consumer" in my example shall NOT get ownership of "thing" as I have clearly stated. Citing Herb Sutter in his great talk Back to the Basics! Essentials of Modern C++ Style: Non-owning raw pointers are still great. – Medawar

"avoid raw pointers" is a myth. It is raw owning pointers that should be avoided. Then there is also no ambiguity, raw pointers dont own stuff – Engrave