Есть ли простой способ сортировки массива 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

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

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

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

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

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

Answer 6

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

Answer 7

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

Answer 8

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

<Ол>

Если ваши данные слишком велики, чтобы уместиться в память, вы можете просто создать в памяти индекс смещений файлов, а затем отобразить в памяти файл для доступа к строкам (зависит от вашей ОС).

На месте потребуется много копий памяти. Если можете, используйте сортировку оболочки. Затем, как только вы узнаете окончательный порядок, гораздо проще изменить порядок строк за линейное время.

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

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

Answer 9

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

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

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

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

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