Una clase String

9.3.2 Manejo de cadenas alfanuméricas

Una clase String

Se muestra el esquema de una clase String pensada para manejar matrices de caracteres, que también puede manejar matrices C. Se desea dotarla de un álgebra capaz de realizar las siguientes operaciones:

String s1 = "Matriz-C"; // L1: creación desde matriz-C

String s1 = 'X'; // L2: cración desde carácter

String s1; // L3: Strin vacío de tamaño inicial por defecto

String s1(size); // L4: String vacío de tamaño inicial determinado

String s1 = s2; // L5: constructor-copia

s1 = s2; // L6: asignación

s1 = 'X'; // L7: asignar carácter

s1 = "AEIOU"; // L8: asignar matriz-C

s1 = s2 + s3; // L9: suma

s1 = s2 + "AEIOU"; // L10: suma con matriz-C

s1 = s2 + 'X'; // L11: suma con carácter

char c = s2[n]; // L12: obtener elemento enésimo

s1 = s2.substr(m,n); // L13: obtener substring

s1 == s2 // L14: igualdad

s1 != s2 // L15: desigualdad

s1 < s2 // L16: menor que

s1 <= s2 // L17: menor o igual

s1 > s2 // L18: mayor que

s1 >= s2 // L19: mayor o igual

La clase String almacena los datos en el montón ( 1.3.2) y para evitar en lo posible los problemas de fragmentación de memoria, el String será capaz de albergar un cierto número de caracteres antes de necesitar una reubicación. Cada vez que sea necesaria una nueva asignación, se duplicará el espacio actual en una secuencia 16, 32, 64, 128, 256, 512, 1024 etc. caracteres. El tamaño inicial por defecto es de 16 caracteres, aunque este valor puede ser modificado fácilmente.

Para evitar problemas de desbordamiento, también se ha limitado el tamaño máximo superior del String que puede crearse inicialmente, o que resulte de una composición (operación de suma). Como complemento se dispone de varios métodos auxiliares que permiten controlar ciertos aspectos de los objetos de la clase.

§1 Interfaz

La interfaz de la clase es como sigue:

// Una clase String

#define MAXSIZE LONG_MAX

#define MINSIZE 16
#define NULO '\0'

#define CTD unsigned long

class String {
public:
    String();                 nbsp; // C-1 constructor por defecto
    String(CTD);                // C-2 construir tamaño especificado
    String(const char&);        // C-3 construir a partir de caracter
    String(const char*);        // C-4 construir a partir de una matriz C.
    String(String&);            // C-5 constructor-copia
    String& operator= (const String&);   // = asignar cadena
    String operator+(const String&);     // + Concatenar cadenas

    bool operator==(cons String&);       // == igualdad
    bool operator!=(cons String&);       // != desigualdad
    bool operator<(cons String&);        // < menor que
    bool operator>=(cons String&);       // >= mayor o igual
    bool operator>(cons String&);        // > mayor que
    bool operator<=(cons String&);       // <= menor o igual

    char operator[](CTD);       // subindice
    ~String() { delete cptr; } // destructor
    void show();
    CTD len() { return ln; }

    CTD maxLen() { return size; }
    String substr(CTD, CTD);
private:
    CTD getSize(CTD);
    void fillN();
    char* cptr;                 // puntero a contenido
    CTD ln;                      // ocupado (0 = vacio; maximo = size)
    CTD size;                  // tamaño (real en caracteres)
};

El almacenamiento total viene determinado por la propiedad size. La zona realmente ocupada (en caracteres) se refleja en ln. La condición ln == size representa la máxima utilización del espacio asignado. A partir de este momento el crecimiento del String exige una reubicación con asignación de un nuevo espacio y liberación del antiguo, operación que es efectuada automáticamente por los algoritmos correspondientes.

En lo sucesivo, las referencias a contenido se refieren a la zona que contiene datos útiles. El resto se completa con caracteres nulos; esta operación está encomendada al método fillN() .

Aparte de constructores; destructor; operadores y otros métodos privados auxiliares, la clase tiene varios métodos públicos:

show(): Mostrar tamaño total; espacio utilizado (en caracteres) y contenido
len(): Obtener el espacio ocupado .
maxLen(): Obtener el espacio total .
substr(int, int): Obtener una subcadena .

