[adrianN]

If those lists are anywhere on your hot path benchmarking with a deque build from two vectors, or a circular buffer as you suggested, would be worthwhile imho. The constants in linked lists are such that the O(1) operations are often slower than the O(n) operations in vectors, at least for lists that fit in cache, and depending on your allocator etc. Chasing pointers to more or less random memory locations is pretty much the worst case workload for a modern CPU.