Data structure that maps unique id to an object

Question

I'm looking for a C++ data structure that will let me associate objects with a unique numeric value (a key), and that will re-use these keys after the corresponding object have been removed from the container. So it's basically somewhat of a hybrid map/queue structure. My current implementation is a

std::map<size_t, TObject>

and I insert objects like this:

 size_t key = (m_Container.end()--)->first + 1;
 m_Container[key] = some_object;

which works fine for my purposes (I will never allocate more than size_t objects); yet still I keep wondering is there is a more specialized container available, preferably already in the stl or boost, or that there is a way to use another container to achieve this goal.

(Of course I could, rather than taking the highest key in my map and adding one, every time go through the map and search for the first available key but that would reduce complexity from O(1) to O(n) Also it would be nice if the API was a simple

size_t new_key = m_Container.insert(object);

).

Any ideas?

Answer 1

If you're never going to allocate more than size_t keys then I recommend you simply use a static counter:

size_t assign_id()
{
    static size_t next_id;
    return next_id++;
}

And if you want a nice API:

template<class Container>
size_t insert(Container & container, TObject const & obj)
{
     container.insert(obj);
     return assign_id();
}

std::set<TObject> m_Container;
size_t new_key = insert(m_Container, object);

Answer 2

I'm not certain what you exactly want from your ID. As it happens, each object already has a unique ID: its address! There are no two distinct objects with the same address, and the address of an object doesn't change over its lifetime.

std::set<T> typically stores its T values as members of larger nodes, not independent objects. Still, the T subobjects are never moved, and thus their addresses too are stable, unique identifiers.

Answer 3

Create std::set<key_type> removed_keys; of the removed keys. If removed_keys is not empty then use key from removed_keys else create a new key.

Answer 4

Why not just use a vector?

std::vector<TObject> m_Container;

size_t key = m_Container.size();
m_Container.push_back(some_object);

Of course this could be completely useless if you have other usage characteristics. But since you only describe insert and the need for a key (so extracting) it is hard to give any other clear answer. But from these two requirements a std::vector<> should work just fine.

If you have some other usage characteristics like: (Elements can be removed), (we insert elements in large blocks), (we insert elements infrequently) etc these would be interesting factoids that may change the recommendations people give.

You mention that you want to search for un-used elements ID's. This suggests that you may be deleting elements but I don't see any explicit requirements or usage where elements are ebing deleted.

Looking at your code above:

size_t key = (m_Container.end()--)->first + 1;

This is not doing what you think it is doing.
It is equivalent too:

size_t key = m_Container.end()->first + 1;
m_Container.end()--;

The post decrement operator modifies an lvalue. But the result of the expression is the original value. Thus you are applying the operator -> to the value returned by end(). This is (probably) undefined behavior.

See the standard:

Section:5.2.6 Increment and decrement
The value of a postfix ++ expression is the value of its operand.

m_Container.end()--  // This sub-expresiion returns m_Container.end()

Alternative:

#include <vector>

template<typename T>
class X
{
    public:
        T const& operator[](std::size_t index) const    {return const_cast<X&>(*this)[index];}
        T&       operator[](std::size_t index)          {return data[index];}
        void        remove(std::size_t index)           {unused.push_back(index);}

        std::size_t insert(T const& value);
    private:
        std::vector<T>                  data;
        std::vector<std::size_t>        unused;
};

template<typename T>
std::size_t X<T>::insert(T const& value)
{
    if (unused.empty())
    {
        data.push_back(value);
        return data.size() - 1;
    }
    std::size_t result  = unused.back();
    unused.pop_back();
    data[result]    = value;
    return result;
}

Answer 5

Is there a reason that you need std::map to not remove a key, value pair?

This sounds like an attempt at premature optimization.

A method is to replace the value part with a dummy or place holder value. The problem in the long run is that the dummy value can be extracted from the std::map as long as the key exists. You will need to add a check for dummy value every time the std::map is accessed.

Because you want to maintain a key without a value, you most likely will have to write your own container. You will especially have to design code to handle the case when the client accesses the key when it has no value.

Looks like there is no performance gain for using standard containers and a key without value pair. However, there may be a gain as far as memory is concerned. Your issue would reduce fragmentation of dynamic memory; thus not having to re-allocate memory for the same key. You'll have to decide the trade-off.