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)

• Loki Astari: You can store there index. Even if the vector grows the index of an element does not become invalid.
• xDaevax: Is this asking for a review or an alternative library?
• tower120: @LokiAstari But it become invalid when you insert / erase in the middle.
• Loki Astari: Looks you are trying to create a multi index container. I would look at the boost implementation for some ideas. PS. USes classes.
• Loki Astari: @tower120 No problem. But a bit more research your side first. The first big step in C++ is encapsulation. Do the same thing in a class with methods so that nobody else can mutate the state. Then I'll do a big review with lots of suggestions.

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 */
};

• tower120: The code in question is just condensed version of coliru.stacked-crooked.com/a/044f33b3f219f3f9 (which is in the very bottom of the question). Could you show, instead, how to use boost::multi_index to achieve the same result?
• Deduplicator: emplace_back is different: en.cppreference.com/w/cpp/container/vector/emplace_back