Tessil
commented
4 years ago Hi,
This pop_front implementation will be in O(n) no matter the underlying container. Using pop_front on a std::dequeis effectively in O(1) but after doing that we have to shift all the indexes in the m_buckets array which is a O(n) operation.
We could make it in O(1) with std::deque if we store a shift variable and each time we access bucket_entry::index we subtract this variable. On pop_front we would just have to increment this shift variable. But I'm not too keen to do so as it would reduce the performance even if we never use pop_front, we would need to subtract this variable for each index access even if the variable is zero.
Added pop_front to all three headers, as it is useful to remove the least recently added element.
The present implementation works with std::deque as well as std::vector, albeit inefficiently in the latter case.