Jakie jest uzasadnienie ciągów zakończonych zerem?

Mimo że uwielbiam C i C ++, nie mogę powstrzymać się od podrapania po wyborze ciągów zakończonych znakiem zerowym:

• Łańcuchy z prefiksem długości (tj. Pascal) istniały przed C.
• Łańcuchy z prefiksem długości przyspieszają działanie kilku algorytmów, umożliwiając ciągłe wyszukiwanie długości.
• Łańcuchy z prefiksem długości utrudniają powodowanie błędów przepełnienia bufora.
• Nawet na maszynie 32-bitowej, jeśli zezwolisz, aby łańcuch był wielkości dostępnej pamięci, łańcuch z prefiksem długości jest tylko trzy bajty szerszy niż łańcuch zakończony zerem. Na maszynach 16-bitowych jest to jeden bajt. Na maszynach 64-bitowych 4 GB to rozsądny limit długości łańcucha, ale nawet jeśli chcesz go rozszerzyć do wielkości słowa maszynowego, maszyny 64-bitowe zwykle mają wystarczającą pamięć, co sprawia, że ​​dodatkowe siedem bajtów jest argumentem zerowym. Wiem, że oryginalny standard C został napisany dla niesamowicie słabych maszyn (pod względem pamięci), ale argument wydajności nie sprzedaje mnie tutaj.
• Prawie każdy inny język (tj. Perl, Pascal, Python, Java, C # itp.) Używa ciągów z prefiksem długości. Te języki zwykle pokonują C w testach porównawczych w zakresie manipulacji ciągami, ponieważ są bardziej wydajne w przypadku ciągów.
• C ++ nieco to poprawiło w std::basic_stringszablonie, ale tablice zwykłych znaków oczekujące ciągów zakończonych znakiem zerowym są nadal wszechobecne. Jest to również niedoskonałe, ponieważ wymaga alokacji sterty.
• Ciągi zakończone znakiem NULL muszą zarezerwować znak (mianowicie NULL), który nie może istnieć w ciągu, a ciągi z prefiksem długości mogą zawierać osadzone wartości NULL.

Kilka z tych rzeczy wyszło na jaw niedawno niż C, więc sensowne byłoby, aby C nie wiedział o nich. Jednak kilka było wyraźnie na długo przed pojawieniem się C. Dlaczego ciągi zerowane mają być wybierane zamiast oczywiście prefiksu o większej długości?

EDYCJA : Ponieważ niektórzy pytali o fakty (i nie podobały mi się te, które już przedstawiłem) na temat powyższego punktu wydajności, wynikają one z kilku rzeczy:

• Łączenie przy użyciu łańcuchów zakończonych zerem wymaga złożoności czasowej O (n + m). Prefiksowanie długości często wymaga tylko O ​​(m).
• Długość przy użyciu łańcuchów zakończonych znakiem zerowym wymaga złożoności czasowej O (n). Prefiks długości to O (1).
• Długość i konkat to zdecydowanie najczęstsze operacje na łańcuchach. Istnieje kilka przypadków, w których ciągi zakończone znakiem zerowym mogą być bardziej wydajne, ale występują one znacznie rzadziej.

Z poniższych odpowiedzi wynika, że ​​niektóre przypadki, w których ciągi zakończone znakiem NULL są bardziej wydajne:

• Kiedy musisz odciąć początek łańcucha i przekazać go do jakiejś metody. Naprawdę nie możesz tego zrobić w stałym czasie z prefiksem długości, nawet jeśli możesz zniszczyć oryginalny ciąg, ponieważ prefiks długości prawdopodobnie musi być zgodny z regułami wyrównania.
• W niektórych przypadkach, gdy przeglądasz ciąg znaków po znaku, możesz zapisać rejestr procesora. Zauważ, że działa to tylko w przypadku, gdy nie przydzieliłeś dynamicznie ciągu (ponieważ wtedy musiałbyś go zwolnić, wymagając użycia tego rejestru procesora, który zapisałeś, aby utrzymać wskaźnik, który pierwotnie otrzymałeś od malloc i przyjaciół).

Żadne z powyższych nie jest tak powszechne jak długość i konkat.

W odpowiedziach poniżej znajduje się jeszcze jedno stwierdzenie:

• Musisz odciąć koniec sznurka

ale ten jest niepoprawny - to tyle samo czasu na łańcuchy zakończone znakiem null i łańcuchy z prefiksem długości. (Ciągi zakończone znakiem NULL po prostu przyklejają null tam, gdzie ma być nowy koniec, prefiksy długości po prostu odejmują od prefiksu.)

Z pyska konia

Żaden z BCPL, B lub C nie obsługuje danych znaków silnie w języku; każdy traktuje ciągi znaków jak wektory liczb całkowitych i uzupełnia ogólne zasady o kilka konwencji. Zarówno w BCPL, jak i B literał ciągu oznacza adres obszaru statycznego zainicjowanego znakami ciągu, upakowanego w komórkach. W BCPL pierwszy spakowany bajt zawiera liczbę znaków w ciągu; w B, nie ma licznika i łańcuchy są zakończone znakiem szczególnym charakterze, które B orkiszu *e. Ta zmiana została wprowadzona częściowo, aby uniknąć ograniczenia długości łańcucha spowodowanego utrzymywaniem licznika w 8- lub 9-bitowym gnieździe, a częściowo dlatego, że utrzymywanie liczenia wydawało się, naszym zdaniem, mniej wygodne niż używanie terminatora.

_{Dennis M Ritchie, Rozwój języka C.}

C nie ma łańcucha jako części języka. „Ciąg znaków” w C jest tylko wskaźnikiem char. Więc może zadajesz złe pytanie.

„Jakie jest uzasadnienie pominięcia typu ciągu” może być bardziej odpowiednie. Zwracam na to uwagę, że C nie jest językiem obiektowym i ma jedynie podstawowe typy wartości. Łańcuch to koncepcja wyższego poziomu, którą należy w jakiś sposób połączyć, łącząc wartości innych typów. C jest na niższym poziomie abstrakcji.

w świetle szalejącego szkwała poniżej:

Chcę tylko zaznaczyć, że nie próbuję powiedzieć, że jest to głupie lub złe pytanie, lub że sposób reprezentowania łańcuchów w C jest najlepszym wyborem. Próbuję wyjaśnić, że pytanie byłoby bardziej zwięźle postawione, jeśli weźmie się pod uwagę fakt, że C nie ma mechanizmu odróżniającego ciąg znaków jako typ danych od tablicy bajtów. Czy to najlepszy wybór w świetle mocy obliczeniowej i mocy pamięci dzisiejszych komputerów? Prawdopodobnie nie. Ale z perspektywy czasu zawsze jest 20/20 i tak dalej :)

