В std::map (который является сбалансированным двоичным деревом поиска, например, красно-черным деревом) большинство операций (вставка, удаление, поиск) имеют логарифмическую временную сложность O(\log N), где N — количество элементов в контейнере.
Амортизированная константная сложность, о которой иногда говорят в контексте ассоциативных контейнеров, чаще относится к std::unordered_map (хеш-таблице, см. ниже). В std::map такой амортизированной константной сложности для основных операций нет.
Возможно, вопрос касается амортизированной константной сложности при операциях, которые не являются основными поисковыми или модифицирующими, например, при перемещении итератора. Итераторы в std::map позволяют перемещаться по элементам в отсортированном порядке за амортизированное O(1) время, поскольку структура дерева позволяет находить следующий/предыдущий элемент достаточно эффективно в среднем.
Также стоит упомянуть std::unordered_map – это хеш-таблица. В ней вставка, удаление и поиск имеют среднюю амортизированную сложность O(1) при хорошей хеш-функции и отсутствии большого количества коллизий. Худший случай при большом количестве коллизий или плохой хеш-функции может достигать O(N).
В контексте std::map говорить об амортизированной константной сложности для ключевых операций неверно.