Как использовать std::string в качестве ключа в stxxl::map

Я пытаюсь использовать 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 строки. Я просто вернул пустую строку.

Источник

3 ответа

Решение

Наконец-то я нашел решение своей проблемы с огромной помощью Тимо Бингмана, пользователя2079303 и Мартина Ба. Спасибо.

Я хотел бы поделиться этим с вами.

Во-первых, 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. Теперь мы можем определить fixed_name_map для 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 строк. Также мы можем использовать myFixedMap как std:: map. {например: myFixedMap[fixedString] = 10}

Источник

Согласно документации:

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());
    }
};
Источник

Если вы используете C++11, то в качестве альтернативы классу FixedString вы можете использовать std::array<char, MAX_KEY_LEN>, Это слой STL поверх обычного массива C фиксированного размера, реализующий сравнения и итераторы, как вы привыкли делать из std::string, но это тип POD, поэтому STXXL должен его поддерживать.

Кроме того, вы можете использовать serialization_sort в TPIE. Может сортировать элементы типа std::pair<std::string, unsigned int> просто отлично, так что если все, что вам нужно, это вставить все навалом, а затем получить к нему доступ навалом, этого будет достаточно для вашего случая (и, вероятно, быстрее, в зависимости от конкретного случая).

Источник
Другие вопросы по тегам