title: What is the big O memory usage of maps in C++?
body: <p>I'm wondering what the big O memory usage of maps in C++ (like how arrays use O(n) memory). In the <a href="https://www.cplusplus.com/reference/map/map/map/" rel="nofollow noreferrer">C++ documentation</a>, it says</p>
  <blockquote>
  <p>Constant for the empty constructors (1), and for the move constructors (4) (unless alloc is different from x's allocator).
  For all other cases, linear in the distance between the iterators (copy constructions) if the elements are already sorted according to the same criterion. For unsorted sequences, linearithmic (N*logN) in that distance (sorting,copy constructions).</p>
  </blockquote>
  <p>but I'm having a hard time understanding what this means. Does this mean that maps use O(n*log(n)) memory? Thanks for your help!</p>