effizienteste Weg, um Worte in einem String zu iterieren

Question

Wenn ich einzelne Wörter iterieren in einem String gesucht (durch Leerzeichen getrennt), dann ist die offensichtliche Lösung wäre:

std::istringstream s(myString); 

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

jedoch, dass ziemlich ineffizient ist. Der gesamte String wird kopiert, während der String-Stream initialisiert wird, und dann wird jedes extrahierte Wort nacheinander in die Variable word kopiert (was nahe daran liegt, den gesamten String ein zweites Mal zu kopieren). Gibt es eine Möglichkeit, dies zu verbessern, ohne jedes Zeichen manuell durchlaufen zu müssen?

Answer 1

In den meisten Fällen stellt das Kopieren einen sehr kleinen Prozentsatz der Gesamtkosten dar, daher wird es wichtiger, einen sauberen, gut lesbaren Code zu haben. In seltenen Fällen, wenn der Zeitprofiler Ihnen mitteilt, dass das Kopieren einen Engpass verursacht, können Sie mit Hilfe der Standardbibliothek über Zeichen in der Zeichenfolge iterieren.

Ein Ansatz, die Sie ergreifen können, ist mit std::string::find_first_of und std::string::find_first_not_of Mitgliederfunktionen iterieren, wie folgt aus:

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.

Leider ist der Code sehr viel schwieriger zu lesen wird, so dass Sie vermeiden sollten diese Änderung, oder zumindest verschieben, bis es erforderlich wird.

Answer 2

Wie wäre es, die Zeichenfolge aufzuspalten? Sie können dies überprüfen post für weitere Informationen.

In diesem Beitrag gibt es eine detaillierte Antwort darüber, wie Sie eine Zeichenfolge in Token teilen. In dieser Antwort könnten Sie vielleicht den zweiten Weg mit Iteratoren und dem Kopieralgorithmus überprüfen.

Answer 3

Mit boost string algorithms können wir es wie folgt schreiben. Die Schleife enthält kein Kopieren der Zeichenfolge.

#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; 
} 

Making it C++ 11-ish

Da Paare von Iteratoren heutzutage so oldschool sind wir boost.range verwenden können einige allgemeine Hilfsfunktionen zu definieren. Diese schließlich ermöglichen es uns, eine Schleife über den Wörtern mit Entfernungs-für:

#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; 
} 

Demo:

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

Answer 4

Wenn Sie es haben, so schnell wie möglich, Sie müssen zurück fallen auf die gute alte C-Funktion strtok() (oder deren Thread-sichere Begleiter 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)); 
} 

Beachten Sie, dass dies den Inhalt von myString verfälscht: Es funktioniert, indem das erste Trennzeichen nach jedem Token durch ein abschließendes Nullbyte ersetzt wird und ein Zeiger auf den Start der Token zurückgegeben wird. Dies ist eine Legacy-C-Funktion.

Diese Schwäche ist aber auch ihre Stärke: Sie führt weder eine Kopie durch, noch weist sie einen dynamischen Speicher zu (was wahrscheinlich am zeitaufwendigsten in Ihrem Beispielcode ist).Daher werden Sie keine systemeigene C++ - Methode finden, die die Geschwindigkeit strtok() übertrifft.