char *の配列をソートする簡単な方法はありますか？ C ++

https://stackoverflow.com/questions/314492

10-07-2019
|

質問

ファイルに char * の配列があります。私が働いている会社は、データをフラットファイルに保存しています。データがソートされることもあれば、ソートされないこともあります。ファイル内のデータをソートしたい。

これを行うためのコードを最初から作成できました。もっと簡単な方法はありますか？

もちろん、インプレースソートが最適なオプションです。私は大きなファイルで作業していて、RAMがほとんどありません。しかし、私はすべてのオプションを検討します。

すべての文字列は同じ長さです。

これはサンプルデータです：

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

これは、長さ28の3つのレコードを表します。アプリは長さを認識しています。各レコードはCRLF（ \ r \ n ）で終了しますが、このソートには関係ありません。

解決

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

他のヒント

データをRAMに適合できない場合は、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);

おそらく最も簡単な方法は、古いstdlib.h関数qsortを使用することです。これは動作するはずです：

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

これは標準Cであり、英語のテキストでのみ信頼性の高い動作をすることに注意してください。

Stringオブジェクトのリストがある場合、C ++では他のことが可能です。

LinuxでgtkまたはQtアプリケーションを作成している場合は、これらのライブラリを事前に確認することをお勧めします。

ファイルが大きく、RAMに収まらない場合は、 bin / bucket ソートしてデータを小さなファイルに分割し、最終的に断片を結果ファイルに集約します。他の応答は、個々のバケットファイルをソートする方法を示しています。

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...
}

いくつかのことが思い浮かびます：

データが大きすぎてメモリに収まらない場合は、メモリ内にファイルオフセットのインデックスを作成し、ファイルをメモリマッピングして文字列にアクセスします（OSによって異なります）。
インプレースでは、メモリコピーの多くが必要になります。可能であれば、シェルソートを使用します。その後、最終的な順序がわかれば、線形時間でその場で文字列を並べ替えることがはるかに簡単になります。
文字列がすべて同じ長さの場合、基数ソートが本当に必要です。基数ソートに慣れていない場合の基本的な考え方は次のとおりです。比較ベースのソート（ std :: sort 、 qsort 、およびその他の一般的なソート目的のソート）は常にO（N log N）時間を必要とします。基数の並べ替えでは、一度に1桁（ str [0] で始まり、 str [K-1] で終わり、K桁の文字列）が比較されます。実行に必要な時間はO（N）だけです。

基数ソートアルゴリズムの詳細な説明については、私が提供できるよりもインターネットを参照してください。私が言ったこととは別に、標準的なライブラリーの並べ替え機能を使用する他のソリューションはすべて避けます。残念ながら、彼らはあなたの特定の問題を設計していません。

メモリマップファイルを調べたいと思うでしょう（ http：//en.wikipediaをご覧ください。 org / wiki / Memory-mapped_file ）、mmap（）関数（ http：// en。 wikipedia.org/wiki/Mmap ）POSIX準拠OSで。基本的に、ファイルの内容を表す連続したメモリへのポインタを取得します。

良い面は、OSがファイルの一部をメモリにロードし、必要に応じて再びアンロードすることです。

欠点は、複数のプロセスがファイルにアクセスする可能性が高い場合、破損を避けるために何らかの形式のファイルロックに解決する必要があることです。

もう1つの欠点は、これが良好なパフォーマンスを保証しないことです-それを行うには、常にページのロードとアンロードを回避しようとするソートアルゴリズムが必要です（もちろん、ファイル全体をメモリにロードするのに十分なメモリがない限り））。

これでアイデアが得られたことを願っています！

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow