1
\$\begingroup\$

I just want to gather some feedback about this container, in my view it solves the problem of common data containers which don't have fast access and fast deletion. I want to admit that I have not benchmark this, as I don't understand how to do it and to compare with other containers. I tested it and it works, although it might not be the cleanest or safest code.

map<> has O(log(n)) for access and deletion

vector<> has O(n) for deletion

As you can see, with usual STL containers, you can't have O(1) performance and low memory footprint everywhere.

I heard about object pool some time ago, where instead of deleting objects, you reuse them, but the problem is that you have to resize the vector<>.

Then I've read a suggestion on IRC about swapping the tail of the vector with the item I want to delete. The problem is that the index of the last item is changing.

So I wrote this container with an index mapper.

The index is just two vector<int>, a forward and a backward map, with a queue<int> for available indexes.

The data is a vector<T>.

Each time an item is remove or added, the index is adjusted so that you can still access the item by the same index.

template <typename T>
struct managed_pool {
    queue<size_t> avail;
    vector<T> data;
    vector<int> index, back_index; // forward and backward index
    size_t add(T&&val) {

        // always add to tail since we "swap-pop": 
        data.push_back(val);
        size_t data_index = data.size() - 1;
        size_t index_index;

        // if there's no available index
        if (avail.empty()) {
            // add a new index
            index.push_back(data_index);
            index_index = index.size()-1;
        }
        else {
            // reuse one
            index_index = avail.front();
            avail.pop();
        }
        back_index.push_back(index_index);
        index[index_index] = data_index;

        msgm(val, index_index);
        return index_index;
    }
    void rem(size_t translate_index_delete) {
        auto real_index_backup = data.size() - 1; // you want to keep this
        auto real_index_delete = index[translate_index_delete]; // you want to delete this
        auto translate_index_backup = back_index[real_index_backup];

        index[translate_index_delete] = -1; // invalidate
        avail.push(translate_index_delete);

        data[real_index_delete] = data[real_index_backup]; // here we "swap-pop". We move the .back() of the vector to the index of the item we want to remove. This ensures contiguity of the vector, at a minimal performance cost
        data.pop_back(); // remove it

        index[translate_index_backup] = real_index_delete; // we adjust the mapping table to make sure the item is still indexed at the same index.
    }
    T&operator[](size_t & i) {
        if(index[1] != -1)
        return data[index[i]];
    }
};

I just want to have your opinion if this is good, and if there are better methods than this. Remember that a heap is not what I want. I want the fastest container and keep a low memory footprint, be simple enough, have fast insertion, fast removal, and fast access. I'm not sure queue<> is a good choice.

\$\endgroup\$
2
\$\begingroup\$

Define exactly what properties you want your container to have

You say:

As you can see, with usual STL containers, you can't have O(1) performance and low memory footprint everywhere.

That's not so much a property of STL, but of container structures in general. You only get O(1) performance if you don't have to search and don't have to shuffle memory around, and if you can't shuffle memory around you can't have a low memory footprint. So you have to make some compromises.

You don't mention what you want to optimize for, or what kind of usage patterns you are expecting. It would be good if you could write down (for yourself) what exact properties you want your container to have, and then verify whether your implementation actually has those properties.

Your metadata uses storage as well

Your container has a vector<T> with the actual data, which is quite efficient. However, there is also metadata. In particular, there is vector<int> index, which you never shrink. So this means that if you have an access pattern where there is a short spike where a lot of data is stored in the container, then after the spike the data itself doesn't use a lot of space, but the vector of indices is now very large. Especially if T is small, then the overhead of the indices and availability queue might be very significant.

Note that you also never shrink index, even if it is possible to do so (whenever tail indices are unused).

Adding to a vector<> is amortized O(1)

Adding items to a vector<> might cause memory allocations and moves, so the time used for an addition is variable, and does not have an upper bound. Whenever the STL has to reallocate memory for a vector<>, it basically doubles the size, so with a constant rate of addition, it needs less and less reallocations. The result is that the amortized cost is O(1). However, be aware that this container might not be suitable for a real-time system.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.