Amortized O(1) Complexity in C++
summary
Shows how amortized analysis works with concrete examples: uses the accounting method (coins) to analyze vector push_back, demonstrating amortized O(1) with a 3 coins budget per insertion despite occasional O(n) resizes. Examines std::ranges::begin on a filtered view and points out the standard relies on memoization so the first begin costs O(n) and later calls are O(1), making the standard's phrasing of amortized constant misleading when only a single call occurs.
AI-written summary · about
related talks
55mIntroduction to C++ Containers - Know Your Data Structures
01h 04mBack to Basics: Standard Library Containers in Cpp
06mUsing STL containers efficiently
45mMost of the Time It Works Every Time: The Mindset Behind Using Probabilistic Data Structures
48mA Helicopter Tour of Purely Functional Data Structures
01h 02m“Lightweight Object Persistence With Relocatable Heaps in Modern C++"
45mBeyond Lists: High Performance Data Structures
56mWhy Data Access Patterns Have Always Mattered