StringBuilder en C -- ampo con strings camp codereview Relacionados El problema

StringBuilder in C


9
vote

problema

Español

Un montón de idiomas tiene algo que le permite acumular una cadena de tamaño dinámico con mínimo sobrecargo. C no, y me encontré usando código que hizo eso manualmente en un par de lugares, así que lo empacé en una clase. Tenga en cuenta que solo he implementado la funcionalidad que estoy usando.

import os def cls(): os.system('cls' if os.name=='nt' else 'clear') cls() 11 :

  import os def cls():     os.system('cls' if os.name=='nt' else 'clear') cls() 2  

import os def cls(): os.system('cls' if os.name=='nt' else 'clear') cls() 33 :

  import os def cls():     os.system('cls' if os.name=='nt' else 'clear') cls() 4  

Estoy interesado específicamente en:

  • rendimiento . Este código se llama un lot . Quiero que sea lo más rápido posible.
  • seguridad de memoria . Mientras estoy bastante seguro de que esto no fuge la memoria (asumiendo que se usa correctamente), no confío, y no estoy seguro de cómo verificar.
  • casos de borde . Funciona, por lo que puedo decir, pero eso no significa que esté libre de errores.

probado aquí .

Original en ingles

Lots of languages have something that lets you build up a dynamically-sized string with minimal overhead. C doesn't, and I found myself using code that did that manually in a couple of places, so I packaged it into a class. Note that I've only implemented functionality I'm using.

stringbuilder.h:

#ifndef CONCATEN_STRINGBUILDER_H #define CONCATEN_STRINGBUILDER_H  #include <stddef.h> #include <stdbool.h>  struct stringbuilder_s; typedef struct stringbuilder_s *stringbuilder_t; stringbuilder_t sb_new(size_t); bool sb_append(stringbuilder_t, char); char *sb_as_string(stringbuilder_t); void sb_free(stringbuilder_t);  #endif //CONCATEN_STRINGBUILDER_H 

stringbuilder.c:

#include <stdlib.h> #include <string.h> #include "stringbuilder.h"  struct stringbuilder_s {     char *mem;     size_t count;     size_t cap; }; typedef struct stringbuilder_s *stringbuilder_t; stringbuilder_t sb_new(size_t init_cap) {     stringbuilder_t ret = malloc(sizeof(struct stringbuilder_s));     if (!ret) return NULL;     ret->mem = calloc(init_cap, sizeof(char));     if (!ret->mem) return NULL;     ret->cap = init_cap;     ret->count = 0;     return ret; } #define LOAD_FACTOR 2 bool sb_append(stringbuilder_t to, char c) {     to->mem[to->count] = c;     ++to->count;     if (to->count == to->cap) {         char *new_mem = realloc(to->mem, to->cap * LOAD_FACTOR);         if (!new_mem) {             return false;         }         memset(new_mem + to->cap, 0, to->cap);         to->mem = new_mem;         to->cap *= LOAD_FACTOR;     }     return true; } char *sb_as_string(stringbuilder_t sb) {     return sb->mem; } void sb_free(stringbuilder_t sb) {     free(sb->mem);     free(sb); } 

