Introducción
Constructores
Destructor
Iteradores
Constructor de Copia y Operador de Asignación
Probleam de Copia Superficial y Profunda
Enfoque Tradicional
Enfoque Moderno
Funciones de Inserción
reserve()
push_back()
append()
Operador +=
insert()
erase()
Inserción y Extracción de Flujo
Inserción en Flujo
Extracción de Flujo
Sobrecarga de Operadores
Otras Implementaciones de Funciones
Sobrecarga de []
resize()
find()
substr()
Código Completo
Introducción
Este artículo presenta la implementación de una clase string similar a la proporcionada en la STL de C++. Nuestro objetivo no es crear una implementación mejor que la original, sino comprender los fundamentos de cómo funciona internamente la clase string. La implementación real en la biblioteca estándar es mucho más compleja y optimizada.
Para conocer el uso básico de la clase string, puedes consultar la documentación oficial en cplusplus.com/reference/string/string/
Constructores
Al implementar los constructores, podemos crear uno sin parámetros y uno con parámetros. Sin embargo, podemos omitir el constructor sin parámetros utilizando un valor predeterminado en el constructor con parámetros. Para el caso sin parámetros, necesitamos asegurarnos de incluir el carácter nulo ('\0'), por lo que podemos usar una cadena vacía como valor predeterminado.
// Constructor
Cadena(const char* str = "")
{
_tamano = strlen(str);
_capacidad = _tamano;
_datos = new char[_capacidad + 1];
strcpy(_datos, str);
}
Al usar la función strlen para inicializar las variables miembro, solo necesitamos aplicarla a una de ellas, ya que cada llamada a strlen tiene una complejidad O(N). Al asignar memoria con new, debemos recordar incluir espacio para el carácter nulo al final, como se muestra en _capacidad + 1 en el código anterior. Finalmente, no olvides copiar los datos después de la inicialización.
Destructor
// Destructor
~Cadena()
{
delete[] _datos;
_datos = nullptr;
_tamano = _capacidad = 0;
}
Es necesario liberar la memoria asignada con delete y establecer el puntero a nullptr para evitar punteros salvajes.
Iteradores
Los iteradores son bastante sencillos de implementar. En esencia, son simplemente punteros a char.
// Iteradores
typedef char* iterador;
typedef char* const_iterador;
iterador begin()
{
return _datos;
}
iterador end()
{
return _datos + _tamano;
}
const_iterador begin() const
{
return _datos;
}
const_iterador end() const
{
return _datos + _tamano;
}
Constructor de Copia y Operador de Asignación
Problema de Copia Superficial y Profunda
Si no implementamos el constructor de copia, el compilador generará uno por defecto. Sin embargo, este es una copia superficial, lo que significa que múltiples objetos compartirán la misma memoria. Cuando uno de estos objetos es destruido, la memoria se libera, pero los otros objetos seguirán apuntando a esa memoria ya liberada, lo que puede causar un comportamiento indefinido o fallos del programa.
Copia superficial: También llamada copia bit a bit, donde el compilador simplemente copia los valores de los atributos. Si el objeto gestiona recursos (como memoria), múltiples objetos terminarán compartiendo el mismo recurso, causando problemas cuando uno de ellos libera el recurso.
Copia profunda: Asigna reucrsos independientes para cada objeto, asegurando que la liberación de recursos en un objeto no afecte a otros.
Enfoque Tradicional
// Constructor de copia - enfoque tradicional
Cadena(const Cadena& otra)
: _datos(new char[otra._capacidad + 1])
, _tamano(otra._tamano)
, _capacidad(otra._capacidad)
{
strcpy(_datos, otra._datos);
}
// Operador de asignación - enfoque tradicional
Cadena& operator=(const Cadena& otra)
{
if (this != &otra)
{
char* tmp = new char[otra._capacidad + 1];
strcpy(tmp, otra._datos);
delete[] _datos;
_datos = tmp;
_tamano = otra._tamano;
_capacidad = otra._capacidad;
}
return *this;
}
Enfoque Moderno
void intercambiar(Cadena& tmp)
{
::swap(_datos, tmp._datos);
::swap(_tamano, tmp._tamano);
::swap(_capacidad, tmp._capacidad);
}
// Constructor de copia - enfoque moderno
Cadena(const Cadena& otra)
: _datos(nullptr)
, _tamano(0)
, _capacidad(0)
{
Cadena tmp(otra._datos);
intercambiar(tmp);
}
// Operador de asignación - enfoque moderno
Cadena& operator=(const Cadena& otra)
{
Cadena tmp(otra);
intercambiar(tmp);
return *this;
}
// Versión simplificada del operador de asignación
Cadena& operator=(Cadena otra)
{
intercambiar(otra);
return *this;
}
Funciones de Inserción
reserve()
Antes de insertar datos, debemos asegurarnos de que haya suficiente espacio. La función reserve() gestiona esto. Si el espacio es insuficiente, asignamos un nuevo bloque de memoria, copiamos los datos existentes al nuevo espacio, liberamos el antiguo y actualizamos la capacidad.
void reservar(size_t n)
{
if (n > _capacidad)
{
char* tmp = new char[n + 1]; // Espacio para '\0'
strcpy(tmp, _datos);
delete[] _datos;
_datos = tmp;
_capacidad = n;
}
}
push_back()
void aniadirFinal(char caracter)
{
if (_tamano == _capacidad)
{
reservar(_capacidad == 0 ? 4 : _capacidad * 2);
}
_datos[_tamano++] = caracter;
_datos[_tamano] = '\0'; // Asegurarse de añadir el terminador nulo
}
append()
void aniadir(const char* str)
{
size_t len = strlen(str);
if (_tamano + len > _capacidad)
{
reservar(_tamano + len);
}
strcpy(_datos + _tamano, str);
_tamano += len;
}
void aniadir(const Cadena& s)
{
aniadir(s._datos);
}
void aniadir(size_t n, char ch)
{
reservar(_tamano + n);
for (int i = 0; i < n; i++)
{
aniadirFinal(ch);
}
}
Operador +=
Cadena& operator+=(const char* str)
{
aniadir(str);
return *this;
}
insert()
Cadena& insertar(size_t pos, char ch)
{
assert(pos <= _tamano);
if (_tamano == _capacidad)
{
reservar(_capacidad == 0 ? 4 : _capacidad * 2);
}
// Mover datos hacia adelante
size_t final = _tamano + 1;
while (final > pos)
{
_datos[final] = _datos[final - 1];
final--;
}
_datos[pos] = ch;
_tamano++;
return *this;
}
Cadena& insertar(size_t pos, const char* str)
{
assert(pos <= _tamano);
size_t len = strlen(str);
if (_tamano + len > _capacidad)
{
reservar(_tamano + len);
}
// Mover datos para hacer espacio
size_t final = _tamano + len;
while (final >= pos + len)
{
_datos[final] = _datos[final - len];
final--;
}
strncpy(_datos + pos, str, len);
_tamano += len;
return *this;
}
erase()
En la implementación de la STL, erase utiliza una constante npos que es esencialmente -1. Podemos agregar esta constante a nuestra clase de cadena.
static const size_t npos = -1;
void borrar(size_t pos, size_t len = npos)
{
assert(pos < _tamano);
if (len == npos || pos + len >= _tamano)
{
_datos[pos] = '\0';
_tamano = pos;
}
else
{
strcpy(_datos + pos, _datos + pos + len);
_tamano -= len;
}
}
Inserción y Extracción de Flujo
Inserción en Flujo
ostream& operator<<(ostream& out, const Cadena& s)
{
for (size_t i = 0; i < s.tamano(); i++)
{
out << s[i];
}
return out;
}
Extracción de Flujo
Primero, implementamos una función clear() para limpiar los datos existentes:
void limpiar()
{
_datos[0] = '\0';
_tamano = 0;
}
La implementación básica de la extracción de flujo podría verse así:
istream& operator>>(istream& in, Cadena& s)
{
char ch;
in >> ch;
while (ch != ' ' && ch != '\n')
{
s += ch;
in >> ch;
}
return in;
}
Sin embargo, esta implementación tiene problemas: el bucle no se detendría correctamente porque considera espacios y saltos de línea como separadores. Además, la eficiencia es bajja debido a las múltiples reasignaciones de memoria al insertar caracteres uno por uno.
Una solución mejor utiliza un búfer temporal para mejorar la eficiencia:
istream& operator>>(istream& in, Cadena& s)
{
s.limpiar();
char ch;
ch = in.get();
const size_t N = 64;
char buffer[N];
size_t i = 0;
while (ch != ' ' && ch != '\n')
{
buffer[i++] = ch;
if (i == N - 1)
{
buffer[i] = '\0';
s += buffer;
i = 0;
}
ch = in.get();
}
buffer[i] = '\0';
s += buffer;
return in;
}
Sobrecarga de Operadores
Implementemos algunos operadores de comparación utilizando la función strcmp de la biblioteca estándar:
bool operator > (const Cadena& s) const
{
return strcmp(_datos, s._datos) > 0;
}
bool operator == (const Cadena& s) const
{
return strcmp(_datos, s._datos) == 0;
}
bool operator >= (const Cadena& s) const
{
return *this > s || *this == s;
}
bool operator <= (const Cadena& s) const
{
return !(*this > s);
}
bool operator < (const Cadena& s) const
{
return !(*this >= s);
}
bool operator != (const Cadena& s) const
{
return !(*this == s);
}
Otras Implementaciones de Funciones
Sobrecarga de []
La sobrecarga del operador corchete permite el acceso por índice:
const char& operator[](size_t pos) const
{
assert(pos < _tamano);
return _datos[pos];
}
char& operator[](size_t pos)
{
assert(pos < _tamano);
return _datos[pos];
}
resize()
Esta función ajusta el tamaño de la cadena, opcionalmente rellenando con un carácter específico:
void redimensionar(size_t n, char ch = '\0')
{
if (n > _tamano)
{
// Insertar caracteres para expandir
reservar(n);
for (size_t i = _tamano; i < n; i++)
{
_datos[i] = ch;
}
_datos[n] = '\0';
}
else
{
// Reducir el tamaño
_datos[n] = '\0';
_tamano = n;
}
}
find()
La función find busca un carácter o subcadena y devuelve su posición:
size_t buscar(char ch, size_t pos = 0) const
{
assert(pos < _tamano);
for (size_t i = pos; i < _tamano; i++)
{
if (ch == _datos[i])
{
return i;
}
}
return npos;
}
size_t buscar(const char* subcadena, size_t pos = 0) const
{
assert(subcadena);
assert(pos < _tamano);
const char* ptr = strstr(_datos + pos, subcadena);
if (ptr == nullptr)
{
return npos;
}
else
{
return ptr - _datos; // Calcular posición mediante resta de punteros
}
}
substr()
La función substr extrae una subcadena:
Cadena subcadena(size_t pos, size_t len = npos) const
{
assert(pos < _tamano);
size_t longitudReal = len;
if (len == npos || len + pos >= _tamano)
{
longitudReal = _tamano - pos;
}
Cadena resultado;
for (size_t i = 0; i < longitudReal; i++)
{
resultado += _datos[i + pos];
}
return resultado;
}
Código Completo
La implementación completa de nuestra clase string personalizada incluye todas las funciones descritas anteriormente. La biblioteca estándar de C++ contiene muchas más funciones que pueden ser implementadas si se desea profundizar en el tema.