Pada pytanie jak Length Prefixed Strings (LPS)vs zero terminated strings (SZ)rzeczy, ale przede wszystkim wystawiać korzyści z prefiksem długości strun. To może wydawać się przytłaczające, ale szczerze mówiąc, powinniśmy również rozważyć wady LPS i zalety SZ.

W moim rozumieniu pytanie to można nawet uznać za stronniczy sposób zadawania pytań „jakie są zalety ciągów zerowanych?”.

Zalety (widzę) ciągów zerowanych:

• bardzo proste, nie trzeba wprowadzać nowych pojęć w języku, tablice char / wskaźniki char mogą zrobić.
• podstawowy język zawiera po prostu minimalny cukier składniowy, aby przekonwertować coś między podwójnymi cudzysłowami na kilka znaków (naprawdę kilka bajtów). W niektórych przypadkach można go użyć do zainicjowania rzeczy całkowicie niezwiązanych z tekstem. Na przykład format pliku obrazu xpm jest prawidłowym źródłem C, które zawiera dane obrazu zakodowane jako ciąg.
• nawiasem mówiąc, to można postawić zero w ciągiem znaków, kompilator będzie po prostu dodać jeszcze jeden na końcu dosłownym: "this\0is\0valid\0C". Czy to jest struna? czy cztery struny? Lub kilka bajtów ...
• płaska implementacja, brak ukrytej pośredniczości, brak ukrytej liczby całkowitej.
• brak zaangażowanego ukrytego przydziału pamięci (cóż, niektóre niesławne niestandardowe funkcje, takie jak strdup, wykonują przydział, ale to głównie jest źródłem problemu).
• nie ma specyficznego problemu dla małego lub dużego sprzętu (wyobraź sobie, że trzeba zarządzać długością 32-bitową prefiksu na 8-bitowych mikrokontrolerach lub ograniczeniami ograniczania rozmiaru łańcucha do mniej niż 256 bajtów, to był problem, który faktycznie miałem z eonami Turbo Pascal eony temu).
• implementacja manipulacji ciągami to tylko garść bardzo prostych funkcji bibliotecznych
• wydajne w przypadku głównego użycia ciągów: stały tekst odczytywany sekwencyjnie od znanego początku (głównie wiadomości do użytkownika).
• końcowe zero nie jest nawet obowiązkowe, dostępne są wszystkie niezbędne narzędzia do manipulowania znakami, takie jak kilka bajtów. Podczas inicjalizacji tablicy w C można nawet uniknąć terminatora NUL. Po prostu ustaw odpowiedni rozmiar. char a[3] = "foo";jest poprawny C (nie C ++) i nie umieści ostatniego zera w.
• spójny z uniksowym punktem widzenia „wszystko jest plikiem”, w tym „pliki”, które nie mają wewnętrznej długości, takie jak stdin, stdout. Należy pamiętać, że operacje podstawowe do odczytu i zapisu są implementowane na bardzo niskim poziomie. Nie są to wywołania biblioteczne, ale wywołania systemowe. Ten sam interfejs API jest używany do plików binarnych lub tekstowych. Operacje podstawowe odczytu pliku uzyskują adres bufora i rozmiar i zwracają nowy rozmiar. I możesz użyć ciągów jako bufora do zapisu. Użycie innego rodzaju reprezentacji ciągu oznaczałoby, że nie można łatwo użyć literału jako bufora do wyjścia, lub musiałbyś sprawić, że zachowuje się bardzo dziwnie podczas rzutowania char*. Mianowicie, aby nie zwracać adresu ciągu, ale zamiast tego zwracać rzeczywiste dane.
• bardzo łatwe do manipulowania danymi tekstowymi odczytywanymi z pliku w miejscu, bez zbędnej kopii bufora, wystarczy wstawić zera we właściwych miejscach (no cóż, nie tak naprawdę w nowoczesnym C, ponieważ ciągi podwójnie cytowane są obecnie tablicami stałych znaków zwykle przechowywanymi w niemodyfikowalnych danych człon).
• wstawienie niektórych wartości int o dowolnym rozmiarze oznaczałoby problemy z wyrównaniem. Początkowa długość powinna być wyrównana, ale nie ma powodu, aby robić to dla danych znaków (i ponownie, wymuszenie wyrównania ciągów oznaczałoby problemy podczas traktowania ich jako wiązki bajtów).
• długość jest znana w czasie kompilacji dla stałych literałów (sizeof). Dlaczego więc ktoś chciałby przechowywać go w pamięci, przygotowując go do rzeczywistych danych?
• w sposób, w jaki C robi (prawie) wszystkich innych, łańcuchy są postrzegane jako tablice znaków char. Ponieważ długość tablicy nie jest zarządzana przez C, logiczna długość nie jest również zarządzana dla łańcuchów. Jedyną zaskakującą rzeczą jest to, że na końcu dodano 0 pozycji, ale to tylko na poziomie języka podstawowego podczas wpisywania ciągu między podwójnymi cudzysłowami. Użytkownicy mogą doskonale wywoływać funkcje manipulacji ciągami mijającymi długość, a nawet używać zwykłego memcopy. SZ to tylko obiekt. W większości innych języków długość tablicy jest zarządzana, logiczne jest to samo dla łańcuchów.
• w dzisiejszych czasach zestawy znaków 1-bajtowych to za mało i często masz do czynienia z zakodowanymi ciągami znaków Unicode, w których liczba znaków jest bardzo różna od liczby bajtów. Oznacza to, że użytkownicy prawdopodobnie będą chcieli czegoś więcej niż „tylko rozmiaru”, ale także innych informacji. Zachowując długość nie używaj niczego (szczególnie nie ma naturalnego miejsca do ich przechowywania) w odniesieniu do tych innych przydatnych informacji.