§2 Constructor por defecto:

String::String(){ // C-1 constructor por defecto
size = 0;
cptr = new char[getSize(1)];
ln = 0; fillN();
}

Este constructor es responsable de que sean posibles expresiones como L3 . El tamaño por defecto viene determinado por el método getSize(), que a su vez lo toma de la constante MINSIZE. El método fillN( ) se encarga de borrar contenido previo del espacio asignado rellenándolo con el carácter determinado por la constante NULO.

§3 Construir con tamaño inicial determinado:

String::String(CTD n){             // C-2 objeto vacío de tamaño inicial determinado
if (n == 0UL || n > MAXSIZE) {
    cptr = NULL; size = 0UL; ln = 0UL;
} else if (n == 1) {
    cptr = new char[1];
    *cptr = NULO;
    size = 1; ln = 0;
} else {
    n = n < 0? MINSIZE: n;
    size = n;
    cptr = new char[size];
    ln = 0; fillN();
}
}

Este constructor hace posibles expresiones como L4 . Si el tamaño solicitado es cero o mayor que el permitido, se crea un objeto String nulo (sin espacio de almacenamiento). Si el tamaño inicial es 1, se crea un objeto String unitario (con almacenamiento para un carácter y contenido nulo). Finalmente, si el tamaño solicitado es menor que el mínimo, se adopta el valor establecido por la constante MINSIZE. En caso contrario, el espacio de almacenamiento es el indicado.

String s1(1UL); // String unitario

String s0(0UL); // String nulo

Nota: Los sufijos UL ( 3.2.3b) son necesarios para evitar ambigüedad con el constructor C-3: String::String(const char&) en todas las situaciones en que se invoque implícita o explícitamente este constructor utilizando constantes numéricas.

§4 Constructor desde carácter:

String::String(const char& ch) { // C-3 constructor desde caracter
size = 1;
cptr = new char[getSize(1)];
*cptr = ch;
ln = 1; fillN();
}

Como se indica en la sentencia L2 , queremos poder construir un String unitario con el contenido de un carácter, este constructor construye un objeto String de tamaño unidad conteniendo el carácter tomado como modelo. En realidad actúa también como constructor-conversor en todas las situaciones donde el contexto exija al compilador convertir un const char a String. Su presencia garantiza que se puedan realizar también conversiones explícitas del tipo:

s1 = static_cast<String>('X');

§5 Constructor desde matriz "C":

String::String(const char* pt) { // C-4 constructor desde una matriz C
ln = ::strlen(pt)+1; // espacio para el nulo final
size = 0;
cptr = new char[getSize(ln)];
::strcpy(cptr, pt);
fillN();
}

En realidad es un constructor-copia que crea un objeto String a partir de una matriz al estilo clásico C ( 3.2.3f). Es decir, una cadena alfanumérica terminada en un carácter nulo y definida mediante un puntero-a-carácter. Su presencia garantiza que se puedan realizar asignaciones del tipo:

String sc = "Hola Mundo";

Observe que la utilización de las funciones de Librería strlen y strcpy exige que la cadena no contenga caracteres nulos intercalados. Y que a semejanza del anterior, actúa también como constructor-conversor en todas las situaciones donde el contexto exija al compilador convertir una cadena de caracteres constantes a String (por ejemplo en la sentencia L10 ). Su presencia garantiza que puedan utilizarse conversiones explícitas:

s1 = static_cast<String>("Lo he convertido");

§6 Constructor-copia

String::String(String& st) { // C-5 constructor-copia
ln = st.len();
size = 0;
cptr = new char[getSize(ln)];
for (register CTD i=0; i<ln; i++) *(cptr+i) = *(st.cptr+i);
fillN();
}

Es el clásico constructor-copia que obtiene un objeto String a partir de un modelo (sentencia L5 ). Observe que el criterio seguido incluye la creación de un nuevo objeto. No se trata por tanto de utilizar un nuevo "handle" para acceder al objeto ya existente. El modelo y el objeto resultante tienen existencias totalmente independientes.

§7 Operador de asignación:

String& String::operator= (const String& st) { // = asignar String
if (cptr == st.cptr) {   // evitar s = s;
    return *this;
}
if (size < st.ln) {      // nuevo espacio
    char* nptr = new char[getSize(st.ln)];
    for (register CTD i=0; i<st.ln; i++) *(nptr+i) = *(st.cptr+i);
    delete cptr; cptr = nptr; ln = st.ln;
} else {                 // usar espacio actual
    for (register CTD i=0; i<st.ln; i++) *(cptr+i) = *(st.cptr+i);
    ln = st.ln;
}
fillN();
return *this;
}

Esta versión sobrecargada del operador de asignación = para objetos String permite realizar operaciones del tipo:

s1 = s2;

Se utiliza un criterio conservativo de memoria, usando el almacenamiento actual del Lvalue si el Rvalue puede alojarse en él. En caso de tener que realizarse una reubicación, el espacio anterior es devuelto al montón.

§8 Operador suma:

String String::operator+(const String& st) { // + concatenar Strings
CTD sza = size;
String sx(getSize(ln+st.ln)); // String auxiliar para el resultado

// incluir captura del posible error producido por getSize

// si el tamaño resultante excede del máximo
register CTD i;
for (i=0; i<ln; i++) *(sx.cptr+i) = *(cptr+i);
for (i=0; i<st.ln; i++) *(sx.cptr+i+ln) = *(st.cptr+i);
size = sza;
sx.ln = ln + st.ln;
return sx;
}

Esta versión sobrecargada de la función operator+() permite expresiones como las señaladas en L9 . En realidad se trata de una concatenación de Strings. El objeto resultante de la operación s1 + s2 incluye el contenido del operando izquierdo seguido del contenido del operando derecho:

String s1 = "AEIOU";

String s2 = "aeiou";

s1 + s2; // AEIOU aeiou

Observe que esta "suma" no es conmutativa (los operadores relacionales son proporcionados también)

s1 + s2 != s2 + s1

Pero si asociativa por la derecha y por la izquierda:

s1 + s2 + s3 == s1 + (s2 + s3) == (s1 + s2) + s3.

§9 Operador subíndice:

char String::operator[](CTD n) { // subindice
if (n<0 || n >= ln) return '\0';
return *(cptr+n);
}

Esta versión de operator[ ] permite obtener el carácter correspondiente al elemento enésimo de un objeto String (sentencia L12 ). Para mayor simplicidad se ha seguido el criterio de que si el argumento n está fuera de rango se devuelva el carácter nulo. Esto puede ser fácilmente modificado para que devuelva cualquier otro carácter; un mensaje de error o una excepción.

Nota: Si se desea obtener un objeto String, debe utilizarse el método substr(n,n).

§10 Operadores relacionales

Igualdad:

bool String::operator==(const String& st) { // == operador de igualdad
if (ln != st.ln) return false;
for (register CTD i=0; i<ln; i++) {
if (*(cptr+i) != *(cptr+i)) return false;
}
return true;
}

El criterio para que dos objetos sean iguales es que tengan la misma longitud ln (no importa que sus respectivos almacenamientos sean de tamaño distinto), y que los contenidos de los dos objetos sean iguales miembro a miembro. En todos los demás casos el operador devuelve falso.

Este operador permite realizar comparaciones entre objetos de la clase String:

if (s1 == "ABCDE") cout << "Iguales!!\n";

if (s1 == 'A') cout << "Iguales!!\n";

if (s1 == s2) cout << "Iguales!!\n";

Menor-que:

bool String::operator<(const String& st) {       // < menor que
CTD min = ln < st.ln? ln: st.ln;      // longitud del menor
for (register CTD i=0; i<min; i++) {
    if (*(cptr+i) > *(st.cptr+i)) return false;
    else if (*(cptr+i) < *(st.cptr+i)) return true;
}
// iguales en la parte comun
if (ln == st.ln) return false;        // misma longitud
return (ln < st.ln? true: false);
}

El criterio para que un String sea menor que otro, es que la palabra contenida en él aparezca antes en el diccionario (suponiendo una ordenación según la tabla de caracteres ASCII). Se utiliza el criterio de comparación de caracteres c1 < c2 y c1 > c2 preconstruido en el lenguaje para los tipos char. La longitud de la palabra solo tiene influencia si la parte común de ambas coincide. En este caso, la más corta se considera menor. Ejemplo:

