Hcfyk

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?

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.

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.

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.