To powiedziawszy, nie trzeba narzekać w rzadkim przypadku, gdy standardowe ciągi C są rzeczywiście nieefektywne. Biblioteki są dostępne. Jeśli podążę za tym trendem, powinienem narzekać, że standardowy C nie zawiera żadnych funkcji obsługi wyrażeń regularnych ... ale tak naprawdę wszyscy wiedzą, że to nie jest prawdziwy problem, ponieważ istnieją biblioteki przeznaczone do tego celu. Jeśli więc potrzebna jest wydajność manipulacji ciągami, dlaczego nie skorzystać z biblioteki takiej jak bstring ? A może nawet ciągi znaków C ++?

EDIT : Niedawno miałem wygląd strun D . Interesujące jest, aby zobaczyć, że wybrane rozwiązanie nie jest ani prefiksem rozmiaru, ani zakończeniem zerowym. Podobnie jak w C, dosłowne łańcuchy ujęte w podwójne cudzysłowy są po prostu krótką ręką dla niezmiennych tablic char, a język ma również słowo kluczowe string, które to oznacza (niezmienna tablica char).

Ale tablice D są znacznie bogatsze niż tablice C. W przypadku tablic statycznych długość jest znana w czasie wykonywania, więc nie ma potrzeby przechowywania długości. Kompilator ma go w czasie kompilacji. W przypadku tablic dynamicznych dostępna jest długość, ale dokumentacja D nie określa, gdzie jest przechowywana. Z tego, co wiemy, kompilator może zdecydować się zachować go w jakimś rejestrze lub w pewnej zmiennej przechowywanej z dala od danych znaków.

Na normalnych tablicach znaków lub ciągach nieliteralnych nie ma końcowego zera, dlatego programista musi ustawić je sam, jeśli chce wywołać jakąś funkcję C z D. W szczególnym przypadku ciągów dosłownych, jednak kompilator D nadal ustawia zero na koniec każdego łańcucha (aby umożliwić łatwe rzutowanie na łańcuchy C, aby ułatwić wywoływanie funkcji C?), ale to zero nie jest częścią ciągu (D nie liczy go w rozmiarze łańcucha).

Jedyną rzeczą, która mnie trochę rozczarowała, jest to, że ciągi powinny być utf-8, ale długość najwyraźniej nadal zwraca pewną liczbę bajtów (przynajmniej tak jest w moim kompilatorze gdc), nawet przy użyciu wielobajtowych znaków. Nie jest dla mnie jasne, czy jest to błąd kompilatora, czy celowo. (OK, prawdopodobnie dowiedziałem się, co się stało. Aby powiedzieć kompilatorowi D, że twoje źródło używa utf-8, musisz na początku umieścić jakiś głupi bajt. Piszę głupio, bo wiem, że nie robi tego edytor, szczególnie dla UTF- 8, który ma być zgodny z ASCII).

Myślę, że ma to przyczyny historyczne i znalazłem to w wikipedii :

W czasie opracowywania C (i języków, z których został uzyskany) pamięć była bardzo ograniczona, więc użycie tylko jednego bajtu narzutu do przechowywania długości łańcucha było atrakcyjne. Jedyna popularna alternatywa w tym czasie, zwykle nazywana „ciągiem Pascala” (chociaż używana również we wczesnych wersjach BASIC), używała wiodącego bajtu do przechowywania długości ciągu. Dzięki temu ciąg może zawierać NUL i znalezienie długości wymaga tylko jednego dostępu do pamięci (czas O (1) (stały)). Ale jeden bajt ogranicza długość do 255. To ograniczenie długości było znacznie bardziej restrykcyjne niż problemy ze łańcuchem C, więc łańcuch C ogólnie wygrał.

Calavera ma rację , ale ponieważ ludzie wydają się nie rozumieć, przedstawię kilka przykładów kodu.

Najpierw zastanówmy się, czym jest C: prosty język, w którym cały kod ma dość bezpośrednie tłumaczenie na język maszynowy. Wszystkie typy mieszczą się w rejestrach i na stosie i nie wymagają do działania systemu operacyjnego ani dużej biblioteki wykonawczej, ponieważ miały napisać te rzeczy (zadanie, do którego świetnie się nada, biorąc pod uwagę nie jest nawet prawdopodobnym konkurentem do dziś).

Gdyby C miał stringtyp, taki jak intlub char, byłby to typ, który nie zmieściłby się w rejestrze lub na stosie i wymagałby alokacji pamięci (wraz z całą infrastrukturą wspierającą) w jakikolwiek sposób. Wszystko to jest sprzeczne z podstawowymi założeniami C.

Zatem ciąg w C to:

char s*;

Załóżmy więc, że były one z prefiksem długości. Napiszmy kod, aby połączyć dwa ciągi:

char* concat(char* s1, char* s2)
{
    /* What? What is the type of the length of the string? */
    int l1 = *(int*) s1;
    /* How much? How much must I skip? */
    char *s1s = s1 + sizeof(int);
    int l2 = *(int*) s2;
    char *s2s = s2 + sizeof(int);
    int l3 = l1 + l2;
    char *s3 = (char*) malloc(l3 + sizeof(int));
    char *s3s = s3 + sizeof(int);
    memcpy(s3s, s1s, l1);
    memcpy(s3s + l1, s2s, l2);
    *(int*) s3 = l3;
    return s3;
}

Inną alternatywą byłoby użycie struktury do zdefiniowania łańcucha:

struct {
  int len; /* cannot be left implementation-defined */
  char* buf;
}

W tym momencie wszelkie manipulacje ciągami wymagałyby dokonania dwóch przydziałów, co w praktyce oznacza, że ​​przeglądałeś bibliotekę, aby wykonać dowolną obsługę.

Najśmieszniejsze jest to, że ... kodowanym jak zrobić istnieć w C! Nie są one po prostu używane do codziennego wyświetlania wiadomości użytkownikom.

Oto, o czym mówi Calavera: w C nie ma typu łańcucha . Aby cokolwiek z tym zrobić, trzeba wziąć wskaźnik i zdekodować go jako wskaźnik do dwóch różnych typów, a następnie staje się bardzo istotny, jaki jest rozmiar łańcucha, i nie można go po prostu pozostawić jako „zdefiniowaną implementację”.

Teraz C i tak może obsługiwać pamięć, a memfunkcje w bibliotece ( <string.h>nawet, nawet!) Zapewniają wszystkie narzędzia potrzebne do obsługi pamięci jako pary wskaźnika i wielkości. Tak zwane „ciągi” w C zostały utworzone tylko w jednym celu: pokazywania komunikatów w kontekście pisania systemu operacyjnego przeznaczonego dla terminali tekstowych. Do tego wystarczy zerowe zakończenie.

Oczywiście ze względu na wydajność i bezpieczeństwo będziesz chciał zachować długość łańcucha podczas pracy z nim, zamiast powtarzać strlenlub wykonywać na nim równowartość. Jednak przechowywanie długości w ustalonym miejscu tuż przed zawartością łańcucha jest niesamowicie złym projektem. Jak zauważył Jörgen w komentarzach do odpowiedzi Sanjita, wyklucza to traktowanie ogona łańcucha jako łańcucha, co na przykład sprawia, że ​​wiele typowych operacji jest podobnych path_to_filenamelub filename_to_extensionniemożliwych bez przydzielania nowej pamięci (i pociąga za sobą możliwość awarii i obsługi błędów) . I oczywiście istnieje problem, że nikt nie może się zgodzić, ile bajtów powinno zajmować pole długości łańcucha (dużo złych „łańcuchów Pascala”

Projekt C pozwalający programatorowi wybrać, czy / gdzie / jak przechowywać długość, jest znacznie bardziej elastyczny i wydajny. Ale oczywiście programista musi być inteligentny. C karze głupotę programami, które powodują awarie, zatrzymują się lub powodują korzenie wrogów.

Leniwość, oszczędność rejestrów i przenośność, biorąc pod uwagę żyłkę asemblera dowolnego języka, zwłaszcza C, który jest o jeden krok wyżej niż asembler (w ten sposób dziedziczy wiele starszego kodu asemblera). Zgodziłbyś się, ponieważ znak zerowy byłby bezużyteczny w tych dniach ASCII (i prawdopodobnie tak dobry jak znak kontrolny EOF).

zobaczmy w pseudo kodzie

function readString(string) // 1 parameter: 1 register or 1 stact entries
    pointer=addressOf(string) 
    while(string[pointer]!=CONTROL_CHAR) do
        read(string[pointer])
        increment pointer

w sumie 1 użycie rejestru

przypadek 2

 function readString(length,string) // 2 parameters: 2 register used or 2 stack entries
     pointer=addressOf(string) 
     while(length>0) do 
         read(string[pointer])
         increment pointer
         decrement length

wykorzystano ogółem 2 rejestry

To może wydawać się krótkowzroczne w tym czasie, ale biorąc pod uwagę oszczędność kodu i rejestru (które były w tym czasie PREMIUM, kiedy wiesz, że używają karty dziurkacza). W związku z tym, że jest szybszy (gdy szybkość procesora można liczyć w kHz), ten „hack” był naprawdę cholernie dobry i przenośny, aby z łatwością rejestrować procesor.

Dla argumentu zaimplementuję 2 wspólne operacje na łańcuchach

stringLength(string)
     pointer=addressOf(string)
     while(string[pointer]!=CONTROL_CHAR) do
         increment pointer
     return pointer-addressOf(string)

złożoność O (n), gdzie w większości przypadków łańcuch PASCAL ma wartość O (1), ponieważ długość łańcucha jest wstępnie powiązana ze strukturą łańcucha (oznaczałoby to również, że operacja ta musiałaby zostać przeprowadzona na wcześniejszym etapie).

concatString(string1,string2)
     length1=stringLength(string1)
     length2=stringLength(string2)
     string3=allocate(string1+string2)
     pointer1=addressOf(string1)
     pointer3=addressOf(string3)
     while(string1[pointer1]!=CONTROL_CHAR) do
         string3[pointer3]=string1[pointer1]
         increment pointer3
         increment pointer1
     pointer2=addressOf(string2)
     while(string2[pointer2]!=CONTROL_CHAR) do
         string3[pointer3]=string2[pointer2]
         increment pointer3
         increment pointer1
     return string3

złożoność O (n) i nadanie długości łańcucha nie zmieniłoby złożoności operacji, ale przyznaję, że zajęłoby to 3 razy mniej czasu.

Z drugiej strony, jeśli użyjesz łańcucha PASCAL, będziesz musiał przeprojektować interfejs API, aby uwzględnić długość rejestru i endianowość bitów, łańcuch PASCAL ma dobrze znane ograniczenie 255 znaków (0xFF), ponieważ długość została zapisana w 1 bajcie (8 bitów ), a jeśli chcesz mieć dłuższy ciąg (16 bitów -> cokolwiek), musisz wziąć pod uwagę architekturę w jednej warstwie kodu, co w większości przypadków oznacza niekompatybilne interfejsy API ciągów, jeśli chcesz dłuższy ciąg.

Przykład:

Jeden plik został napisany z przygotowanym ciągiem interfejsu API na 8-bitowym komputerze, a następnie musiałby zostać odczytany na powiedzmy na komputerze 32-bitowym. Co leniwy program zrobiłby, biorąc pod uwagę, że twoje 4 bajty to długość łańcucha, a następnie przydzielono tyle pamięci następnie spróbuj odczytać tyle bajtów. Innym przypadkiem byłby 32-bajtowy ciąg PPC odczytany (mały endian) na x86 (duży endian), oczywiście jeśli nie wiesz, że jeden jest zapisany przez drugi, mogą wystąpić problemy. Długość 1 bajtu (0x00000001) to 16777216 (0x0100000), czyli 16 MB na odczyt ciągu 1-bajtowego. Oczywiście powiedziałbyś, że ludzie powinni zgodzić się na jeden standard, ale nawet 16-bitowy Unicode ma małą i dużą endianizm.

Oczywiście C również miałby swoje problemy, ale poruszone tutaj problemy byłyby bardzo mało dotknięte.

Pod wieloma względami C był prymitywny. I bardzo mi się podobało.

Było to o krok ponad językiem asemblera, zapewniając prawie taką samą wydajność w języku, który był znacznie łatwiejszy do napisania i utrzymania.

Terminator zerowy jest prosty i nie wymaga specjalnego wsparcia ze strony języka.

Patrząc wstecz, nie wydaje się to wygodne. Ale użyłem języka asemblerowego w latach 80. i wtedy wydawało się to bardzo wygodne. Wydaje mi się, że oprogramowanie stale się rozwija, a platformy i narzędzia są coraz bardziej wyrafinowane.

Zakładając przez chwilę, że C zaimplementował ciągi Pascala, poprzedzając je ciągiem długości: czy ciąg znaków o długości 7 znaków ma ten sam TYP DANYCH, co ciąg znaków o długości 3 znaków? Jeśli odpowiedź brzmi „tak”, to jaki kod powinien wygenerować kompilator, gdy przypiszę ten drugi do drugiego? Czy należy obciąć lub automatycznie zmienić rozmiar ciągu? W przypadku zmiany rozmiaru, czy operacja ta powinna być chroniona przez blokadę, aby zapewnić bezpieczeństwo wątku? Podejście C przeskoczyło wszystkie te problemy, czy im się to podoba, czy nie :)

