Наиболее эффективный способ для перебора слов в строке

Question

Если бы я хотел перебрать отдельные слова в строке (разделенных пробелами), то очевидное решение будет:

std::istringstream s(myString); 

std::string word; 
while (s >> word) 
    do things 

Однако это весьма неэффективно. Вся строка копируется при инициализации потока строк, а затем каждое извлеченное слово копируется по одному в переменную word (которая почти полностью копирует всю строку). Есть ли способ улучшить это без ручного повторения каждого символа?

Answer 1

В большинстве случаев копирование представляет собой очень небольшой процент от общих затрат, поэтому использование более чистого и высоко читаемого кода становится более важным. В редких случаях, когда профилировщик времени сообщает вам, что копирование создает узкое место, вы можете перебирать символы в строке с некоторой помощью из стандартной библиотеки.

Один подход, который вы могли бы сделать, это итерацию с std::string::find_first_of и std::string::find_first_not_of функций-членов, как это:

const std::string s = "quick \t\t brown \t fox jumps over the\nlazy dog"; 
const std::string ws = " \t\r\n"; 
std::size_t pos = 0; 
while (pos != s.size()) { 
    std::size_t from = s.find_first_not_of(ws, pos); 
    if (from == std::string::npos) { 
     break; 
    } 
    std::size_t to = s.find_first_of(ws, from+1); 
    if (to == std::string::npos) { 
     to = s.size(); 
    } 
    // If you want an individual word, copy it with substr. 
    // The code below simply prints it character-by-character: 
    std::cout << "'"; 
    for (std::size_t i = from ; i != to ; i++) { 
     std::cout << s[i]; 
    } 
    std::cout << "'" << std::endl; 
    pos = to; 
} 

Demo.

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

Answer 2

Как насчет срыва строки? Вы можете проверить это post для получения дополнительной информации.

В этом сообщении есть подробный ответ о том, как разделить строку в токенах. В этом ответе, возможно, вы могли бы проверить второй способ, используя итераторы и алгоритм копирования.

Answer 3

Используя boost string algorithms, мы можем написать его следующим образом. Цикл не требует никакого копирования строки.

#include <string> 
#include <iostream> 
#include <boost/algorithm/string.hpp> 

int main() 
{ 
    std::string s = "stack over flow"; 

    auto it = boost::make_split_iterator(s, boost::token_finder( 
          boost::is_any_of(" "), boost::algorithm::token_compress_on)); 
    decltype(it) end; 

    for(; it != end; ++it) 
    { 
     std::cout << "word: '" << *it << "'\n"; 
    } 

    return 0; 
} 

делает его C++ 11-иш

Поскольку пары итераторов так Oldschool в настоящее время, мы можем использовать boost.range определить некоторые общие вспомогательные функции. Они, наконец, позволяют нам петлю над словами с использованием диапазона для:

#include <string> 
#include <iostream> 
#include <boost/algorithm/string.hpp> 
#include <boost/range/iterator_range_core.hpp> 

template< typename Range > 
using SplitRange = boost::iterator_range< boost::split_iterator< typename Range::const_iterator > >; 

template< typename Range, typename Finder > 
SplitRange<Range> make_split_range(const Range& rng, const Finder& finder) 
{ 
    auto first = boost::make_split_iterator(rng, finder); 
    decltype(first) last; 
    return { first, last }; 
} 

template< typename Range, typename Predicate > 
SplitRange<Range> make_token_range(const Range& rng, const Predicate& pred) 
{ 
    return make_split_range(rng, boost::token_finder(pred, boost::algorithm::token_compress_on)); 
} 

int main() 
{ 
    std::string str = "stack \tover\r\n flow"; 

    for(const auto& substr : make_token_range(str, boost::is_any_of(" \t\r\n"))) 
    { 
     std::cout << "word: '" << substr << "'\n"; 
    } 

    return 0; 
} 

Демо:

http://coliru.stacked-crooked.com/a/2f4b3d34086cc6ec

Answer 4

Если вы хотите, чтобы он как можно быстрее, вы должны упасть назад к старой доброй функции C strtok() (или его поточно-компаньон strtok_r()):

const char* kWhiteSpace = " \t\v\n\r"; //whatever you call white space 

char* token = std::strtok(myString.data(), kWhiteSpace); 
while(token) { 
    //do things with token 
    token = std::strtok(nullptr, kWhiteSpace)); 
} 

Опасайтесь, что это скроет содержимое myString: оно работает, заменяя первый символ разделителя после каждого токена с завершающим нулевым байтом и возвращая указатель на начало токенов по очереди. В конце концов, это устаревшая функция C.

Однако эта слабость также является ее силой: она не выполняет никакой копии и не выделяет никакой динамической памяти (что, вероятно, является самым трудоемким в вашем примере кода).Таким образом, вы не найдете собственный метод C++, который будет превосходить скорость strtok().