Задача на сортировку Опции

[klem4]

Есть следующая задача:

Входные данные
Дано число N (1 ≤ N ≤ 100000), а затем в одной или нескольких строках N натуральных чисел из диапазона от 1 до 100.
Выходные данные
Выведите в одной строке N чисел в неубывающем порядке.

Есть ограничения:
Лимит времени: 0.1 секунды

Понятно, что сортировать тут ничего не нужно, так как в заданное время не уложиться, есть решение:

Спойлер (Показать/Скрыть)

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

using namespace std;

int main()
{
    long n = 0;
    vector<long> counts(101, 0);

    cin >> n;

    int value = 0;
    while ( n-- )
    {
        cin >> value;
        ++counts[value];
    }

    stringstream ss;

    for (int i = 1; i <= 100; i++ )
    {
        for (long j = 0; j < counts[i]; j++ )
        {
            ss << " " << i;
        }
    }

    string s = ss.str();
    s.erase(s.begin());
    cout << s << endl;

    return 0;
}

Но оно проходит всего-лишь 78.6% тестов, на остальных - превышение времени, максимальное время работы 0.109 секунды из 0.1 секунды, то есть превышение в 0.009с. От куда мне их взять ума не приложу Пробовал кучу разных вариантов, без векторов, без строк, все только хуже. Нид хелп

Добавлено через 19 мин.
вопрос решен, помогла замена iostream на stdio.h

[-TarasBer-]

> А ты всерьез считаешь, что пробежаться по дереву одним циклом будет медленнее, чем организовать несколько (до 100) циклов, и в каждом из них делать что-то

Ты вообще поразрядную сортировку знаешь, или как?
Проверь, а потом говори, ладно?

> а потом еще и по результирующей строке пройтись erase-ом?

Тут согласен - удаление символа из начала строки - это неправильно.
Лучше бы он писал не "пробел-число", а "число-пробел", а потом удалял символ из конца.

> Знаешь, я вообще не обязан ничего никому посылать.

То есть аргументировать свои утверждения не можешь?

> На миллионе входных значений (из файла) никакого проседания (тем более - пятикратного) multimap-а не заметил

А ты сравнивал его с поразрядной сортировкой? По сравнению с ЧЕМ проседания ты не заметил?

> Если у тебя комплятор - дерьмо - это твои личные проблемы.

Причём тут компилятор, если мы алгоритм обсуждаем?

> Интеловский компилер уделает мультимапом любую из самописных сортировок.

Ты понимаешь разницу между оптимизацией микрокода и реализацией стандартной библиотеки? Это непересекающиеся вещи. Если алгоритм из библиотеки не подходит под данную задачу (а универсальные вещи всегда сливают узкоспециализированным), то никакой компилятор тебе не сделает неправильный алгоритм правильным.
Давай, чтобы честно было, прогони и поразрядную сортировку через ICC.

> STL применяется в таких проектах, что у тебя диска не хватит исходники сохранить, и никто не собирается от него отказываться

Да только в участках, где нужна предельная скорость, СТЛ заменяется на велосипеды. А если не заменяется, значит там скорость всех устраивает и выжимать такты никому не надо.

> и все равно проигрывать современным компиляторам на современных камнях.

Ах, нам ещё и современный камень нужен, да?
Если уж говорить о крупных проектах, то там вообще С++ не нужен. Дешевле вот именно, взять язык попроще и тот самый современный камень прикупить, чем платить несчастным крестопрограммистам за их непроизводительный (а на С++ он другим не будет) труд. Я вообще не знаю, где С++ нужен, он держится только на старых библиотеках.