C++ Каков наилучший способ чтения словаря из текстового файла и его хранения в отсортированном контейнере

Question

Каков наилучший способ чтения словаря из текстового файла и его хранения в сортированном контейнере. У меня проблема с производительностью при вставке слов в контейнер. Итак, вот мой код.

std::set<std::string> m_words; 
std::stringstream ss(textStr); 
std::string buf; 
while (ss >> buf) 
{ 
    m_words.insert(m_words.end(), buf); 
} 

Файл словаря - это английский словарь с 130000 строк. Есть ли что-то еще для оптимизации производительности.

Answer 1

Моя догадки использовать vector, потому что прилегающая хранения хорошая производительности, резервировать ожидаемое количество записей заранее, воспользоваться ходом семантики и сортировать вектор в конце только файл:

std::vector<std::string> m_words; 
m_words.reserve(10000); 

std::string buf; 
while (ss >> buf) 
{ 
    m_words.push_back(std::move(buf)); 
    buf.clear(); 
} 

std::sort(m_words.begin(), m_words.end()); 

(Вы также можете проверить размер файла на фазе предварительной обработки, чтобы получить лучший подсказку вместо фиксированного)

Из-за перемещения, buf должен быть сброшен в пустое состояние.

Если не указано иное, все стандартные функции библиотеки, которые принимают эталонные Rvalue параметры (такие как станд :: вектор :: push_back) являются гарантированно оставить перемещенный-от аргумента в действительной, но неустановленный состоянии. То есть, только функция без предварительных условий, таких как оператор в назначении, может быть использован на объекте после того, как он был перемещен в стандартной библиотеке контейнер (cppreference)

Answer 2

Вместо добавления отсортированных значений в станд: : set, вы можете нажимать строки на std :: vector или std :: deque (Примечание: не используйте std :: deque из msvc (2013) - это не лучше, чем std :: list).

STD :: set должен иметь хорошую производительность, обнаруживая правильную точку вставки, если он соблюдает подсказку «в конце». Однако std :: set выделяет узлы для каждого элемента отдельно.

Имея последовательность данных, вы можете выполнить бинарный поиск (std :: lower_bound) по этим данным.

Смотрите также:

• Двоичное: Where can I get a "useful" C++ binary search algorithm?
• MSVC Deque: profiling: deque is 23% of my runtime

Примечание: Имея C++ 11 можно считать вектор :: резерв (huge_amount) и вектор :: shrink_to fit()