1

std::string を stxxl::map のキーとして使用しようとしています。10 ～ 100 程度の少数の文字列の場合、挿入は問題ありませんでした。しかし、そこに約100000の多数の文字列を挿入しようとすると、セグメンテーション違反が発生します。

コードは次のとおりです。

struct CompareGreaterString {
    bool operator () (const std::string& a, const std::string& b) const {
       return a > b;
    }
    static std::string max_value() {
       return "";
    } 
};

// template parameter <KeyType, DataType, CompareType, RawNodeSize, RawLeafSize, PDAllocStrategy (optional)>
typedef stxxl::map<std::string, unsigned int, CompareGreaterString, DATA_NODE_BLOCK_SIZE, DATA_LEAF_BLOCK_SIZE> name_map;
name_map strMap((name_map::node_block_type::raw_size)*3, (name_map::leaf_block_type::raw_size)*3);
for (unsigned int i = 0; i < 1000000; i++) { /// Inserting 1 million strings
    std::stringstream strStream;
    strStream << (i);
    Console::println("Inserting: " + strStream.str());
    strMap[strStream.str()]=i;
}

ここでは、より多くの文字列を挿入できない理由を特定できません。「1377」を挿入すると、正確にセグメンテーション違反が発生します。さらに、任意の数の整数をキーとして追加できます。文字列の可変サイズがこの問題を引き起こしているのではないかと思います。

また、文字列の何を返すのか理解できませんmax_value。単純に空の文字列を返しました。

4

3 に答える 3

3

ドキュメントによると：

CompareType は、静的な max_value メソッドも提供する必要があります。このメソッドは、マップに格納されているどのキーよりも大きい KeyType 型の値を返します。

空の文字列はたまたま他の文字列よりも小さいと比較されるため、この前提条件が破られ、予期しない動作が発生する可能性があります。

これがうまくmax_valueいくはずです。MAX_KEY_LENマップが持つことができる最長の文字列キーの長さ以上の整数です。

struct CompareGreaterString {
    // ...
    static std::string max_value() {
        return std::string(MAX_KEY_LEN, std::numeric_limits<unsigned char>::max());
    }
};
于 2014-04-17T13:46:07.510 に答える
1

Timo bingmann、user2079303、Martin Ba の多大な助けを借りて、私の問題の解決策をついに見つけました。ありがとうございました。

あなたとそれを共有したいと思います。

まず、stxxl は POD のみをサポートします。つまり、固定サイズの構造のみを格納します。したがって、std::string をキーにすることはできません。stxxl::map は、物理メモリ自体に含まれていたため、約 100 ～ 1000 個の文字列に対して機能しました。さらに文字列が挿入されると、ディスクに書き込む必要があり、内部的に問題が発生します。

したがって、次のように char[] を使用して固定文字列を使用する必要があります。

static const int MAX_KEY_LEN = 16;

class FixedString { 
public:
    char charStr[MAX_KEY_LEN];

    bool operator< (const FixedString& fixedString) const {
        return std::lexicographical_compare(charStr, charStr+MAX_KEY_LEN,
            fixedString.charStr, fixedString.charStr+MAX_KEY_LEN);
    }

    bool operator==(const FixedString& fixedString) const {
        return std::equal(charStr, charStr+MAX_KEY_LEN, fixedString.charStr);
    }

    bool operator!=(const FixedString& fixedString) const {
        return !std::equal(charStr, charStr+MAX_KEY_LEN, fixedString.charStr);
    } 
};

struct comp_type : public std::less<FixedString> {
    static FixedString max_value()
    {
        FixedString s;
        std::fill(s.charStr, s.charStr+MAX_KEY_LEN, 0x7f);
        return s;
    } 
};

すべての stxxl::map 関数を機能させるには、主にすべての演算子 (()、==、!=) をオーバーライドする必要があることに注意してください。

typedef stxxl::map<FixedString, unsigned int, comp_type, DATA_NODE_BLOCK_SIZE, DATA_LEAF_BLOCK_SIZE> fixed_name_map;
fixed_name_map myFixedMap((fixed_name_map::node_block_type::raw_size)*5, (fixed_name_map::leaf_block_type::raw_size)*5);

現在、プログラムは正常にコンパイルされており、約 10^8 文字列を問題なく受け入れています。また、std::map 自体のように myFixedMap を使用することもできます。{例: myFixedMap[fixedString] = 10}

于 2014-04-20T11:44:28.970 に答える
1

C++11 を使用している場合は、FixedString クラスの代わりにstd::array<char, MAX_KEY_LEN>. 通常の固定サイズの C 配列の上にある STL レイヤーであり、std::string から慣れ親しんだ比較と反復子を実装しますが、これは POD 型であるため、STXXL はそれをサポートする必要があります。

または、 TPIEで serialization_sort を使用できます。タイプの要素をうまく並べ替えることができるstd::pair<std::string, unsigned int>ので、すべてをまとめて挿入してからまとめてアクセスするだけであれば、これで十分です (正確なケースによってはおそらくより高速です)。

于 2014-07-13T16:28:33.433 に答える