The time complexity of the libc++ deque push_front implementation is O(log n)

Re:The time complexity of the libc++ deque push_front implem... by krona on Sunday November 28, 2021 @08:18AM (#29368680)

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

[ Parent | on HN ]

Re:The time complexity of the libc++ deque push_front implem... by Kranar on Sunday November 28, 2021 @02:53PM (#29372299)

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.

[ Parent | on HN ]

Re:The time complexity of the libc++ deque push_front implem... by gpderetta on Sunday November 28, 2021 @03:51PM (#29372883)

Memory allocation in particular is very hard to analyze.

[ Parent | on HN ]

Re:The time complexity of the libc++ deque push_front implem... by im3w1l on Sunday November 28, 2021 @08:21AM (#29368699)

It's not conformant.

[ Parent | on HN ]

Re:The time complexity of the libc++ deque push_front implem... by mkl on Sunday November 28, 2021 @08:49AM (#29368878)

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

[ Parent | on HN ]