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 类型的值，该值大于存储在 map 中的任何键

因为空字符串碰巧比任何其他字符串都小，它打破了这个先决条件，因此可能导致未指定的行为。

这是一个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 函数都需要覆盖所有的操作符 major((), ==, !=) 现在我们可以为 map 定义 fixed_name_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 回答