Q:

Is there a efficient way to search a key in queue and override its value? 

I am writing an application using C++ in which I need to implement a message queue that will continuously receive data (i.e. object) from network, every object has a key (e.g. name of company say Oracle, Google etc.).  If the queue consumer is slower, I can have huge amount of elements in the queue (max limit can be kept in millions). 
Requirement is: If an object with key XYZ is arrived from network and queue already have object with key XYZ then I need to over write that object and position of that object in the queue should remain same.  For example if an object of key "Oracle" with the value 25 is arrived from network and an object with the key "Oracle" and value 10 is already present at position 120 in the queue then I need to over write value 10 with value 25 and position should remain 120. 
I try to implement this using thread safe queue and set, on arrival of an object from network first I check whether key is present in set, if key is not present I add key in the set and add object in the queue.  If key is present then I perform liner search for the key in the queue and override the object. 
Performance will be very slow if I get very frequent updates for keys which I have already in the queue. 
Is there any efficient way to implement this ?  Thanks in advance. 

A:

Since a queue isn't sorted, there's no real way to get faster to data than a linear search. 
You may use a queue with priority.  The std::priority_queue doesn't allow quick priority change, you will have to use boost. 
You may also try this algorithm:

Store key like Google, Microsoft, Apple, etc.  in an unordered_map. 
Keep also a count of how many items have been processed so far. 
When removing item from the queue, increment the count and remove the key from the map. 
When an item arrive to the queue,

look in the map if the key exists (linear time)
if it does, change the value at queue[index -count] (linear time)
if it doesn't yet, store map[key] = count + index where the new item is placed in the queue (linear amortized time)

I offer no guaranty, I haven't tested this algorithm.