"1234567890" < "1234567890 "

"1234567891" > "1234567890 "

Mayor-que:

bool String::operator>(const String& st) {       // > mayor que
CTD min = ln < st.ln? ln: st.ln;      // longitud del menor
for (register CTD i=0; i<min; i++) {
    if (*(cptr+i) < *(st.cptr+i)) return false;
    else if (*(cptr+i) > *(st.cptr+i)) return true;
}

// iguales en la parte común
if (ln == st.ln) return false; // misma longitud
return (ln < st.ln? false: true);
}

El criterio para que un String sea mayor que otro es justamente inverso al anterior: que la palabra contenida en él aparezca después en el diccionario suponiendo una ordenación de caracteres ASCII estándar. La longitud de palabra solo tiene influencia si la parte común de ambas coincide. En este caso, la palabra más larga se considera mayor.

Para evitar definiciones redundantes de los operadores se definen:

bool String::operator!=(const String& st) { // != operador de desigualdad
return !(*this == st);
}

bool String::operator>=(const String& st) { // >= mayor o igual
return !(*this < st);
}

bool String::operator<=(const String& st) { // <= menor o igual
return !(*this > st);
}

§11 Obtener un sub-String:

String String::substr(CTD ini, CTD fin) { // Obtener substring
if (ini<0 || ini>fin ) {   // argumento fuera de límites
    String s0(0UL);
    return s0;
}
// si el límite superior excede el contenido, se copia la totalidad

fin = fin >= ln? ln-1: fin;
CTD sz = fin-ini+1;
String sr(sz);
for (register CTD i=0; i<sz; i++) *(sr.cptr+i) = *(cptr+i+ini);
sr.ln = sz;
return sr;
}

El método substr(ini, fin) permite obtener un objeto String cuyo contenido es una porción de otro entre dos valores inicial y final (inclusive), determinados por los argumentos ini y fin (sentencia L13 ). Observe que el valor cero corresponde al elemento inicial y el valor len()-1 corresponde al último elemento. Así pues, la expresión:

s.substr(0, s.len()-1);

devuelve la totalidad del contenido de s.

Se ha seguido el criterio de que si el límite inicial ini está fuera de rango, o el rango es inadecuado (ini > fin), se devuelve un objeto String nulo (de tamaño 0 sin espacio de almacenamiento). Por contra, si el límite superior fin excede del rango, se devuelve desde la posición ini hasta el final. Este comportamiento puede ser fácilmente modificado para cubrir otras necesidades. Por ejemplo, lanzar una excepción.

§12 Mostrar contenido:

Se dispone de un método público que permite mostrar tamaño total; espacio utilizado (en caracteres) y contenido

void String::show() {
std::cout << ln << " de " << size << " caracteres; String: ";
for (register CTD i=0; i<ln; i++) std::cout << *(cptr+i);
std::cout << std::endl;
}

Ejemplo:

String s1 = "Hola mundo";

s1.show();

Salida:

11 de 16 caracteres; String: Hola mundo

§12 Espacio utilizado y tamaño total:

Para evitar en lo posible la fragmentación, y salvo indicación explícita en contrario, la asignación de memoria para objetos String sigue un esquema de progresión geométrica a partir de un valor mínimo hasta el valor máximo permitido. Existen dos métodos públicos que permiten obtener (en caracteres) el tamaño total reservado y el realmente ocupado:

CTD maxLen() { return size; }

Devuelve el espacio total de almacenamiento reservado en el montón. Este valor puede ser cero para los objetos String "nulos" (creados sin espacio de almacenamiento).

CTD len() { return ln; }

Devuelve el espacio realmente ocupado dentro del total disponible. Los valores devueltos pueden oscilar entre cero (ocupación nula) y un valor máximo maxLen() determinado en cada momento por el total de memoria disponible sin reubicación (ocupación máxima). A partir de este momento la reubicación se produce automáticamente si fuese necesaria.

Ejemplo:

String s1 = "Hola mundo";

std::cout << s1.maxLen(); // -> 16

std::cout << s1.len(); // -> 11

§13 Funciones auxiliares:

