C++ bez cholesterolu

Napisy

Wprowadzenie

Może się na początku trochę porozczulam. Fakt, że przez długi czas jakoś nie pomyślałem o napisaniu jakiejś dłuższej dokumentacji do stringa, który rozwiązuje dość sporą liczbę cokolwiek przecież banalnych problemów, częstych w języku C. To może tyle rozczulania się, bo na pewno są jakieś pytania.

Typ std::string bardzo ułatwia pracę ze wszelakiego rodzaju napisami, co jest w wielu językach rzeczą całkowicie "normalną". Nie będę się tu jednak skupiać na szczegółach dotyczących jego wewnętrznej budowy (takich jak opisane w STL-u alokatory i reguły cechowania [ang. traits]). Od strony STL większość jest opisana właśnie tam, natomiast tutaj skupię się już na elementach charakterystycznych dla samego stringa. I to nawet bez wnikania w szczegóły np. tego, że istnieje wzorzec std::basic_string, który dopiero po skonkretyzowaniu typem char (plus standardowym cechowaniem - std::char_traits - dla char i standardowym alokatorem) staje się dopiero typem std::string. Ani tego całego cechowania znaków. Po prostu są to rzadko używane przez większość programistów elementy, zatem jeśli komuś bardzo zależy na ich poznaniu, zawsze może zajrzeć do dokumentacji.

Tablica znaków a std::string

Z jednej strony, napis jest tablicą znaków. Ale z drugiej strony, użytkownik chciałby operować na tym napisie jak na konkretnej wartości i nie martwić się o kwestie pamięci. Cały myk polega na tym, że tablica znaków to jest implementacja napisu i nic więcej. Użytkownik zaś potrzebuje jakiegoś sensownego interfejsu, żeby móc tym czymś sensownie operować.

Interfejs napisu różni się zresztą od nawet wysokopoziomowych tablic (takich jak std::vector). Po części wynika to z naleciałości historycznych, a po części również z bardzo szczególnego znaczenia napisów. Napis zatem nie jest takim sobie tylko zbiornikiem znaków - jest po prostu... napisem :)

Z tablicą jest jednak jeden problem, przynajmniej w C: muszą się na nią zawsze składać dwie rzeczy: początek tablicy oraz ilość jej elementów. Głównie dlatego, że w C przekazać tablicę można tylko przez wskaźnik. Byłoby nieporęcznie za każdym razem przekazywać i wskaźnik i rozmiar (aczkolwiek z tym rozmiarem to jest wiecznie problem w C, przy tablicach przekazuje się go albo jawnie, albo się zakłada z góry jakiś rozmiar, albo liczy się naiwnie na to, że ten rozmiar nie zostanie przekroczony, jak w funkcji gets()). Dlatego w C napis, który się implementuje za pomocą tablicy znaków to jest tzw. NTS (null-terminated string), czyli zawsze się w nim znajduje znak terminujący o wartości zero.

Implementacja ta ma tylko i dokładnie jedną zaletę: napisem takim można operować za pomocą wskaźnika (co jest jedynym możliwym sposobem operowania takim typem danej w języku C). Stąd dla większości programistów C "const char*" (czy nawet "char*") znaczy to samo, co "string". Poza tą zaletą, pozostałe cechy należą do wad; między innymi jest to liniowy czas mierzenia długości stringa (funkcja strlen, złożoność liniowa w długość napisu, zresztą jeszcze lepszy numer jest z strcat: złożoność liniowa, ale nie w długość kopiowanego napisu, tylko w sume tej wartości z długością stringa już znajdującego się w docelowej tablicy) oraz niebezpieczeństwo związane z niewłaściwie umieszczonym znakiem terminującym (nadpisanie tego znaku lub jego przypadkowe nieumieszczenie powoduje, że w przypadku takiego np. kopiowania znaki czytane są dalej i czytana jest po prostu dalsza część pamięci, być może aż do wyjechania poza swój segment). Ogólnie, NTS jest powolny i ma dziury związane z bezpieczeństwem. W związku z tym std::string nie jest bynajmniej tylko "ułatwiaczem" dla użytkownika; jest od NTS-a po prostu lepszy pod każdym względem (wyjątek może stanowić krótki lokalny bufor, ale w praktyce zysk jest i tak niewielki, a niebezpieczeństwo spore).

