Здравствуйте.
Имеется проблема в реализации быстрой очереди уникальных сообщений фиксированного размера 8 байт.
С очередью работают три потока.
— Первый должен помещать в конец очереди новое сообщение, при условии, что такого сообщения в очереди нет.
— Второй последовательно извлекать на обработку сообщения из вершины очереди.
— Третий должен иметь возможность удалять из любого места очереди сообщение, отменяя, тем самым, его обработку вторым потоком.

Сейчас задача решена при помощи двух STL контейнеров: list<TMsg> и map<TMsg, list<TMsg>::iterator >.
— Первый поток перед добавлением в конец списка list<TMsg> нового сообщения проверяет наличие такого сообщения в карте map<TMsg, list<TMsg>::iterator >. Если такого сообщения нет, то добавляет его в конец списка, добавляет его и итератор на него в карту. Все это происходит атомарно, с использованием критической секции.
— Второй поток просто атомарно удаляет из двух контейнеров сообщение.
— Третий поток (когда это необходимо), атомарно отыскивает по карте наличие сообщения, удаляет его из карты и из списка по найденному итератору.

Сейчас основная проблема состоит в том, что STL контейнеры на таком маленьком объекте (8 байт) ведут себя очень неоптимально: очень много операций выделения и освобождения памяти.

Вопрос. Известно ли кому более быстрая реализация подобной вещи?
Важно.
1. Очередь может неограниченно расти.
2. Реализация должна быть мультиплатформенной.