[krona]

CppReference defines the time complexity is constant: https://en.cppreference.com/w/cpp/container/deque/push_front

So does this mean: - We're talking about different complexities (Amortized vs something else) - The libc++ implementation isn't standards conformant - The analysis in the c++ standard is incorrect. - Something else

[Kranar]

Neither is correct. Generally when complexity is specified in the standard, it's with respect to a specific operation. In this case the standard specifies that it's the number of calls to the constructor of T that must be constant, which means that push_back and push_front can not copy or move its elements.

There is never a way to guarantee that the physical amount of time is bounded by O(1) in the worst case. You could always have pathological scenarios or data structures written so that performing a move or copy of a single T could require O(n^n) time for all anyone knows.

[gpderetta]

Memory allocation in particular is very hard to analyze.

[im3w1l]

It's not conformant.

[mkl]

To make bullet points on HN, put a blank line between the paragraphs.