Ponieważ jednak mnóstwo części istniejącego kodu operuje NTS-ami (głównie dlatego, że są pisane na użytek języka C), std::string może się konwertować na NTS za pomocą metody c_str():

string s;
...
const char* t = s.c_str();

W ten (I TYLKO W TEN) sposób tablica zostanie zaterminowana zerem. Takoż oczywiście wstawienie zera w środku niczego w stringu nie zmienia - string ma wciąż tą samą długość, a ów znak zerowy jest takim samym znakiem, jak każdy inny. Jedyne, co to może zmienić, to rezultat wywołania c_str().

Budowa teoretyczna typu std::string

Teoretycznie rzecz biorąc, string to jest wciąż tablica znaków, tyle że z sensownym interfejsem. Ów string zatem - podobnie jak std::vector - może się sam rozrastać, skracać, następuje również kopiowanie z przydziałem pamięci (wedle wskazanego alokatora). Jest to więc wysokopoziomowa tablica, tzn. o dynamicznie przydzielanej pamięci, z zapasem oraz pamiętanym rozmiarem. Dzięki temu metoda size() (jej historycznym synonimem jest length()) jest zawsze stałego czasu.

Implementacja SGI (przynajmniej jak widziałem to ostatnio) jest właściwie identyczna z wektorem. Tak samo, jak tam, istnieją trzy pola: początek tablicy, koniec aktualnie wykorzystanej tablicy i koniec zużytej pamięci (różnica tych dwóch ostatnich jest tzw. zapasem). Nie jest to dla stringa najlepsza implementacja, zwłaszcza że - jak wspomniałem - string ma wiele szczególności, z których warto skorzystać.

W lepszych implementacjach stosuje się współdzielenie wewnętrznej tablicy między obiektami stringa oraz tzw. "copy-on-write". Polega to na tym, że w całej przydzielonej pamięci wykraja się część na potrzeby wewnętrznej struktury. Wskaźnik do tej pamięci (przesunięty oczywiście o wielkość tej struktury) jest jedynym polem struktury basic_string. Dzięki temu dostęp do najważniejszych rzeczy - czyli samych znaków - jest bardzo szybki. Natomiast te ukryte pola (tzw. reprezentacja) zawierają elementy charakterystyczne, czyli długość stringa, zapas i oczywiście licznik referencji. Zatem kopiowanie jednego stringa do drugiego w efekcie jedynie zwiększa licznik referencji. Dopiero w przypadku wykonania zapisu do tego stringa jeśli string nie jest właścicielem absolutnym do tej wewnętrznej tablicy, wykonuje się kopiowanie.

Wypełnianie

String do nadawania nowych wartości posiada przede wszystkim konstruktory oraz metody assign(). Metody assign() implementują wszystko, co jest związane z przypisywaniem (choć posiadają również postacie niemożliwe do zapisania za pomocą operatora przypisania), czyli kopiowanie z innego string'a (również częściowe), kopiowanie z const char* (NTS), const char* oraz długości (czyli jako zwykła tablica znaków) oraz wypełnianie jedną wartością znaku. Razem mamy następujące assign:

