Есть ли простой способ сортировки массива char *? C ++

Question

У меня есть массив char* в файле. Компания, в которой я работаю, хранит данные в виде простых файлов. Иногда данные сортируются, но иногда это не так. Я хочу отсортировать данные в файлах.

Теперь я мог бы написать код для этого с нуля. Есть ли более простой способ?

Конечно, сортировка по месту будет лучшим вариантом. Я работаю с большими файлами и у меня мало оперативной памяти. Но я рассмотрю все варианты.

Все строки имеют одинаковую длину.

Это примерные данные:

the data is of fixed length
the Data is of fixed length
thIS data is of fixed lengt

Это будет представлять три записи длины 28. Приложение знает длину. Каждая запись заканчивается CRLF (\r\n), хотя это не должно иметь значения для этого вида.

Answer 1

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>);

Answer 2

Используйте программу сортировки GNU (внешне), если вы не можете поместить данные в ОЗУ: она будет сортировать файлы произвольного размера, и чем больше файл, тем меньше будет дополнительная стоимость создания процесса.

Answer 3

Вы можете использовать алгоритмы в 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;
}

Answer 4

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); 

Answer 5

Если файлы имеют большой размер и не помещаются в ОЗУ, вы можете использовать bin / bucket sort, чтобы разбить данные на более мелкие файлы и, наконец, объединить фрагменты в файле результатов. Другие ответы показывают, как сортировать каждый отдельный файл корзины.

Answer 6

Вероятно, самый простой способ - использовать старую функцию stdlib.h qsort. Это должно работать:

qsort( array, num_elements, sizeof( char* ), strcmp )

Обратите внимание, что это стандарт C и работает только с английским текстом.

Если у вас есть список объектов String, то в C ++ возможны и другие вещи.

Если вы работаете в Linux и пишете приложения для gtk или Qt, я бы посоветовал вам заранее ознакомиться с этими библиотеками.

Answer 7

Возможно, вы захотите просмотреть файлы, отображенные в память (см. Функцию http://en.wikipedia.org/wiki/Memory-mapped_file), mmap () (http://en.wikipedia.org/wiki/Mmap) в ОС с жалобами POSIX. По сути, вы получите указатель на непрерывную память, представляющую содержание.

Хорошая сторона заключается в том, что ОС позаботится о загрузке частей файла в память и при необходимости выгрузит их снова.

Недостатком является то, что вам необходимо разрешить какую-либо форму блокировки файлов, чтобы избежать повреждения, если более чем один процесс может получить доступ к файлу.

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

Надеюсь, это дало вам некоторые идеи!

Answer 8

Несколько вещей приходят на ум:

1. Если ваши данные слишком велики, чтобы уместиться в память, вы можете просто создать в памяти индекс смещений файлов, а затем отобразить в памяти файл для доступа к строкам (зависит от вашей ОС).
2. На месте потребуется лот копий памяти. Если можете, используйте сортировку оболочки. Затем, как только вы узнаете окончательный порядок, гораздо проще изменить порядок строк за линейное время.
3. Если все строки одинаковой длины, вы действительно хотите радикальную сортировку. Если вы не знакомы с радикальной сортировкой, вот основная идея: сортировка на основе сравнения (то есть то, что std::sort, qsort и любая другая универсальная сортировка) всегда требует O (N log N) времени. Radix сортировка сравнивает одну цифру за раз (начиная с str[0] и заканчивая str[K-1] для строки K-длины), и в целом может потребоваться только O (N) время для выполнения.

Обратитесь к Интернету за более подробным описанием алгоритмов сортировки по основанию, чем я могу предоставить. Помимо того, что я сказал, я бы избегал всех других решений, которые используют стандартные средства сортировки библиотек. К сожалению, они не предназначены для вашей конкретной проблемы.

Answer 9

Канонический способ сортировки массива символьных строк в 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...
}