W jakiś sposób zrozumiałem pytanie, które sugeruje, że nie ma obsługi kompilatora dla łańcuchów z prefiksami długości w C. Poniższy przykład pokazuje, że możesz przynajmniej uruchomić własną bibliotekę łańcuchów znaków C, w której długości łańcuchów są liczone w czasie kompilacji, za pomocą takiej konstrukcji:

#define PREFIX_STR(s) ((prefix_str_t){ sizeof(s)-1, (s) })

typedef struct { int n; char * p; } prefix_str_t;

int main() {
    prefix_str_t string1, string2;

    string1 = PREFIX_STR("Hello!");
    string2 = PREFIX_STR("Allows \0 chars (even if printf directly doesn't)");

    printf("%d %s\n", string1.n, string1.p); /* prints: "6 Hello!" */
    printf("%d %s\n", string2.n, string2.p); /* prints: "48 Allows " */

    return 0;
}

Nie przyniesie to jednak żadnych problemów, ponieważ musisz uważać, kiedy specjalnie zwolnić ten wskaźnik łańcucha i kiedy jest on statycznie przydzielony (dosłownie char tablica ).

Edytować: Jako bardziej bezpośrednią odpowiedź na pytanie, moim zdaniem jest to sposób, w jaki C mógł obsługiwać zarówno posiadanie dostępnej długości łańcucha (jako stałej czasowej kompilacji), jeśli jest to potrzebne, ale nadal bez narzutu pamięci, jeśli chcesz użyć tylko wskaźniki i zerowe zakończenie.

Oczywiście wydaje się, że zalecaną praktyką jest praca z ciągami zakończonymi zerem, ponieważ biblioteka standardowa ogólnie nie przyjmuje długości łańcucha jako argumentu, a ponieważ wyodrębnienie długości nie jest tak proste char * s = "abc", jak pokazuje mój przykład.

„Nawet na maszynie 32-bitowej, jeśli zezwolisz, aby łańcuch był wielkości dostępnej pamięci, łańcuch z prefiksem długości jest tylko trzy bajty szerszy niż łańcuch zakończony zerem.”

Po pierwsze, dodatkowe 3 bajty mogą stanowić znaczne obciążenie dla krótkich łańcuchów. W szczególności ciąg o zerowej długości zajmuje teraz 4 razy więcej pamięci. Niektórzy z nas używają maszyn 64-bitowych, więc albo potrzebujemy 8 bajtów, aby przechowywać ciąg o zerowej długości lub format ciągu nie jest w stanie poradzić sobie z najdłuższymi ciągami obsługiwanymi przez platformę.

Mogą również występować problemy z wyrównaniem. Załóżmy, że mam blok pamięci zawierający 7 ciągów znaków, na przykład „solo \ 0second \ 0 \ 0four \ 0five \ 0 \ 0seventh”. Drugi ciąg zaczyna się od przesunięcia 5. Sprzęt może wymagać wyrównania 32-bitowych liczb całkowitych pod adresem będącym wielokrotnością liczby 4, dlatego należy dodać dopełnianie, jeszcze bardziej zwiększając obciążenie. W porównaniu z tym reprezentacja C jest bardzo wydajna pod względem pamięci. (Wydajność pamięci jest dobra; pomaga na przykład w wydajności pamięci podręcznej).