I tu zwracam uwagę i to bardzo szczególną na jedną rzecz: ostatnia postać assign jest bardzo niebezpieczna. Całe niebezpieczeństwo tkwi tu w fakcie, że jeśli podamy do tego wywołania argumenty w złej kolejności, to nikt nie będzie w stanie tego wykryć. Po prostu nie ma takiej możliwości; size_t może się na char konwertować bez żadnego miauknięcia (i vice versa). Oczywiście swego czasu znalazłem na to sposób (należy zdefiniować sobie wzorzec takiej metody i dodać implementację dla kolejności "size_t,char", a w implementacji holomorficznej zrobić po prostu coś, co się nie skompiluje), ale to wymagało niestety przeróbek w standardowym pliku nagłówkowym. Dodatkowo problem ten dotyczy nie tylko metody assign, ale wszystkich funkcji, które w ten sposób określają źródłowy ciąg znaków.

Podle bowiem tych powyższych deklaracji zmontowane są również konstruktory, a dla jednoargumentowych postaci z powyższej listy również operatory przypisania. Dodatkowo istnieje jeszcze jeden konstruktor, a dokładnie wzorzec konstruktora, który zawiera dwa argumenty dowolnego (byle takiego samego) typu. Teoretycznie mają one być iteratorami wyznaczającymi zakres znaków, z jakich ma być skonstruowany napis.

Wstawianie i sklejanie

Metody, które za te operacje odpowiadają, mają sygnatury podobne do przedstawionych wyżej assign. Są to: insert (wstawia dany ciąg na podanej pozycji) oraz append (dokłada napis na koniec). Metody insert() mają jeszcze w stosunku do assign() na początku jeden argument - pozycję, na której ma nastąpić wstawienie. Na przykład:

Do podobnych celów służą operatory + i +=. Operator += jest – jak się można domyślać – inną postacią append() z jednym argumentem. Natomiast operator + zwraca sklejony z dwóch string jako obiekt tymczasowy (którymkolwiek z argumentów może być NTS).

Indeksowanie, wyszukiwanie, pod-napisy

Indeksowanie napisu ma bardziej istotne znaczenie, niż indeksowanie np. wektora. Poza operatorem [] i metodą at() (o znaczeniu identycznym, jak w przypadku wektora), indeks jest używany przede wszystkim do wskazywania miejsc wewnątrz stringa, do których ma następować odwołanie. Na przykład pierwszy argument metod insert(), opisanych powyżej.

W przypadku stringa, indeks jest używany we wszystkich operacjach, które wymagają podania pozycji. Niektóre operacje, jak np. wyszukiwanie, zwracają ten indeks. Wyszukiwanie oczywiście może się nie powieść i w takim przypadku zwracana jest specjalna wartość (statyczna), string::npos.

Do wyszukiwania konkretnego elementu (znaku lub ciągu znaków) służą metody find:

Wyszukiwanie może być też do tyłu i wtedy należy użyć metody rfind.

Następujące metody mają podobny zestaw sygnatur, więc podam tylko nazwy. Te poniższe, w szczególności, dokonują wyszukiwania na bazie POJEDYNCZYCH znaków znajdujących się w podanym jako argument ciągu znaków (przez string lub NTS). To oznacza, że string traktowany jest praktycznie jak zwykły zbiornik ze znakami, a nie jako napis. Argument ten będzie tu nazwany "ciągiem".

find_first_of - znajduje w napisie pierwszy znak równy któremukolwiek ze znaków z ciągu

find_first_not_of - znajduje w napisie pierwszy znak różny od któregokolwiek ze znaków z ciągu

find_last_of i find_last_not_of - podobnie jak powyżej, tyle że szukają od końca

Jeśli w danym stringu znajdziemy to, co nas tam w nim interesuje, możemy skopiować interesujący nas fragment do innego napisu. Poniższa metoda zwraca taki string jako obiekt tymczasowy:

string substr(size_t pos = 0, size_t n = npos) const

która, jak widać, potrzebuje mieć podany początek owego ciągu oraz ilość (!) znaków nań się składających (zwracam na to uwagę; w ogólności wszelkie zakresy w metodach stringów określa się zawsze przez indeks początkowy oraz ilość znaków).

Koncepty Porównywalny i Porządkowalny

