Dlaczego łańcuchy zakończone znakiem NUL? Lub: null zakończone vs. przechowywania znaków + długość

Question

Piszę interpreter języka w C, a moja string typ zawiera atrybut length, tak:

struct String 
{ 
    char* characters; 
    size_t length; 
}; 

Z tego powodu muszę wydać dużo czasu w moim tłumaczu obsługującym ten rodzaj ciągu ręcznie, ponieważ C nie zawiera wbudowanej obsługi tego. Zastanawiałem się nad przejściem na proste zakończone znakiem NUL tylko po to, aby spełnić podstawowe C, ale wydaje się, że istnieje wiele powodów, aby nie:

Sprawdzanie granic jest wbudowane, jeśli używasz "długość" zamiast szukanie zerowej wartości.

Musisz przemierzyć cały ciąg, aby znaleźć jego długość.

Musisz wykonać dodatkowe czynności, aby obsłużyć pusty znak w środku zakończonego znakiem NUL łańcucha.

Łańcuchy zakończone znakiem zakończonym znakiem NUL słabo radzą sobie z kodowaniem Unicode.

Ciągi, które nie są zakończone znakiem NULL, mogą obsługiwać więcej, tzn. Znaki "Hello, world" i "Hello" mogą być przechowywane w tym samym miejscu, tylko o różnych długościach. Nie można tego zrobić z łańcuchami zakończonymi znakiem NUL.