Zakończenie zerowe pozwala na szybkie operacje oparte na wskaźnikach.

Jeden punkt jeszcze nie wspomniany: kiedy zaprojektowano C, istniało wiele maszyn, w których „char” nie miał ośmiu bitów (nawet dzisiaj istnieją platformy DSP, w których tak nie jest). Jeśli ktoś zdecyduje, że ciągi mają być poprzedzone przedrostkiem długości, ile prefiksów długości wartości „char” należy użyć? Użycie dwóch nałożyłoby sztuczny limit długości łańcucha dla maszyn z 8-bitowym char i 32-bitową przestrzenią adresową, a marnowanie miejsca na maszynach z 16-bitowym char i 16-bitową przestrzenią adresową.

Gdyby ktoś chciał pozwolić na wydajne przechowywanie ciągów o dowolnej długości, a gdyby „char” był zawsze 8-bitowy, można - za pewien koszt szybkości i rozmiaru kodu - zdefiniować schemat, który byłby ciągiem poprzedzonym liczbą parzystą N będzie mieć długość N / 2 bajtów, łańcuch poprzedzony nieparzystą wartością N, a parzystą wartością M (odczyt do tyłu) może być ((N-1) + M * char_max) / 2 itd. I wymagać dowolnego bufora, który twierdzi, że oferuje pewną ilość miejsca do przechowywania łańcucha, musi pozwalać na wystarczającą liczbę bajtów poprzedzających to miejsce, aby obsłużyć maksymalną długość. Fakt, że „char” nie zawsze wynosi 8 bitów, skomplikowałoby taki schemat, ponieważ liczba „char” wymagana do utrzymania długości łańcucha byłaby różna w zależności od architektury procesora.

Wiele decyzji projektowych dotyczących C wynika z faktu, że w momencie jego pierwszego wdrożenia przekazywanie parametrów było nieco kosztowne. Biorąc pod uwagę wybór między np

void add_element_to_next(arr, offset)
  char[] arr;
  int offset;
{
  arr[offset] += arr[offset+1];
}

char array[40];

void test()
{
  for (i=0; i<39; i++)
    add_element_to_next(array, i);
}

przeciw

void add_element_to_next(ptr)
  char *p;
{
  p[0]+=p[1];
}

char array[40];

void test()
{
  int i;
  for (i=0; i<39; i++)
    add_element_to_next(arr+i);
}

ten ostatni byłby nieco tańszy (i dlatego preferowany), ponieważ wymagałby tylko przekazania jednego parametru zamiast dwóch. Gdyby wywoływana metoda nie musiała znać adresu podstawowego tablicy ani indeksu w niej zawartego, przekazanie pojedynczego wskaźnika łączącego oba byłoby tańsze niż przekazanie wartości osobno.

Chociaż istnieje wiele rozsądnych sposobów, w jakie C mógł zakodować długości łańcucha, metody, które zostały wynalezione do tego czasu, miałyby wszystkie wymagane funkcje, które powinny być w stanie pracować z częścią łańcucha, aby zaakceptować adres bazowy łańcucha i pożądany indeks jako dwa osobne parametry. Zastosowanie zerowego zakończenia bajtów pozwoliło uniknąć tego wymogu. Chociaż inne podejścia byłyby lepsze w przypadku dzisiejszych maszyn (współczesne kompilatory często przekazują parametry w rejestrach, a memcpy można zoptymalizować w taki sposób, aby strcpy () - odpowiedniki nie mogą) wystarczająca liczba kodów produkcyjnych używa łańcuchów zakończonych zerami bajtów, których trudno zmienić na cokolwiek innego.

PS - W zamian za niewielką karę prędkości w przypadku niektórych operacji i odrobinę dodatkowego obciążenia na dłuższych ciągach, możliwe byłoby, aby metody działające z ciągami akceptowały wskaźniki bezpośrednio do ciągów, bufory ciągów sprawdzane pod kątem granic lub struktury danych identyfikujące podłańcuchy innego łańcucha. Funkcja taka jak „strcat” wyglądałaby jak [nowoczesna składnia]

void strcat(unsigned char *dest, unsigned char *src)
{
  struct STRING_INFO d,s;
  str_size_t copy_length;

  get_string_info(&d, dest);
  get_string_info(&s, src);
  if (d.si_buff_size > d.si_length) // Destination is resizable buffer
  {
    copy_length = d.si_buff_size - d.si_length;
    if (s.src_length < copy_length)
      copy_length = s.src_length;
    memcpy(d.buff + d.si_length, s.buff, copy_length);
    d.si_length += copy_length;
    update_string_length(&d);
  }
}

Nieco większa niż metoda strcat K&R, ale obsługiwałaby sprawdzanie ograniczeń, czego nie robi metoda K&R. Ponadto, w przeciwieństwie do obecnej metody, można łatwo połączyć dowolne podciąg, np

/* Concatenate 10th through 24th characters from src to dest */

void catpart(unsigned char *dest, unsigned char *src)
{
  struct SUBSTRING_INFO *inf;
  src = temp_substring(&inf, src, 10, 24);
  strcat(dest, src);
}

Zwróć uwagę, że czas życia łańcucha zwracanego przez temp_substring byłby ograniczony przez si src, który zawsze był krótszy (dlatego metoda wymagainf przekazania - jeśli byłaby lokalna, umarłaby, gdy metoda powróciła).

