Как использовать 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 строки. Я просто вернул пустую строку.
Решение
В соответствии с документация:
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());
}
};
Другие решения
Наконец-то я нашел решение своей проблемы с огромной помощью Тимо Бингмана, пользователя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}
Если вы используете C ++ 11, то в качестве альтернативы классу FixedString вы можете использовать std::array<char, MAX_KEY_LEN>. Это слой STL поверх обычного массива C фиксированного размера, реализующий сравнения и итераторы, как вы привыкли использовать из std :: string, но это тип POD, поэтому STXXL должен это поддерживать.
Кроме того, вы можете использовать serialization_sort в TPIE. Может сортировать элементы типа std::pair<std::string, unsigned int> просто отлично, так что если все, что вам нужно, это вставить все навалом, а затем получить к нему доступ навалом, этого будет достаточно для вашего случая (и, вероятно, быстрее, в зависимости от конкретного случая).