Сортировка массива номеров версий в C++

Дан массив номеров версий, как это:Сортировка массива номеров версий в C++

vector<string> v = { "9.8.17.5295", "9.13.0.0", 
          "12.3.9.1017", "25.3.6.1" };

Каков наилучший способ сортировки их в C++? Проблема здесь, конечно, в том, что мы не можем просто сортировать их лексикографически, но мы должны разделить каждую строку на компоненты и сравнить эти компоненты численно. В Python это можно сделать следующим образом:

v.sort(key=lambda x : tuple(map(int, x.split('.'))))

Но как это сделать на C++? Все, что я могу придумать, выглядит довольно громоздким по сравнению с этим однострочным. Лучшее, что я нашел до сих пор это:

array<int, 4> splitversion(const string& s) 
{ 
    array<int, 4> z; 
    sscanf(s.c_str(), "%d.%d.%d.%d", &z[0], &z[1], &z[2], &z[3]); 
    return z; 
} 

int main() 
{ 
    vector<string> v = { "9.8.17.5295", "25.3.6.1", "9.13.0.0", "12.3.9.1017" }; 
    sort(v.begin(), v.end(), [](string s1, string s2) 
      { return splitversion(s1) < splitversion( s2); }); 
}

Конечно, sscanf настоящее время неодобрительно C++ людей, так что я, возможно, придется заменить его на что-то другое, но, насколько я могу сказать, то это становится еще более громоздким. Как вы это сделаете?

источник

2013-11-19 pentadecagon

Выполняет '' '' на 'std :: array' так, как вы ожидаете (отдавая предпочтение первому элементу и т. Д.)? –

Я точно ожидаю. Компилятор не жаловался, поэтому этот оператор существует, и каким другим способом он мог работать? – pentadecagon

Он может быть реализован как a0

Никто не будет хмуриться :) Это выглядит приличным решением. Более быстрым решением будет хэш каждого элемента и сортировка в соответствии с хешами. Пример хэша будет:

array<int, 4> z; 
sscanf(s.c_str(), "%d.%d.%d.%d", &z[0], &z[1], &z[2], &z[3]); 
unsigned long long hash = (z[0] << 24) + (z[1] << 16) + (z[2] << 8) + z[3];

переход исходного массив/вектор и сортировки в соответствии с хеш-значений будет значительно быстрее быть на длинных векторах. Для этого потребуется больше кода. Что касается минимального кода, то это очень приятно. Вы можете использовать лямбда-функции, но они менее читаемы.

источник

2013-11-19 22:01:45 egur

Ум, сортировка хешей не сортирует исходные значения. Ваша версия будет сортировать '1.0.1.0' перед' 1.0.0.32768'. –

@egur, Спасибо, я буду иметь это в виду, если есть проблемы с производительностью. У меня есть несколько тысяч в моих списках. И Раймонд прав, все смены должны быть вдвое больше, длинный - 64 бит. – pentadecagon

Я бы просто сделать то же самое, за исключением

char c; 
istringstream(s) >> z[0] >> c >> z[1] >> c >> z[2] >> c >> z[3];

Хотя, все, что потоки довольно медленно, так что лучше использовать что-то вроде boost::spirit в случае, если у вас есть много номеров версий или по крайней мере подготовить данные в vector<pair<array<int, 4>, string>> перед сортировкой.

источник

2013-11-20 01:35:27

Сортировка массива номеров версий в C++

ответ

Смежные вопросы