title: std::map and operations of amortized O(log N)
body: <p>I have an assignment in which I must implement the insert member function for a data structure impemented on top of std::map.
  This member function has 3 parameters: firstKey, secondKey, valToInsert.</p>
  <p>The assignment specifies not to make more than 2 operations of amortized O(log N), in contrast to O(1), in which N is the number of elements in map.</p>
  <p>I wrote the code, it compiles and works as it should.
  I am not sure about these 2 operations, though.</p>
  <p>I can not show the entire code (since it is part of the assignment), so I will only list the map's member function I used.
  They are:</p>
  <ul>
  <li>one <code>auto firtstIt = map.lower_bound(firstKey);</code></li>
  <li>one <code>auto secondtIt = map.lower_bound(secondKey);</code></li>
  <li>one <code>map.insert(secondIt, {secondKey, valToInsert});</code></li>
  <li>one <code>map.insert_or_assign(firstIt, firstKey, valToInsert);</code></li>
  <li>one <code>map.erase(std::next(firstKey), secondKey);</code></li>
  <li>several <code>map.erase(it);</code> where &quot;several&quot; depends on the distance between firstIt and secondIt</li>
  </ul>
  <p>Did I meet the condition imposed by the task? If not, why?</p>