Почему вставка сортировки + подсказки в std::map повышает производительность? ⇐ C++

[Anonymous]

Я пытаюсь воспользоваться подсказкой вставки в std::map для вставки большого количества пар ключ-значение, и я заметил, что вставка их в отсортированном порядке ключей происходит значительно быстрее, чем вставка тех же элементов в случайном порядке.
Это согласуется с тем фактом, что std::map обычно реализуется как красно-черное дерево, где количество поворотов и операций балансировки зависит от порядка вставки. Однако я хотел бы подтвердить, ожидается ли такое поведение в соответствии с гарантиями сложности std::insert, и известно ли, что сортированная вставка уменьшает количество шагов ребалансировки.
Мои вопросы:

• Ожидается ли улучшение производительности при вставке ключей в отсортированном порядке, учитывая обычную реализацию std::map в виде красно-черного дерева?
• Разрешает ли стандарт реализациям использовать преимущества сортированной вставки (например, меньшее количество вращений) или это просто деталь реализации?
• Когда набор ключей известен заранее, существуют ли другие соответствующие стандарту методы снижения стоимости вставки?

Ниже приведен минимальный воспроизводимый пример с результатами синхронизации.

Код: Выделить всё

#include 
#include 
#include 
#include 
#include 

int main() {
std::map m0, m1;
// Generate random input
std::vector vins(10000);
for (auto& p : vins) {
p.first = rand() % 1000000;
p.second = rand() % 2;
}
// Baseline: normal insertion
clock_t t0 = clock();
m0.insert(vins.begin(), vins.end());
clock_t t1 = clock();
std::cout