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:
§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.