Re: Unsorted map?
On Thu, 08 Nov 2007 02:32:01 -0800, hg@x-formation.com wrote:
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::pair<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).
--
Joel Yliluoma - http://bisqwit.iki.fi/
: comprehension = 1 / (2 ^ precision)