I agree w/ the LRU, but isn't a vector more efficient for building a queue? (You use it as a ring-buffer. Push/pop are O(1) (amortized for push), and it interac

I agree w/ the LRU, but isn't a vector more efficient for building a queue? (You use it as a ring-buffer. Push/pop are O(1) (amortized for push), and it interacts well with the CPU cache since the memory is contiguous. And you get O(1) indexing, too.) Then there's the rather interesting datastructure that C++ has, std::deque, which seems to get implemented as a vector of pointers to vectors. Still O(1) push/pop/index.