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
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.
Comments
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
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.
Memory allocation in particular is very hard to analyze.
It's not conformant.
To make bullet points on HN, put a blank line between the paragraphs.