std::multiset<int> arr;
    //...
    while (set.size() > 1)
    {
        std::multiset<int>::const_iterator itA = arr.begin();
        std::multiset<int>::const_iterator itB = ++arr.begin();
        double c = *itA + *itB;
        set.erase(itA, ++itB);
        set.insert(c);
    }

For the first version ( insert(x) ), logarithmic.
For the last version ( erase(first,last) ), logarithmic in container size plus linear in the distance between first and last.

S>    std::multiset<int> arr;
S>    //...
S>    while (set.size() > 1)
S>    {
S>        std::multiset<int>::const_iterator itA = arr.begin();
S>        std::multiset<int>::const_iterator itB = ++arr.begin();
S>        double c = *itA + *itB;
S>        set.erase(itA, ++itB);
S>        set.insert(c);
S>    }
S>

S>Вот как такое может быть? Компилятор MinGW. Тестировалось на 300000 эл.

    std::multiset<int> arr;
    //...
    while (set.size() > 1)
    {
        std::multiset<int>::const_iterator itA = arr.begin();
        std::multiset<int>::const_iterator itB = ++arr.begin();
        double c = *itA + *itB;
        arr.erase(itA, ++itB);
        arr.insert(c);
   }

Возьмём вот такую простенькую функцию перемножения матриц:

void multiply(T* X, T* Y, T* Z, int size)
{
    for (int i = 0; i != size; ++i)
        for (int j = 0; j != size; ++j)
            for (int k = 0; k != size; ++k)
                Z[i*size+j] += X[i*size+k] * Y[k*size+j];
}

Запускаю для матриц размера 512 — результат 16.9 секунды.
Запускаю для матриц размера 513... делайте ставки, господа! Результат 4.8 секунды!
Причина кроется в паттерне прохода по матрице Y во внутреннем цикле. При размере матрицы 512 размер строки матрицы составляет 4096 байт (8-байтовые элементы). Соответственно адреса элементов Y[0][0] и Y[1][0] имеют одинаковые младшие 12 бит. Это вызывает постоянные конфликты в кэше с вытеснением старых данных.