Wycinek łańcucha (uwaga: ciągi są niezmienne w moim języku). Oczywiście drugi jest wolniejszy (i bardziej podatny na błędy: pomyśl o dodaniu do obu funkcji sprawdzania błędów dla begin i end. Zastanawiam się dlaczego C ich używa:

struct String slice(struct String in, size_t begin, size_t end) 
{ 
    struct String out; 
    out.characters = in.characters + begin; 
    out.length = end - begin; 

    return out; 
} 

char* slice(char* in, size_t begin, size_t end) 
{ 
    char* out = malloc(end - begin + 1); 

    for(int i = 0; i < end - begin; i++) 
     out[i] = in[i + begin]; 

    out[end - begin] = '\0'; 

    return out; 
} 

Po tym wszystkim, moje myślenie o tym, czy nie powinno się używać ciągi zerowych jest zakończone!

Moje pytanie brzmi: czy są jakieś korzyści z zerowego rozwiązania, którego mi brakuje?

Answer 1

Zazwyczaj rozwiązaniem jest wykonanie obu tych funkcji - zachowanie długości i zachowanie terminatora zerowego. To niewiele więcej pracy i oznacza, że ​​zawsze jesteś gotowy, aby przekazać ciąg do dowolnej funkcji.

Ciągi zakończone znakami zakończonymi znakami zakończonymi znakami zakończonymi znakiem Null są często przyczyną utraty wydajności, z oczywistych powodów, że czas potrzebny na wykrycie długości zależy od długości. Po stronie dodatniej są one standardowym sposobem reprezentowania ciągów w C, więc nie masz wielkiego wyboru, jak tylko je wspierać, jeśli chcesz korzystać z większości bibliotek C.

Answer 2

Myślę, że głównym powodem jest to, że standard nie mówi nic konkretnego o rozmiarze innego niż char. Ale sizeof (char) = 1 i to zdecydowanie za mało dla rozmiaru łańcucha.

Answer 3

Jedną z korzyści jest to, że w przypadku zakończenia zerowego każdy ogon ciągu zakończonego zerem jest również łańcuchem zakończonym znakiem NUL. Jeśli musisz przekazać podłańcuch zaczynający się od N-tego znaku (pod warunkiem, że nie ma przepełnienia bufora) do jakiejś funkcji obsługi ciągów - nie ma problemu, po prostu podaj tam adres dodatkowy. Przechowując rozmiar w inny sposób, musisz skonstruować nowy ciąg znaków.

Answer 4

Mimo że preferuję metodę array + len w większości przypadków, istnieją uzasadnione powody, dla których zakończono wartością NUL.

Weź system 32-bitowy.

do przechowywania Ciąg 7 bajta
char * + size_t + 8 bajtów = 19 bajtów

do przechowywania 7 bajta null utrzymujące Ciąg
char * + 8 = 16 bajtów.

tablice bezterminowe nie muszą być niezmienne, jak robią to twoje struny. Mogę szczęśliwie skrócić ciąg znaków, umieszczając po prostu pusty znak. Jeśli kodujesz, będziesz musiał utworzyć nowy ciąg, który wiąże się z przydzielaniem pamięci.

W zależności od wykorzystania ciągów, struny nigdy nie będą w stanie dorównać wydajności możliwej za pomocą ciągów c w przeciwieństwie do ciągów.

Answer 5

Długości też mają swoje problemy.

• Długość zajmuje dodatkowe miejsce do przechowywania (obecnie nie jest to problem, ale duży czynnik 30 lat temu).

• Za każdym razem, gdy zmieniasz ciąg znaków, musisz aktualizować długość, aby zmniejszyć wydajność całej płyty.

• Za pomocą łańcucha zakończonego znakiem NUL można nadal używać długości lub przechowywać wskaźnik do ostatniego znaku, więc jeśli wykonujesz wiele operacji na łańcuchach, możesz nadal być równy wydajności string-length-length.

• Łańcuchy zakończone znakiem NUL są znacznie prostsze - terminator NUL jest po prostu konwencją używaną przez metody takie jak strcat do określenia końca ciągu znaków. Możesz więc przechowywać je w zwykłej tablicy char, zamiast korzystać z struct.

Answer 6

Wystarczy wyrzucając kilka hypotheticals:

• nie ma sposobu, aby dostać "złego" Wdrożenie null zakończone sznurki. Standaryzowana struktura może jednak zawierać implementacje specyficzne dla danego dostawcy.
• nie są wymagane żadne struktury. Ciągi zakończone znakiem Null są "wbudowane", że tak powiem, dzięki temu, że są szczególnym przypadkiem znaku *.

Answer 7

Od Joel Back to Basics:

Dlaczego smyczki C działa w ten sposób? Ponieważ mikroprocesor PDP-7, na którym wynaleziono język programowania UNIX i C, miał typ ASCIZ. ASCIZ oznaczało "ASCII z Z (zero) na końcu."

Czy to jedyny sposób na przechowywanie ciągów? Nie, w rzeczywistości jest to jeden z najgorszych sposobów przechowywania łańcuchów. W przypadku nietrywialnych programów, interfejsów API, systemów operacyjnych, bibliotek klas należy unikać ciągów ASCIZ, takich jak dżuma.

Answer 8

Jedną zaletą strun nul zakończone jest to, że jeśli idziesz przez ciąg znaków po znaku, tylko trzeba zachować pojedynczy wskaźnik, aby zająć się napis:

while (*s) 
{ 
    *s = toupper(*s); 
    s++; 
} 

natomiast dla ciągi bez strażników, trzeba zachować dwa bity stanu wokół: albo wskaźnik i indeks:

while (i < s.length) 
{ 
    s.data[i] = toupper(s.data[i]); 
    i++; 
} 

... albo aktualny wskaźnik i limit:

s_end = s + length; 
while (s < s_end) 
{ 
    *s = toupper(*s); 
    s++; 
} 

Gdy rejestry CPU były rzadkim zasobem (i kompilatory były gorsze w przydzielaniu ich), było to ważne. Teraz nie tak bardzo.

Answer 9

Masz całkowitą rację, że zakończenie 0 to metoda, która jest słaba w odniesieniu do sprawdzania typu i wydajności dla części operacji. Odpowiedzi na tej stronie już zawierają podsumowanie źródeł i zastosowań.

Podobał mi się sposób, w jaki Delphi zapisywała ciągi. Uważam, że zachowuje długość/maksymalną długość przed ciągiem (o zmiennej długości). W ten sposób łańcuchy mogą być zakończone zerem dla zgodności.

Moje obawy dotyczące mechanizmu: - dodatkowy wskaźnik - niezmienność si w podstawowych częściach języka; zwykle typy łańcuchów nie są niezmienne, więc jeśli kiedykolwiek się zastanowisz, to będzie ciężko. Musiałbyś zaimplementować mechanizm "stwórz kopię na zmianę" - użycie malloc (mało efektywny, ale może być tu zawarty tylko dla ułatwienia?)

Powodzenia; pisanie własnego tłumacza może być bardzo pouczające w zrozumieniu głównie gramatyki i składni języków programowania! (przynajmniej dla mnie to)

Answer 10

Nieco offtopic, ale jest bardziej efektywny sposób na wykonywanie ciągów o długości z prefiksem, niż opisujesz. Tworzenie struct jak to (ważne w C99 i górę):

struct String 
{ 
    size_t length; 
    char characters[0]; 
} 

To tworzy struct, który ma długość na starcie, z elementem do "bohaterów użytkowej jako char * tak samo jak z prądem struct. Różnica polega jednak na tym, że można przydzielić tylko jeden element na stercie dla każdego ciągu, zamiast dwóch. Przeznaczyć swoje struny tak:

mystr = malloc(sizeof(String) + strlen(cstring)) 

Np - długość struct (które jest po prostu size_t) oraz wystarczająco dużo miejsca, aby umieścić rzeczywisty ciąg po niej.

Jeśli nie chcesz używać C99, możesz to również zrobić za pomocą "znaków char [1]" i odjąć 1 od długości łańcucha do przydzielenia.