Słyszałem, jak kilka osób martwiło się operatorem „+” w std :: string i różnymi obejściami, aby przyspieszyć konkatenację. Czy któreś z nich są naprawdę potrzebne? Jeśli tak, jaki jest najlepszy sposób łączenia ciągów w C ++?

Dodatkowa praca prawdopodobnie nie jest tego warta, chyba że naprawdę potrzebujesz wydajności. Prawdopodobnie uzyskasz znacznie lepszą wydajność, używając zamiast tego operatora + =.

Teraz, po tym zrzeczeniu się, odpowiem na twoje rzeczywiste pytanie ...

Wydajność klasy ciągu STL zależy od implementacji używanego pliku STL.

Możesz zagwarantować wydajność i mieć większą kontrolę , wykonując konkatenację ręcznie za pomocą wbudowanych funkcji c.

Dlaczego operator + nie jest wydajny:

Spójrz na ten interfejs:

template <class charT, class traits, class Alloc>
basic_string<charT, traits, Alloc>
operator+(const basic_string<charT, traits, Alloc>& s1,
          const basic_string<charT, traits, Alloc>& s2)

Możesz zobaczyć, że nowy obiekt jest zwracany po każdym +. Oznacza to, że za każdym razem używany jest nowy bufor. Jeśli wykonujesz mnóstwo dodatkowych + operacji, nie jest to wydajne.

Dlaczego możesz uczynić to bardziej wydajnym:

• Gwarantujesz efektywność, zamiast ufać delegatowi, że zrobi to skutecznie za Ciebie
• klasa std :: string nie wie nic o maksymalnym rozmiarze twojego łańcucha ani o tym, jak często będziesz z nim łączyć. Możesz mieć tę wiedzę i możesz robić rzeczy w oparciu o te informacje. Doprowadzi to do mniejszej liczby realokacji.
• Będziesz kontrolować bufory ręcznie, więc możesz być pewien, że nie skopiujesz całego ciągu do nowych buforów, jeśli nie chcesz, aby tak się stało.
• Możesz użyć stosu dla swoich buforów zamiast stosu, co jest znacznie bardziej wydajne.
• Operator string + utworzy nowy obiekt typu string i zwróci go, używając nowego bufora.

Uwagi dotyczące wdrożenia:

• Śledź długość struny.
• Zachowaj wskaźnik do końca łańcucha i początku lub tylko początku i użyj początku + długości jako przesunięcia, aby znaleźć koniec łańcucha.
• Upewnij się, że bufor, w którym przechowujesz łańcuch, jest wystarczająco duży, aby nie trzeba było ponownie przydzielać danych
• Użyj strcpy zamiast strcat, aby nie trzeba było iterować po długości ciągu, aby znaleźć jego koniec.

Struktura danych liny:

Jeśli potrzebujesz naprawdę szybkich konkatenacji, rozważ użycie struktury danych liny .

Zarezerwuj ostatnie miejsce wcześniej, a następnie użyj metody dołączania z buforem. Załóżmy na przykład, że oczekujesz, że ostateczna długość ciągu będzie wynosić 1 milion znaków:

std::string s;
s.reserve(1000000);

while (whatever)
{
  s.append(buf,len);
}

Nie martwiłbym się tym. Jeśli zrobisz to w pętli, łańcuchy zawsze będą wstępnie alokować pamięć, aby zminimalizować realokacje - po prostu użyj operator+=w takim przypadku. A jeśli robisz to ręcznie, coś takiego lub dłużej

a + " : " + c

Następnie tworzy tymczasowe - nawet jeśli kompilator mógłby wyeliminować niektóre kopie zwracanej wartości. Dzieje się tak, ponieważ w wywoływanym sukcesywnie operator+nie wie, czy parametr referencyjny odwołuje się do nazwanego obiektu, czy tymczasowo zwracany z operator+wywołania podrzędnego . Wolałbym się tym nie przejmować, zanim nie wykonam profilowania. Ale weźmy przykład, aby to pokazać. Najpierw wprowadzamy nawiasy, aby powiązanie było jasne. Umieszczam argumenty bezpośrednio po deklaracji funkcji, która jest używana dla przejrzystości. Poniżej pokazuję, jakie jest otrzymane wyrażenie:

((a + " : ") + c) 
calls string operator+(string const&, char const*)(a, " : ")
  => (tmp1 + c)

Teraz w tym dodatku tmp1jest to , co zostało zwrócone przez pierwsze wywołanie operatora + z przedstawionymi argumentami. Zakładamy, że kompilator jest naprawdę sprytny i optymalizuje kopię zwracanej wartości. W efekcie otrzymujemy jeden nowy ciąg zawierający konkatenację ai " : ". Teraz dzieje się tak:

(tmp1 + c)
calls string operator+(string const&, string const&)(tmp1, c)
  => tmp2 == <end result>

Porównaj to z następującymi:

std::string f = "hello";
(f + c)
calls string operator+(string const&, string const&)(f, c)
  => tmp1 == <end result>

Używa tej samej funkcji dla tymczasowego i nazwanego ciągu! Dlatego kompilator musi skopiować argument do nowego ciągu, dołączyć do niego i zwrócić go z treści operator+. Nie może wziąć wspomnienia czegoś tymczasowego i dołączyć do tego. Im większe wyrażenie, tym więcej kopii ciągów musi być zrobionych.