Główną metodą do dokonywania porównań napisów jest metoda compare, która jest odpowiednikiem strcmp. Argumenty compare są identyczne jak assign. Efektywnie zatem mamy dwa argumenty, jeden to jest ten string, na rzecz którego wołano metodę oraz ten drugi, określony przez argumenty compare(). Dodatkowo compare posiada również dodatkowe sygnatury, które umożliwiają porównywanie fragmentaryczne:

To jest właściwie najdłuższa z postaci compare i umożliwia porównanie fragmentu bieżącego napisu (określanego przez pierwsze dwa argumenty) z fragmentem napisu podanego jako 's' (określanego przez dwa ostatnie argumenty).

Na owym compare() opierają się operatory relacji, czyli ==, !=, < (innych operatorów relacji nie ma; jak komuś potrzeba, to może sobie zaimportować przestrzeń nazw std::rel_ops). Dokumentacja ostrożnie wypowiada się nt. operatora <; mówi się tylko, że jest podobny do odwrotności operatora ==. Oficjalnie jednak jednocześnie trzeba pamiętać, że < jest operatorem, który ma dostarczać możliwość porządkowania.

Wycinanie i zastępowanie

Oczywiście mogą się nam jakieś znaki w napisie nie podobać i z tego względu zechcemy je usunąć. Dokonuje tego metoda erase:

string& erase(size_t pos = 0, size_t n = npos);

Jak widać, można ją wywołać również bez argumentów i to wyczyści całego stringa. To samo robi również metoda clear().

Możemy również stringa skrócić lub poszerzyć wraz z wypełnieniem odpowiednią wartością znaku; wykonuje to metoda resize():

void resize(size_type n, char c = char())

Możemy również wewnątrz stringa zastąpić jego fragment innym ciągiem znaków. Wykonuje to metoda replace():

string& replace(size_t pos, size_t n, etc... );
string& replace(iterator first, iterator last, etc... );

Owo "etc" znaczy tutaj ten sam zestaw argumentów, co przy assign, co ma stanowić ten drugi argument, będący ciągiem, jaki należy wstawić. Pierwsze dwa argumenty zaś określają zakres w bieżącym napisie, jaki należy tym podanym stringiem zastąpić. Jak widać, ten zakres może być podany jako początek i ilość znaków oraz jako para iteratorów wyznaczająca zakres.

Misc

No Misc, a co. Tutaj znajduje się to, czego nie chciało mi się uporządkować. W tym również pewna dość egzotyczna, moim zdaniem, metoda zwana copy:

size_t copy(char* buf, size_t n, size_t pos = 0) const

Metoda ta (może powinna się raczej nazywać "copy_to") kopiuje 'n' znaków poczynając od 'pos' z bieżącego napisu do bufora 'buf'. Jak widać, 'n' jest tutaj jednocześnie wymaganą wielkością bufora i wielkością zakresu źródłowego znaków. Metoda ta rzuca wyjątkiem std::out_of_range, jeśli 'pos' > size().

Dodatkowo istnieje parę szczegółów związanych ze standardowymi strumieniami: operatory << i >> (o znaczeniu, którego chyba nie muszę wyjaśniać) oraz dość istotną funkcję getline (zaznaczam, że podaję tu uproszczone definicje, zakładając skonkretyzowane std::string i std::istream; postać ogólna tej funkcji jako wzorca wymaga podania basic_istream i basic_string konkretyzowanych tym samym typem znaku):

istream& getline(
  istream& stream, string& s [, char delim]
);

Jest to właściwie identyczne z istream::getline, z tym tylko że wywołuje się to jako funkcję (jakiś istream trzeba podać jako pierwszy argument), a także nie podaje się maksymalnego rozmiaru (string sam przydzieli tyle, ile trzeba). Podobnie jak istream::getline, istnieje opcjonalny argument 'delim' określający znak, do którego należy czytać; standardowo jest to znak końca linii.