C++ std::vector with always valid iterator/pointer/index/key

Question

Motivation: Have std::vector<std::unique_ptr<T>> accessibility at std::vector<T> speed.

std::vector have one inconvenience - you can't store pointers nor indexes to elements if the vector grows/alters.

To overcome this problem we usually use vector of pointers / deque (if only grow) / list / etc. Having our elements in heap have significant overhead on creation, traverse, and per element access.

To store "pointer" (or key) to element in vector I have back array of indices.

Condensed version:

struct Key{
   int index;  // index of key_indices
};

struct Element {
    int key_index;   // never changes
    Value value;
};
std::vector<Element> data;       // usual continious vector, no magic here
std::vector<int> key_indices;    // point to data[]. these values changes when erase/insert to data
std::vector<int> free_indices;

void emplace_back(){
   // if have no free_indices
   data.emplace_back();
   key_indices.emplace_back(data.size() - 1);
   data.back().key_index = key_indices.size() - 1;
}

Key get_key(std::vector<Element>::iterator iter){
    return {iter->key_index};
}

Value& operator[](Key key){
   return data[key_indices[key.index]].value;
}

Value& operator[](int index){
   return data[index].value;
}

void erase(std::vector<Element>::iterator iter){
    free_indices.push_back(iter->key_index);
    update_indices(iter + 1, data.end(), -1);
    data.erase(iter);
}
// same with insert, emplace_front, etc.

template<class iter>
void update_indices(iter from, iter to, int shift) {
    for (auto it = from; it != to; ++it)
    {
        key_indices[it->key_index] += shift;
    }
}

And used like:

KeyContainer<Data> list;

list.emplace_back().back().x = 100;
list.emplace_back().back().x = 200;

auto key = list.get_key(list.end()-1);

list.erase(list.begin());               // all indices invalidated
std::cout << list[key].x << std::endl;  // key still valid

In other words Key - is array index that always points to the same element, just like pointer to std::vector<std::unique_ptr<T>> element.

It is approximately 6-10 times faster than std::vector<std::unique_ptr<T>>/list on creation, 3-4 times faster than deque(at least with VS2015/clang). Same speed as vector when traverse/index access. And approx 10% slower with key access. I tried to use pointers instead of indices, but didn't see a difference.

Is there some ready library solution for container like this (vector with indices back-array (or ptr back-array))?

Full code as is (just a concept proof)

Answer 1

Quick review (in anticipation of more code).

The main issue I have with the code is that is not encapsulate in a class.

std::vector<Element> data;       // usual continious vector, no magic here
std::vector<int> key_indices;    // point to data[]. these values changes when erase/insert to data
std::vector<int> free_indices;

These are basically global variables and anybody can access an mutate them (not just maliciously but accidently). C++ has the ability to encapsulate all the parts of a class and protect it from accidental misuse by only allowing certain functions (methods) to access the raw underlying data.

class MultiIndexToElement
{
    private:
        std::vector<Element> data;         // usual continious vector, no magic here
        std::vector<int>     key_indices;  // point to data[]. these values changes when erase/insert to data
        std::vector<int>     free_indices;
    public:
        void emplace_back();
        Key get_key(std::vector<Element>::iterator iter);

        Value& operator[](Key key);            
        Value& operator[](int index);

        void erase(std::vector<Element>::iterator iter);

     private:
        template<class iter>
        void update_indices(iter from, iter to, int shift);
};

Now that we can see the interface clearly there are a couple of things you should watch for.

Const correctness.

A method that does not change the state of the object should be marked const. This tells the compiler that calling this method does not change the object.

      Key get_key(std::vector<Element>::iterator iter) const;
                                                  //   ^^^^^

This is important because objects get passed to functions by const reference a lot in C++ to avoid the cost of copying the object.

Element Access

Usually containers allow tow forms of element accesses. Mutating access and const accesses.

        Value&       operator[](int index);       // This allows mutating access.
        Value const& operator[](int index) const; // This allows const accesses.

Emplace Back.

Usually emplace back (a new form of push back). Creates the Element in place using one of Elements constructors. Your version only allows for Element to have zero parameter constructor.

It is usually written like this:

 template<Args... args>
 void emplace_back(Args&& args...) {
     data.emplace_back(std::forward<Args>(args)...);     // pass arguments to constructor
     .... /* Other stuff you need */
 }

The Args... part is a new part of C++14 so you will need to tell your compiler to use the newer version of the standard (that's not a default yet). But usually this means adding -std=c++14 to the command line.

Templatization

Your code does not allow for easy templatization. In fact you don't define Value in the code sample above. This is more easily solved using templates around a class.

template<typename Value>
class MultiIndexToElement
{
     /* STUFF */
};