Pod względem kosztu pamięci łańcuchy i bufory do 64 bajtów miałyby jeden bajt narzutu (taki sam jak łańcuchy zakończone zerem); dłuższe łańcuchy miałyby nieco więcej (to, czy jeden dozwolony narzut między dwoma bajtami i wymagane maksimum byłoby kompromisem czas / przestrzeń). Specjalna wartość bajtu długości / trybu byłaby użyta do wskazania, że ​​funkcja łańcucha otrzymała strukturę zawierającą bajt flagi, wskaźnik i długość bufora (który mógłby następnie dowolnie indeksować do dowolnego innego łańcucha).

Oczywiście, K&R nie wdrożył czegoś takiego, ale najprawdopodobniej dlatego, że nie chcieli poświęcać wiele wysiłku na obsługę napisów - obszar, w którym nawet dziś wiele języków wydaje się raczej anemicznych.

Według Joela Spolsky'ego w tym poście na blogu ,

Jest tak, ponieważ mikroprocesor PDP-7, na którym wymyślono UNIX i język programowania C, miał typ łańcucha ASCIZ. ASCIZ oznaczało „ASCII z Z (zero) na końcu”.

Po zobaczeniu wszystkich innych odpowiedzi tutaj jestem przekonany, że nawet jeśli jest to prawdą, to tylko część powodu, dla którego C ma zakończone zerem „łańcuchy”. Ten post jest dość pouczający, jak proste rzeczy takie jak łańcuchy mogą być naprawdę trudne.

Uzasadnienie nie koniecznie ale kontrapunkt do długości kodowane

1. Niektóre formy dynamicznego kodowania długości są lepsze od statycznego kodowania długości, jeśli chodzi o pamięć, wszystko zależy od użycia. Popatrz na UTF-8 jako dowód. Zasadniczo jest to rozszerzalna tablica znaków do kodowania pojedynczego znaku. Używa to jednego bitu dla każdego rozszerzonego bajtu. Zakończenie NUL wykorzystuje 8 bitów. Prefiks długości, jak sądzę, można również rozsądnie określić jako nieskończoną długość, używając 64 bitów. To, jak często trafiasz przypadek swoich dodatkowych bitów, jest decydującym czynnikiem. Tylko 1 bardzo duży sznurek? Kogo to obchodzi, jeśli używasz 8 lub 64 bitów? Wiele małych ciągów (tj. Ciągów angielskich słów)? Wówczas koszty prefiksu są duże.

2. Ciągi z prefiksem długości, pozwalające zaoszczędzić czas, nie są rzeczywistością . Niezależnie od tego, czy podane dane muszą mieć podaną długość, liczysz w czasie kompilacji, czy naprawdę otrzymujesz dane dynamiczne, które musisz zakodować jako ciąg. Rozmiary te są obliczane w pewnym momencie algorytmu. Można podać osobną zmienną do przechowywania rozmiaru łańcucha zakończonego zerem . Co sprawia, że ​​dyskusja na temat oszczędności czasu jest dyskusyjna. Jeden ma na końcu dodatkowy NUL ... ale jeśli kod długości nie zawiera tego NUL, to dosłownie nie ma żadnej różnicy między nimi. W ogóle nie jest wymagana zmiana algorytmu. Wystarczy wstępny przebieg, który musisz samodzielnie zaprojektować, zamiast kompilatora / środowiska wykonawczego. C polega głównie na robieniu rzeczy ręcznie.

3. Opcjonalny prefiks długości jest zaletą. Nie zawsze potrzebuję tych dodatkowych informacji dla algorytmu, dlatego konieczność zrobienia tego dla każdego łańcucha powoduje, że mój czas obliczeń wstępnych i obliczeń nigdy nie może spaść poniżej O (n). (Tzn. Sprzętowy generator liczb losowych 1-128. Mogę wyciągać z „nieskończonego ciągu”. Powiedzmy, że generuje on tylko znaki tak szybko. Więc nasza długość łańcucha zmienia się cały czas. Ale moje wykorzystanie danych prawdopodobnie nie obchodzi, jak wiele losowych bajtów, które mam. Po prostu chce następnego dostępnego, nieużywanego bajtu, gdy tylko będzie mógł go otrzymać po żądaniu. Mogę czekać na urządzeniu. Ale mogę też wstępnie odczytać bufor znaków. Porównanie długości jest niepotrzebna strata obliczeń. Kontrola zerowa jest bardziej wydajna).

4. Prefiks długości jest dobrą ochroną przed przepełnieniem bufora? Podobnie rozsądne jest korzystanie z funkcji bibliotecznych i implementacja. Co się stanie, jeśli przekażę zniekształcone dane? Mój bufor ma 2 bajty, ale mówię funkcji, że to 7! Np .: Jeśli zakończenie () była przeznaczona do użycia na znanych danych, mogła mieć wewnętrzny sprawdzanie bufora, który testował skompilowane bufory i malloc ()TL; DR NUL nigdy nie musiało być niebezpieczne, po prostu skończyło się to niewłaściwym użyciem.połączenia i nadal postępuj zgodnie ze specyfikacją. Jeśli miał być użyty jako potok dla nieznanego STDIN, aby dotrzeć do nieznanego bufora, to oczywiście nie można wiedzieć o wielkości bufora, co oznacza, że ​​długość arg jest bezcelowa, potrzebujesz tutaj czegoś innego, jak sprawdzanie kanarka. W tym przypadku nie można przedrostkować długości niektórych strumieni i danych wejściowych, po prostu nie można. Co oznacza, że ​​kontrola długości musi być wbudowana w algorytm, a nie magiczną część systemu pisania.