Se dispone de un método privado getSize para obtener el espacio a reservar en el montón en función de las necesidades actuales (wanted). Para evitar los problemas de fragmentación, la asignación se realiza según una escala de progresión geométrica en función del tamaño actualmente necesario. Cada vez que sea necesaria una nueva asignación, se duplicará el espacio actual en una secuencia 16, 32, 64, 128, 256, 512, 1024 etc. caracteres. El tamaño inicial por defecto es de 16 caracteres, aunque este valor puede ser fácilmente modificado. También es sencillo implementar una modificación para que a partir de un cierto tamaño el incremento no sea geométrico sino lineal.

long String::getSize(CTD wanted) { // Obtener tamaño
size = size==0? MINSIZE: size;
while (size < wanted) size *= 2;

if (size > MAXSIZE) { /* medidas de control */ }
return size;
}

Puesto que el operador new[ ] para matrices no permite inicializar el espacio reservado ( 4.9.20c), se dispone de un método privado fillN() que se encarga de iniciarlo con un valor determinado.

void String::fillN() {
for (register CTD i=ln; i<size; i++) *(cptr+i) = NULO;
}

Este método se encarga de borrar el posible contenido previo del espacio asignado rellenándolo con el carácter determinado con la constante NULO. Actualmente es el carácter nulo ( '\0' ), pero puede ser fácilmente cambiado.

§14 Código:

La definición completa de la clase:

// Una clase String. Fichero <String.h>
#define MAXSIZE LONG_MAX
#define MINSIZE 16
#define NULO '\0'
#define CTD unsigned long

class String {
public:
    String();              // constructor por defecto
    String(CTD);           // construir a tamaño especificado
    String(const char*);   // construir a partir de una matriz C.
    String(String&);       // construir a partir de otro String
    String(const char&);   // construir a partir de caracter

    String& operator= (const String&); // = asignar cadena
    String operator+(const String&);   // + Concatenar cadenas
    char operator[](CTD);              // subíndice
    bool operator==(const String&);    // igualdad
    bool operator!=(const String&);    // desigualdad
    bool operator<(const String&);     // menor que
    bool operator>=(const String&);    // mayor o igual
    bool operator>(const String&);     // mayor que
    bool operator<=(const String&);    // menor o igual
    ~String() { delete cptr; }         // destructor
    void show();
    CTD len() { return ln; }
    CTD maxLen() { return size; }
    String substr(CTD, CTD);
private:
    CTD getSize(CTD);
    void fillN();
    char* cptr;            // puntero a contenido
    CTD ln;                // ocupado (0 = vacio; maximo size)
    CTD size;              // almacenamiento (en caracteres)
};

String::String(){          // c-0 constructor por defecto
size = 0;
cptr = new char[getSize(1)];
ln = 0; fillN();
}

String::String(CTD n){     // C-1 objeto vacio de tama;o nicial determinado
if (n == 0UL || n > MAXSIZE) {
    cptr = NULL; size = 0UL; ln = 0UL;
} else if (n == 1) {
    cptr = new char[1];
    *cptr = NULO;
    size = 1; ln = 0;
} else {
    n = n < 0? MINSIZE: n;
    size = n;
    cptr = new char[size];
    ln = 0; fillN();
}
}

String::String(const char& ch) {        // C-3 constructor desde caracter
size = 1;
cptr = new char[getSize(1)];
*cptr = ch;
ln = 1; fillN();
}

String::String(const char* pt) {        // C-4 construir-copia (una matriz C).
ln = ::strlen(pt)+1;      // espacio para el nulo final
size = 0;
cptr = new char[getSize(ln)];
::strcpy(cptr, pt);
fillN();
}

String::String(String& st) {            // C-5 constructor-copia (otro String)
ln = st.len();
size = 0;
cptr = new char[getSize(ln)];
for (register CTD i=0; i<ln; i++) *(cptr+i) = *(st.cptr+i);
fillN();
}

String& String::operator= (const String& st) {   // = asignar String
if (cptr == st.cptr) {    // evitar s = s;
    return *this;
}
if (size < st.ln) {       // asignar nuevo espacio
    char* nptr = new char[getSize(st.ln)];
    for (register CTD i=0; i<st.ln; i++) *(nptr+i) = *(st.cptr+i);
    delete cptr; cptr = nptr; ln = st.ln;
} else {                  // usar espacio actual
    for (register CTD i=0; i<st.ln; i++) *(cptr+i) = *(st.cptr+i);
    ln = st.ln;
}
fillN();
return *this;
}

