Как се определя времевата сложност при търсене на елемент в std::map?

В std::map се използва балансирано двоично дърво (обикновено червено-черно дърво), затова търсенето на елемент има времева сложност O(log n), където n е броят на елементите в контейнера. Това се дължи на факта, че при търсенето елементът се сравнява с възлите на дървото, преминавайки или към левия, или към десния поддърво, като по този начин областта за търсене се намалява наполовина на всяка стъпка.