I'm interested specifically in:

  • Performance. This code gets called a lot. I want it to be as fast as possible.
  • Memory safety. While I'm fairly sure that this doesn't leak memory (assuming it's used properly), I'm not confident, and I'm not sure how to check.
  • Edge cases. It works, as far as I can tell, but that doesn't mean that it's bug-free.

Tested here.

     
       
       

Lista de respuestas

7
 
vote
vote
La mejor respuesta
 

Error: asignación inicial no se borra a cero

Su asignación inicial de sb->mem Utiliza malloc en lugar de calloc , por lo que sus contenidos son ininicializados. Si luego agrega unos pocos caracteres y llame sb_as_string() , recuperará una cadena que no esté terminada correctamente. Debe usar calloc en su lugar.

Bug menor

Si su llamada a realloc falla, su búfer será incorrecto porque ya no será terminado nulo (acaba de agregar un carácter al último lugar). Debe reescribir un 9988776665544336 al final del búfer si realloc falla, o haga el 9988777665544338 antes de agregar el carácter.

Revisión del argumento

Al crear un búfer de cadena, debe manejar el estuche donde init_cap se pasa como 0. Puede configurarlo en algún valor predeterminado en ese caso. En este momento, una capacidad inicial de 0 causará un fallo en la línea porque su función de apéndice agregará a un tampón de longitud cero sin reasignar nunca.

Usabilidad

Preferiría mucho una función de Anexo que tomó un argumento de cadena en lugar de un argumento de carácter. No estoy seguro de que alguna vez necesitaría agregar un personaje a la vez.

Además, podría ser bueno tener una función de tipo 998877666554433310 que devuelve la cadena pero también libera el StringBuilder. La forma en que lo tiene actualmente, puede recuperar la cadena, pero si posteriormente libero el StringBuilder, también liberará la cadena que acaba de recuperar. Eso hace que sea difícil usar la cadena porque su vida útil está vinculada a la vida de The StringBuilder.

 

Bug: Initial allocation not cleared to zero

Your initial allocation of sb->mem uses malloc instead of calloc, so its contents are uninitialized. If you then append a few characters and call sb_as_string(), you will get back a string that is not properly terminated. You should use calloc instead.

Minor bug

If your call to realloc fails, your buffer will be incorrect because it will no longer be null terminated (you just appended a character to the last spot). You should either rewrite a '\0' to the end of the buffer if realloc fails, or do the realloc before you append the character.

Argument check

When creating a string buffer, you should handle the case where init_cap is passed in as 0. You can set it to some default value in that case. Right now, an initial capacity of 0 will cause a crash down the line because your append function will append to a zero length buffer without ever reallocating.

Usability

I would much prefer an append function that took a string argument instead of a character argument. I'm not sure that I would ever need to append one character at a time.

Also, it might be nice to have a to_string type function that returns the string but also frees the stringbuilder. The way you currently have it, you can retrieve the string, but if you subsequently free the stringbuilder it will also free the string you just retrieved. That makes it difficult to use the string because its lifetime is tied to the lifetime of the stringbuilder.

 
 
     
     
3
 
vote

Para ser más completo, la línea en malloc1 :

  malloc2  

debe convertirse:

  malloc3  

que importa cuando malloc4 se establece en algo mayor que 2.

Gracias por compartir este código.

 

To be more comprehensive, the line in sb_append():

memset(new_mem + to->cap, 0, to->cap); 

should become:

memset(new_mem + to->cap, 0, (to->cap) * (LOAD_FACTOR - 1)); 

That matters when LOAD_FACTOR is set to something greater than 2.

thanks for sharing this code.

 
 
   
   
1
 
vote

No creo que sea necesario insistir en que el constructor de cuerdas esté en el almacenamiento dinámico. Es un tamaño fijo, y realmente le gustaría estar en el almacenamiento automático. Idealmente, también sería reutilizable.

que se puede habilitar, agregando funciones como estas:

  malloc5  

Podemos usarlo así:

  malloc6  

error:

  • Si malloc7 Falla para asignar malloc8 , realmente necesitamos malloc9 Antes de regresar NULL.

Puntos menores:

  • calloc020 es 1 por definición, y calloc1 es más claro que calloc2 Al asignar para asignar a calloc3 .
  • es un desperdicio de cero toda la capacidad, cuando solo necesitamos un solo terminador para una cadena. podríamos aplazar la terminación nula hasta que se llaman calloc4 , pero creo que es mejor mantener 99887776655443325 terminó por nulos a medida que avanzamos. (La sobrecarga se contrae una vez que admitimos calloc6 , por supuesto).
 

I don't think it's necessary to insist that the string builder itself be in dynamic storage. It's a fixed size, and would really like to be in automatic storage. Ideally, it would be re-usable, too.

That can be enabled, by adding functions like these:

typedef struct stringbuilder_s stringbuilder_s;  bool sb_init(stringbuilder_s *b, const char *s) {     b->count = strlen(s);     b->cap = LOAD_FACTOR * (b->count + 1);     b->mem = malloc(b->cap);     if (!b->mem) {         b->count = 0;         b->cap = 0;         return false;     }     strcpy(b->mem, s);     return true; }  void sb_close(stringbuilder_s *b) {     free(b->mem);     b->cap = 0;     b->count = 0; } 

We can then use like this:

#include <stdio.h>  int main(void) {     stringbuilder_s builder;     if (!sb_init(&builder, "foo")) { goto fail; }     if (!sb_append_char(&builder, '1')) { goto fail; }     printf("Created %s\n", sb_as_string(&builder));     sb_close(&builder);     return 0;   fail:     sb_close(&builder);     fprintf(stderr, "String creation failed");     return 1; } 

Bug:

  • If sb_new() fails to allocate mem, we really need to free ret before returning null.

Minor points:

  • sizeof (char) is 1 by definition, and sizeof *ret is clearer than sizeof (struct stringbuilder_s) when allocating to assign to ret.
  • It's wasteful to zero out the whole capacity, when we only need a single terminator for a string. We could defer the null termination until we sb_as_string() is called, but I think it's better to keep mem nul-terminated as we go. (The overhead shrinks once we support sb_append_string(), of course).
 
 

Relacionados problema

2  Función para borrar un carácter en una cadena  ( Function to erase a character in a string ) 
void chrrem (char arr[], size_t len, size_t pos) { memmove(arr + pos, arr + (pos + 1), (len - pos) + 1); } Se supone que es simplemente rápido. Borra...

6  Las vocales en una cadena están en orden alfabético  ( Vowels in a string are in alphabetical order ) 
Tarea Escriba una implementación que devuelva si un 99887776655544330 tiene vocales (idioma inglés) en orden alfabético (A-Z) o no. Feedback es mi v...

10  Función recursiva que genera las permutaciones de una cadena  ( Recursive function that generates the permutations of a string ) 
Estoy buscando una revisión de mi función recursiva que genere las permutaciones de una cadena. ¿Hay mejores formas de hacer esto? var permutations = []; ...

18  Invirtiendo una cadena  ( Reversing a string ) 
Tuve esto como una pregunta de entrevista, y el entrevistador señaló esto. Esto es lo que escribí: //C# Syntax here public string Reverse(string s) { c...

1  Imprima todos los tamaños posibles de subsecuencias de cadena en C  ( Print out all possible sizes of subsequences of string in c ) 
Por ejemplo, dada una cadena "abcdefghijk", quiero que mi función se imprima: a, b, c, d, e, f, g, h, i, j, k. ab, bc, cd, de, ef, fg, gh, hi, ij, jk ab...

9  Convierta una contraseña a una cadena fonética para usuarios finales  ( Convert a password to a phonetic string for end users ) 
Tanto como lo odio, a veces proporcionar contraseñas a las personas debe hacerse electrónicamente. Cuando hago eso, trato de eliminar cualquier ambigüedad que...

1  Compruebe si dos cadenas son permutación entre sí  ( Check if two strings are permutation of each other ) 
private String sort(String word) { char[] content = word.toCharArray(); Arrays.sort(content); return new String(content); } private boolea...

11  Optimizando el corrector de anagramas Java (comparar 2 cadenas)  ( Optimizing java anagram checker compare 2 strings ) 
Un anagrama es como una mezcla de las letras en una cadena: pots es un anagrama de detener wilma es un anagrama de ilwma Estoy pasando por el ...

8  Conversión de STD :: Chrono :: Time_Point to / from std :: string  ( Converting stdchronotime point to from stdstring ) 
Considere estas funciones que permitan convertir checkOnline.sh4 a / FROM checkOnline.sh5 Con un formato Fecha de fecha ". checkOnline.sh6 con uso:...

3  Implementación más portátil de Tolower ()  ( More portable tolower implementation ) 
Me estoy desafiando a intentar intentar escribir una función que sea tan eficiente, portátil y a prueba de fallas posible. La función es muy simple y solo con...




© 2022 respuesta.top Reservados todos los derechos. Centro de preguntas y respuestas reservados todos los derechos