String String::operator+(const String& st) {     // + concatenar Strings
CTD sza = size;
String sx(getSize(ln+st.ln));   // String auxiliar para el resultado
register CTD i;
for (i=0; i<ln; i++) *(sx.cptr+i) = *(cptr+i);
for (i=0; i<st.ln; i++) *(sx.cptr+i+ln) = *(st.cptr+i);
size = sza;
sx.ln = ln + st.ln;
return sx;
}

char String::operator[](CTD n) {                 // [] subindice
if (n<0 || n >= ln) return '\0';
return *(cptr+n);
}

bool String::operator==(const String& st) {      // == igualdad
if (ln != st.ln) return false;
for (register CTD i=0; i<ln; i++) {
    if (*(cptr+i) != *(st.cptr+i)) return false;
}
return true;
}

bool String::operator!=(const String& st) {      // != desigualdad
return !(*this == st);
}

bool String::operator<(const String& st) {       // < menor que
CTD min = ln < st.ln? ln: st.ln;    // longitud del menor
for (register CTD i=0; i<min; i++) {
    if (*(cptr+i) > *(st.cptr+i)) return false;
    else if (*(cptr+i) < *(st.cptr+i)) return true;
}
if (ln == st.ln) return false;      // misma longitud
return (ln < st.ln? true: false);
}

bool String::operator>=(const String& st) {      // >= mayor o igual
return !(*this < st);
}

bool String::operator>(const String& st) {       // > mayor que
CTD min = ln < st.ln? ln: st.ln;    // longitud del menor
for (register CTD i=0; i<min; i++) {
    if (*(cptr+i) < *(st.cptr+i)) return false;
    else if (*(cptr+i) > *(st.cptr+i)) return true;
}
if (ln == st.ln) return false;      // misma longitud
return (ln < st.ln? false: true);
}

bool String::operator<=(const String& st) {      // <= menor o igual
return !(*this > st);
}

String String::substr(CTD n1, CTD n2) {          // substr()
if (n1<0 || n1>n2 ) {
    String s0(0UL);
    return s0;
}
n2 = n2 >= ln? ln-1: n2;       // copia hasta el final
CTD sz = n2-n1+1;
String sr(sz);
for (register CTD i=0; i<sz; i++) *(sr.cptr+i) = *(cptr+i+n1);
sr.ln = sz;
return sr;
}

void String::show() {                // Mostrar contenido
std::cout << ln << " de " << size << " caracteres; String: ";
for (register CTD i=0; i<ln; i++) std::cout << *(cptr+i);
std::cout << std::endl;
}

CTD String::getSize(CTD wanted) {    // función axuiliar
size = size==0? MINSIZE: size;
while (size < wanted) size *= 2;
if (size > MAXSIZE) { /* medidas de control */ }
return size;
}

void String::fillN() {               // función auxiliar
for (register CTD i=ln; i<size; i++) *(cptr+i) = NULO;
}

Comentario:

La clase es capaz de realizar todas las operaciones propuestas en el pliego de condiciones señalado al principio. Sin embargo, aquellas situaciones en que el primer operando sea un tipo const char o una matriz C clásica, exigen una conversión explícita o implícita previa. Ejemplo:

s1 = s2 + "AEIOU"; // Ok.

s1 = s2 + 'X'; // Ok.

s1 = "AEIOU" + s2; // Error!

s1 = 'X' + s2; // Error!

String s3 = String("AEIOU");

s1 = s3 + s2; // Ok. alternativa-1

String s4('X');

s1 = s4 + s2; // Ok. alternativa-1

s1 = static_cast<String>("AEIOU") + s2; // Ok. alternativa-2

s1 = static_cast<String>('X') + s2; // Ok. alternativa-2

Por las razones expuestas anteriormente (§3 ), la invocación del constructor con una constante numérica explícita debe acompañarse del indicador UL. Ejemplo:

String s1(1024); // Error!

String s2(1024UL); // Ok.

Inicio