Есть ли простой способ сортировки массива символов *? C++
У меня есть массив char*
в файле. Компания, в которой я работаю, хранит данные в виде простых файлов. Иногда данные сортируются, а иногда нет. Я хотел бы отсортировать данные в файлах.
Теперь я мог бы написать код для этого с нуля. Есть ли более простой способ?
Конечно, сортировка по месту была бы лучшим вариантом. Я работаю с большими файлами и у меня мало оперативной памяти. Но я рассмотрю все варианты.
Все строки имеют одинаковую длину.
Вот некоторые примеры данных:
the data is of fixed length
the Data is of fixed length
thIS data is of fixed lengt
Это будет представлять три записи длины 28. Приложение знает длину. Каждая запись заканчивается CRLF (\r\n
), хотя это не должно иметь значения для такого рода.
9 ответов
template<size_t length> int less(const char* left, const char* right) {
return memcmp(left, right, length) < 0;
}
std::sort(array, array + array_length, less<buffer_length>);
Используйте программу сортировки GNU (внешне), если вы не можете поместить данные в оперативную память: она будет сортировать файлы произвольного размера, и чем больше размер файла, тем меньше будут дополнительные затраты на создание процесса.
Вы можете использовать алгоритмы в STL для массивов собственных типов данных, а не только для контейнеров STL. Другое предложение использовать std:: sort не будет работать так, как было опубликовано, потому что strcmp возвращает значение, которое оценивается как true для всех сравнений, когда строки не совпадают, а не только если левая часть меньше правой сторона стороны - это то, что хочет std:: sort; двоичный предикат, возвращающий true для левой части, меньше, чем для правой части.
Это работает:
struct string_lt : public std::binary_function<bool, char, char>
{
bool operator()(const char* lhs, const char* rhs)
{
int ret = strcmp(lhs, rhs);
return ret < 0;
}
};
int _tmain(int argc, _TCHAR* argv[])
{
char* strings [] = {"Hello", "World", "Alpha", "Beta", "Omega"};
size_t numStrings = sizeof(strings)/sizeof(strings[0]);
std::sort(&strings[0], &strings[numStrings], string_lt());
return 0;
}
boost::bind
может сделать это:
// ascending
std::sort(c, c + size, boost::bind(std::strcmp, _1, _2) < 0);
// descending
std::sort(c, c + size, boost::bind(std::strcmp, _1, _2) > 0);
Редактировать: строки не заканчиваются нулем:
// ascending
std::sort(c, c + array_size, boost::bind(std::memcmp, _1, _2, size) < 0);
// descending
std::sort(c, c + array_size, boost::bind(std::memcmp, _1, _2, size) > 0);
Если файлы имеют большой размер и не помещаются в ОЗУ, вы можете использовать сортировку bin/bucket, чтобы разбить данные на более мелкие файлы и, наконец, объединить фрагменты в файл результатов. Другие ответы показывают, как сортировать каждый отдельный файл корзины.
Вероятно, самый простой способ - использовать старую функцию stdlib.h qsort. Это должно работать:
qsort( array, num_elements, sizeof( char* ), strcmp )
Обратите внимание, что это стандарт C и работает только с английским текстом.
Если у вас есть список объектов String, то в C++ возможны другие вещи.
Если вы работаете в Linux и пишете приложения для gtk или Qt, я бы посоветовал вам взглянуть на эти библиотеки заранее.
Вы, вероятно, хотите посмотреть в отображенные в память файлы (см. Http://en.wikipedia.org/wiki/Memory-mapped_file), функцию mmap() ( http://en.wikipedia.org/wiki/Mmap) в POSIX- жалоба ОС. По сути, вы получите указатель на непрерывную память, представляющую содержимое файла.
Хорошая сторона заключается в том, что ОС позаботится о загрузке частей файла в память и при необходимости выгрузит их снова.
Недостатком является то, что вам нужно разрешить какую-либо форму блокировки файлов, чтобы избежать повреждения, если более чем один процесс может получить доступ к файлу.
Еще одним недостатком является то, что это не гарантирует хорошую производительность - для этого вам потребуется алгоритм сортировки, который пытается избежать постоянной загрузки и выгрузки страниц (если, конечно, у вас недостаточно памяти для загрузки всего файла в память).
Надеюсь, что это дало вам некоторые идеи!
Несколько вещей приходят на ум:
- Если ваши данные слишком велики, чтобы поместиться в память, вы можете просто создать индекс в памяти для смещений файлов, а затем отобразить в памяти файл для доступа к строкам (зависит от вашей ОС).
- На месте будет требоваться много копий памяти. Если можете, используйте сортировку оболочки. Затем, как только вы узнаете окончательный порядок, гораздо проще переставить строки на месте за линейное время.
- Если все строки одинаковой длины, вы действительно хотите сортировку по кругу. Если вы не знакомы с сортировкой по основанию, вот основная идея: сортировка на основе сравнения (вот что
std::sort
,qsort
и любая другая сортировка общего назначения) всегда требует времени O(N log N). Radix сортировка сравнивает одну цифру за раз (начиная сstr[0]
и заканчивается вstr[K-1]
для строки K-длины), и в целом может потребоваться только O(N) время для выполнения.
Проконсультируйтесь в Интернете, чтобы получить более подробное описание алгоритмов сортировки по основанию, чем я могу предоставить. Помимо того, что я сказал, я бы избегал всех других решений, которые используют стандартные средства сортировки библиотек. К сожалению, они не предназначены для вашей конкретной проблемы.
Канонический способ сортировки массива символьных строк в C и, следовательно, доступный, но не обязательно рекомендуемый способ сделать это в C++, использует уровень косвенности для strcmp()
:
static int qsort_strcmp(const void *v1, const void *v2)
{
const char *s1 = *(char * const *)v1;
const char *s2 = *(char * const *)v2;
return(strcmp(s1, s2));
}
static void somefunc(void) // Or omit the parameter altogether in C++
{
char **array = ...assignment...
size_t num_in_array = ...number of char pointers in array...
...
qsort(array, num_in_array, sizeof(char *), qsort_strcmp);
...more code...
}