5. counter-counter point: zakończenie NUL jest denerwujące w przypadku plików binarnych. Musisz albo wykonać tutaj prefiks długości, albo w jakiś sposób przekształcić bajty NUL: kody specjalne, mapowanie zakresu itp., Co oczywiście oznacza większe zużycie pamięci / zmniejszenie informacji / więcej operacji na bajt. Prefiks długości zazwyczaj wygrywa tutaj wojnę. Jedyną zaletą transformacji jest to, że nie trzeba pisać żadnych dodatkowych funkcji, aby pokryć ciągi prefiksu długości. Co oznacza, że ​​w bardziej zoptymalizowanych procedurach pod-O (n) możesz sprawić, by automatycznie działały jak ich odpowiedniki O (n) bez dodawania więcej kodu. Minusem jest oczywiście marnotrawstwo czasu / pamięci / kompresji, gdy jest używane na ciężkich łańcuchach NUL.W zależności od tego, ile fragmentów biblioteki powielasz, aby operować na danych binarnych, sensowna może być praca wyłącznie z ciągami prefiksów długości. To powiedziawszy, można również zrobić to samo z łańcuchami z prefiksem długości ... -1 długość może oznaczać zakończenie NUL i można użyć ciągów zakończonych NUL wewnątrz zakończonych długością.

6. Concat: „O (n + m) vs O (m)” Zakładam, że odnosisz się do m jako całkowitej długości łańcucha po konkatenacji, ponieważ oba muszą mieć minimalną liczbę operacji (nie możesz po prostu przypiąć -on na łańcuch 1, co jeśli musisz ponownie przydzielić?). I zakładam, że n to mityczna liczba operacji, których nie musisz już wykonywać z powodu obliczeń wstępnych. Jeśli tak, to odpowiedź jest prosta: obliczenia wstępne.Jeślinalegasz, że zawsze będziesz mieć wystarczającą ilość pamięci, aby nie musieć ponownie przydzielać, a to jest podstawa notacji big-O, wtedy odpowiedź jest jeszcze prostsza: wykonaj wyszukiwanie binarne w przydzielonej pamięci dla końca ciągu 1, wyraźnie jest duża próbka nieskończonych zer po łańcuchu 1, abyśmy nie martwili się o realokację. Tam łatwo udało mi się zalogować (n) i ledwo próbowałem. Co, jeśli przypomnisz sobie, log (n) jest w rzeczywistości tylko tak duży jak 64 na prawdziwym komputerze, co w zasadzie przypomina powiedzenie O (64 + m), które jest zasadniczo O (m). (I tak, logika ta została wykorzystana w analizie w czasie rzeczywistym rzeczywistych struktur danych będących w użyciu dzisiaj. To nie bzdury z mojej głowy.)

7. Concat () / Len () _ponownie : Zapamiętaj wyniki. Łatwo. Zamienia wszystkie obliczenia na obliczenia wstępne, jeśli to możliwe / konieczne. To jest decyzja algorytmiczna. To nie jest wymuszone ograniczenie języka.

8. Przekazywanie sufiksu łańcucha jest łatwiejsze / możliwe przy zakończeniu NUL. W zależności od sposobu implementacji prefiksu długości może on mieć destrukcyjny wpływ na oryginalny ciąg, a czasem nawet może nie być możliwy. Wymaganie kopiowania i podanie O (n) zamiast O (1).

9. Przekazywanie / usuwanie odwołań argumentów jest mniejsze w przypadku przedrostka NUL względem prefiksu długości. Oczywiście, ponieważ przekazujesz mniej informacji. Jeśli nie potrzebujesz długości, oszczędza to dużo miejsca i pozwala na optymalizację.

10. Możesz oszukiwać. To naprawdę tylko wskaźnik. Kto powiedział, że musisz to przeczytać jako ciąg? Co jeśli chcesz odczytać go jako pojedynczy znak lub liczbę zmiennoprzecinkową? Co jeśli chcesz zrobić coś przeciwnego i odczytać liczbę zmiennoprzecinkową jako ciąg? Jeśli jesteś ostrożny, możesz to zrobić z rozwiązaniem NUL. Nie można tego zrobić z prefiksem długości, jest to typ danych wyraźnie różniący się od wskaźnika zwykle. Najprawdopodobniej będziesz musiał zbudować ciąg bajt po bajcie i uzyskać długość. Oczywiście, jeśli chciałbyś mieć coś takiego jak cała liczba zmiennoprzecinkowa (prawdopodobnie ma w sobie NUL), i tak będziesz musiał czytać bajt po bajcie, ale o szczegółach decydujesz.

TL; DR Czy używasz danych binarnych? Jeśli nie, zakończenie NUL pozwala na większą swobodę algorytmiczną. Jeśli tak, to najważniejsza jest ilość kodu w funkcji prędkości / pamięci / kompresji. Najlepszym rozwiązaniem może być połączenie dwóch podejść lub zapamiętywanie.

Nie kupuję odpowiedzi „C nie ma łańcucha”. To prawda, że ​​C nie obsługuje wbudowanych typów wyższego poziomu, ale nadal możesz reprezentować struktury danych w C i taki jest ciąg. Fakt, że ciąg znaków jest tylko wskaźnikiem w C, nie oznacza, że ​​pierwsze N ​​bajtów nie może mieć specjalnego znaczenia jako długość.

Programiści Windows / COM będą bardzo dobrze zaznajomieni z dokładnie takim BSTRtypem - ciągiem C z przedrostkiem długości, w którym rzeczywiste dane znakowe nie zaczynają się od bajtu 0.

Wydaje się więc, że decyzja o zastosowaniu zerowego zakończenia jest po prostu tym, co ludzie wolą, a nie koniecznością języka.

gcc akceptuje poniższe kody:

char s [4] = "abcd";

i jest ok, jeśli traktujemy jako tablicę znaków, ale nie ciąg znaków. Oznacza to, że możemy uzyskać do niego dostęp za pomocą s [0], s [1], s [2] i s [3], a nawet za pomocą memcpy (dest, s, 4). Ale dostaniemy niechlujne postacie, gdy spróbujemy z putami (s), lub gorzej ze strcpy (dest, s).