W jaki sposób implementowany jest ciąg std :: string?

Question

Jestem ciekawa, w jaki sposób std :: string jest zaimplementowany i jak różni się od łańcucha c? Jeżeli standard nie określi żadnej implementacji, to jakakolwiek implementacja z wyjaśnieniem byłaby świetna w sposobie, w jaki spełnia on wymagania strunowe podane przez standard?

Answer 1

Praktycznie każdy użyty kompilator zawiera kod źródłowy dla środowiska wykonawczego - więc niezależnie od tego, czy używasz GCC, czy MSVC, czy cokolwiek, masz możliwość przyjrzenia się implementacji. Jednak duża część lub całość kodu std::string zostanie zaimplementowana jako kod szablonu, co może być bardzo trudne do odczytania.

Scott Meyer's book, Effective STL, ma rozdział na temat implementacji std :: string, który jest przyzwoitym przeglądem popularnych odmian: "Element 15: Bądź świadomy odmian implementacji string".

Opowiada o 4 wariantach:

• kilka wariacji na realizację ref liczone (powszechnie znany jako copy on write) - gdy obiekt ciąg jest kopiowany bez zmian, RefCount jest zwiększany, ale rzeczywisty ciąg dane nie są. Oba obiekty wskazują te same dane refcounted, aż jeden z obiektów je zmodyfikuje, powodując "kopię przy zapisie" danych. Odmiany są tam, gdzie przechowywane są takie rzeczy jak reflok, blokady itp.

• Implementacja "krótkiej optymalizacji łańcucha znaków" (SSO). W tym wariancie obiekt zawiera zwykły wskaźnik do danych, długości, rozmiaru dynamicznie przydzielanego bufora itp. Ale jeśli łańcuch jest wystarczająco krótki, użyje tego obszaru do przechowywania ciągu znaków zamiast dynamicznie przydzielać bufor

Ponadto, Herb Sutter's "More Exceptional C++" ma dodatek (Dodatek A: "Optymalizacje, które nie są (w świecie wielowątkowym)"), który omawia, dlaczego kopiowanie przy ponownym obliczaniu zapisu ma często problemy z wydajnością w aplikacjach wielowątkowych z powodu problemów z synchronizacją.Że artykuł jest również dostępny w Internecie (ale nie jestem pewien, czy to jest dokładnie to samo, co znajduje się w książce):

• http://www.gotw.ca/publications/optimizations.htm

Oba te rozdziały warto byłoby czytanie.

Answer 2

Istnieje przykładowa implementacja w an answer on this page.

Ponadto można przyjrzeć się implementacji gcc, zakładając, że zainstalowano gcc. If not, you can access their source code via SVN. Większość std :: string jest implementowana przez basic_string, więc zacznij tam.

Innym możliwym źródłem informacji jest Watcom's compiler

Answer 3

std :: string jest klasa, która owija się wokół jakiegoś wewnętrznego bufora i zapewnia sposoby manipulowania ten bufor.

ciąg w C jest tylko tablicą znaków

wyjaśniając wszystkie niuanse jak std :: string działa tutaj zajęłoby zbyt długo. Może zajrzyj do kodu źródłowego gcc http://gcc.gnu.org, aby zobaczyć dokładnie, jak to robią.

Answer 4

To zależy od standardowej biblioteki, której używasz.

STLPort na przykład jest implementacją biblioteki standardowej C++, która implementuje ciągi między innymi.

Answer 5

Rozwiązanie C++ dla łańcuchów różni się znacznie od wersji c. Pierwszą i najważniejszą różnicą jest to, że gdy c używa rozwiązania ASCIIZ, std :: string i std :: wstring używają dwóch iteratorów (wskaźników) do przechowywania rzeczywistego łańcucha. Podstawowe użycie klas ciągów zapewnia dynamiczne przydzielanie rozwiązań, więc w kosztach narzutu procesora z dynamiczną obsługą pamięci sprawia, że ​​obsługa ciągów jest bardziej wygodna.

Jak już zapewne wiesz, C nie zawiera wbudowanego generycznego typu łańcucha, udostępnia tylko kilka operacji na łańcuchach w standardowej bibliotece. Jedną z głównych różnic między C i C++, które C++ zapewnia zawijaną funkcjonalność, więc można go uznać za sfałszowany rodzajowy.

W C należy przejść przez ciąg, jeśli chcesz poznać jego długość, funkcja członkowska std :: string :: size() jest tylko jedną instrukcją (koniec - początek) w zasadzie. Możesz bezpiecznie dołączać łańcuchy do siebie tak długo, jak długo masz pamięć, więc nie musisz się martwić o błędy przepełnienia bufora (i dlatego exploity), ponieważ dołączanie tworzy większy bufor, jeśli jest potrzebny.

Jak już wcześniej powiedziano, ciąg jest pochodną funkcji wektorowej, w sposób szablonowy, dzięki czemu łatwiej radzić sobie z systemami o wielobajtowych znakach. Możesz zdefiniować swój własny typ ciągu używając typedef std :: basic_string specific_str_t; wyrażenie z dowolnym arbitralnym typem danych w parametrze szablonu.

myślę, istnieje wystarczająco dużo zalet i contras zarówno niepożądane:

C++ strunowe Plusy: - Szybsze iteracja w niektórych przypadkach (przy użyciu rozmiaru zdecydowanie, i nie potrzebuje danych z pamięci, aby sprawdzić, czy jesteś na końcu łańcucha, porównując dwa wskaźniki, które mogą zrobić różnicę z buforowaniem). Operacja bufora jest zapakowana w funkcje ciągów, więc mniej martwisz się o problemy z buforem.

Ciągi w językach C++: - ze względu na dynamiczne przydzielanie pamięci rzeczy podstawowe użycie może wpłynąć na wydajność. (na szczęście możesz powiedzieć obiektowi typu string, jaki powinien być oryginalny rozmiar bufora, więc jeśli go nie przekroczysz, nie przydzieli on dynamicznych bloków z pamięci) - często dziwne i niespójne nazwy w porównaniu do innych języków. jest to zła rzecz w każdym stl, ale można z niej korzystać, i robi to trochę specyficzne uczucie C++. - intensywne korzystanie z szablonów wymusza na standardowej bibliotece używanie rozwiązań opartych na nagłówkach, co ma duży wpływ na czas kompilacji.