Unsorted map?

[hg]

I'm in search of a STL datastructure which will let me implement an
unsorted map.

I have data in the form of a key and corresponding value which needs
to be used as a FIFO queue.
In most cases I will look at the first item in this queue to see if
the key matches the expected. However in some cases I would like to
remove values with a specific key.
Furthermore "exceptions" to the FIFO can occur where values with
specific information can be taken out before the first element.

How would I implement this?

-- Henrik

 

[Joel Yliluoma]

I'm in search of a STL datastructure which will let me implement an
unsorted map.

I have data in the form of a key and corresponding value which needs
to be used as a FIFO queue.
In most cases I will look at the first item in this queue to see if
the key matches the expected. However in some cases I would like to
remove values with a specific key.
Furthermore "exceptions" to the FIFO can occur where values with
specific information can be taken out before the first element.

How would I implement this?

There is no data structure that does exactly what you asked in one shot.
There is a hash_map in GCC and TR1 that is not sorted, but it is
not a FIFO either.

I do not know your performance requirements,
but you could try this:

// declaration:
typedef std:air<keytype, valuetype> pairtype;
typedef std::deque< pairtype> queuetype;

queuetype fifoqueue;

// pushing
fifoqueue.push_back( pairtype(key1, value1) );
fifoqueue.push_back( pairtype(key2, value2) );

// popping
pairtype v = fifoqueue.front();
fifoqueue.pop_front();

// searching
queuetype::iterator i = std::find_if(
fifoqueue.begin(), fifoqueue.end(),
select1st<pairtype> () );

// utility
template<typename pair>
struct select1st
{
typename pair::first-type& operator()
(pair& x) const { return x.first; }
const typename pair::first-type& operator()
(const pair& x) const { return x.first; }
};

This will have pushing and popping complexity that
of std::deque<> (O(1)), and searching complexity
that of std::find_if (O(N)).
Removing searched elements is another O(N).

Achieving O(log N) searching complexity while also maintaining the
order of entries would require using a separate index. For example,

std::map<keytype, valuetype> container;
std::deque<std::map<keytype, valuetype>::iterator> index;

Where push is done by adding a value into the container and pushing
its iterator into the index, and popping is done by retrieving the
first iterator from the index, and deleting it from both containers
after retrieving the value. Searching is done with container.find()
as usual.
In this implementation, pushing, popping and searching are all O(log N),
but _removing_ searched elements is still O(N) as it requires first
searching the iterator from the index and then removing it, both O(N).

 

[Victor Bazarov]

I'm in search of a STL datastructure which will let me implement an
unsorted map.

There is no such "STL datastructure".

I have data in the form of a key and corresponding value which needs
to be used as a FIFO queue.
In most cases I will look at the first item in this queue to see if
the key matches the expected. However in some cases I would like to
remove values with a specific key.
Furthermore "exceptions" to the FIFO can occur where values with
specific information can be taken out before the first element.

How would I implement this?

If you use a simple 'list' (or 'deque') of 'pair', you will implement
the ordered container of your key-value combinations. In order to
remove the specific pair from the collection, you just need to do
the 'find_if' with a particular predicate. If you do it rarely, the
linear search complexity shouldn't be too much of a hindrance.

There is this "priority queue" thing, but I've never used it, and do
not know if it's going to help you.

V

 

[Joel Yliluoma]

// searching
queuetype::iterator i = std::find_if(
fifoqueue.begin(), fifoqueue.end(),
select1st<pairtype> () );

Actually, this line is incomplete, it still needs a comparator.
I'll leave that as an exercise.

Achieving O(log N) searching complexity while also maintaining the
order of entries would require using a separate index. For example,

std::map<keytype, valuetype> container;
std::deque<std::map<keytype, valuetype>::iterator> index;

Where push is done by adding a value into the container and pushing
its iterator into the index, and popping is done by retrieving the
first iterator from the index, and deleting it from both containers
after retrieving the value. Searching is done with container.find()
as usual.
In this implementation, pushing, popping and searching are all O(log N),
but _removing_ searched elements is still O(N) as it requires first
searching the iterator from the index and then removing it, both O(N).

With hash_map you can improve the performance further a bit, but
it won't overcome the double O(N) in removing searched elements.

I'm thinking of adding an iterator to the deque in the container's
datatype, but that will contain a recursion that the C++ data type system
cannot handle.

I.e.
typedef
hash_multimap<keytype, std:air<valuetype, IndexType::iterator> >
ContType;
typedef
hash_map<int/*index*/, ContType::iterator>
IndexType;
is an error.
There may be a way to overcome that problem with pointers or forward
declarations, but I'm still not sure what that does to running time,
because of iterator invaditation rules.