Kolejne programy Visual Studio i GCC będą obsługiwać semantykę przenoszenia języka c ++ 1x (uzupełniającą semantykę kopiowania ) i odwołania do wartości rvalue jako dodatek eksperymentalny. To pozwala ustalić, czy parametr odnosi się do tymczasowego, czy nie. To sprawi, że takie dodatki będą zadziwiająco szybkie, ponieważ wszystko powyżej skończy się w jednym „potoku dodawania” bez kopii.

Jeśli okaże się, że jest to wąskie gardło, nadal możesz to zrobić

 std::string(a).append(" : ").append(c) ...

Do appendrozmowy dołączy argument *this, a następnie powrót odniesienie do siebie. Dlatego nie jest tam kopiowanie tymczasowych. Alternatywnie operator+=można użyć znaku, ale do ustalenia pierwszeństwa potrzebny byłby brzydki nawias.

W przypadku większości zastosowań to po prostu nie ma znaczenia. Po prostu napisz swój kod, błogo nieświadomy tego, jak dokładnie działa operator + i weź sprawy w swoje ręce tylko wtedy, gdy stanie się to pozornym wąskim gardłem.

W przeciwieństwie do .NET System.Strings, std :: strings w języku C ++ są modyfikowalne i dlatego można je budować za pomocą prostej konkatenacji tak samo szybko, jak za pomocą innych metod.

może zamiast tego std :: stringstream?

Ale zgadzam się z opinią, że prawdopodobnie powinieneś po prostu zachować to w utrzymaniu i zrozumiałe, a następnie profil, aby zobaczyć, czy naprawdę masz problemy.

W Imperfect C ++ Matthew Wilson przedstawia dynamiczny konkatenator ciągów, który wstępnie oblicza długość końcowego ciągu, aby mieć tylko jedną alokację przed połączeniem wszystkich części. Możemy również zaimplementować statyczny konkatenator, grając z szablonami wyrażeń .

Ten rodzaj pomysłu został zaimplementowany w implementacji STLport std :: string - który nie jest zgodny ze standardem z powodu tego precyzyjnego hacka.

std::string operator+przydziela nowy łańcuch i za każdym razem kopiuje dwa łańcuchy operandów. powtarzać wiele razy i robi się drogie, O (n).

std::string appenda operator+=z drugiej strony, wpadać zdolności o 50% za każdym razem łańcuch musi rosnąć. Co znacznie zmniejsza liczbę alokacji pamięci i operacji kopiowania, O (log n).

W przypadku małych strun to nie ma znaczenia. Jeśli masz duże ciągi, lepiej przechowuj je w postaci w wektorze lub w innej kolekcji jako części. I dostosuj swój algorytm do pracy z takim zestawem danych zamiast z jednym dużym ciągiem.

Preferuję std :: ostringstream do złożonych konkatenacji.

Jak w przypadku większości rzeczy, łatwiej jest czegoś nie robić, niż to robić.

Jeśli chcesz wyprowadzić duże ciągi do GUI, może się zdarzyć, że cokolwiek wyprowadzasz, może obsługiwać ciągi w kawałkach lepiej niż jako duży ciąg (na przykład łączenie tekstu w edytorze tekstu - zwykle zachowują wiersze jako oddzielne Struktury).

Jeśli chcesz wyprowadzić dane do pliku, przesyłaj dane strumieniowo zamiast tworzenia dużego ciągu i wyprowadzania go.

Nigdy nie uważałem, że konieczne jest przyspieszenie konkatenacji, jeśli usunąłem niepotrzebną konkatenację z wolnego kodu.

Prawdopodobnie najlepsza wydajność, jeśli wstępnie przydzielisz (zarezerwujesz) miejsce w wynikowym ciągu.

template<typename... Args>
std::string concat(Args const&... args)
{
    size_t len = 0;
    for (auto s : {args...})  len += strlen(s);

    std::string result;
    result.reserve(len);    // <--- preallocate result
    for (auto s : {args...})  result += s;
    return result;
}

Stosowanie:

std::string merged = concat("This ", "is ", "a ", "test!");

Najszybsza jest prosta tablica znaków zamknięta w klasie, która śledzi rozmiar tablicy i liczbę przydzielonych bajtów.

Sztuczka polega na tym, aby na początku zrobić tylko jedną dużą alokację.

w

https://github.com/pedro-vicente/table-string

Benchmarki

W przypadku programu Visual Studio 2015, kompilacja debugowania x86, znaczna poprawa w stosunku do C ++ std :: string.

| API                   | Seconds           
| ----------------------|----| 
| SDS                   | 19 |  
| std::string           | 11 |  
| std::string (reserve) | 9  |  
| table_str_t           | 1  |  

Możesz wypróbować ten z rezerwacjami pamięci dla każdego elementu:

namespace {
template<class C>
constexpr auto size(const C& c) -> decltype(c.size()) {
  return static_cast<std::size_t>(c.size());
}

constexpr std::size_t size(const char* string) {
  std::size_t size = 0;
  while (*(string + size) != '\0') {
    ++size;
  }
  return size;
}

template<class T, std::size_t N>
constexpr std::size_t size(const T (&)[N]) noexcept {
  return N;
}
}

template<typename... Args>
std::string concatStrings(Args&&... args) {
  auto s = (size(args) + ...);
  std::string result;
  result.reserve(s);
  return (result.append(std::forward<Args>(args)), ...);
}