Iteradores en Secuencias de Caracteres Personalizadas

En C++, los iteradores son una abstracción fundamental que permite a los algoritmos genéricos operar sobre diferentes tipos de contenedores de manera uniforme. Estos algoritmos, que son funciones globales independientes del tipo de contenedor, confían en la interfaz proporcionada por los iteradores para acceder y manipular los elementos de cualquier estructura de datos, ya sea una lista enlazada, un array o una secuencia de caracteres.

Consideremos la implemetnación de un iterador para una clase de secuencia de caracteres básica, similar a un std::string simplificado. El iterador encapsula un puntero al tipo de elemento subyacente (char en este caso) y define las operaciones mínimas necesarias para recorrer la secuencia: desreferenciación (*), comparación de desigualdad (!=) e incremento (++).

#include <cstring> // Para strlen, strcpy

class MyCharSeq {
public:
    // Clase anidada que actúa como iterador para MyCharSeq
    class CharSeqIterator {
    private:
        char* _current_pos; // Puntero al carácter actual en la secuencia
    public:
        // Constructor que inicializa el iterador con un puntero
        CharSeqIterator(char* p) : _current_pos(p) {}

        // Operador de desreferencia para obtener el valor del carácter actual
        char operator*() const {
            return *_current_pos;
        }

        // Operador de desigualdad para comparar si dos iteradores apuntan a diferentes posiciones
        bool operator!=(const CharSeqIterator& other) const {
            return _current_pos != other._current_pos;
        }

        // Operador de pre-incremento para avanzar el iterador a la siguiente posición
        void operator++() {
            ++_current_pos;
        }
    };

    // Constructor que inicializa la secuencia con una cadena C-style
    MyCharSeq(const char* c_str = "") {
        if (c_str) {
            _data_ptr = new char[strlen(c_str) + 1];
            strcpy(_data_ptr, c_str);
        } else {
            _data_ptr = new char[1];
            _data_ptr[0] = '\0';
        }
    }

    // Destructor para liberar la memoria asignada
    ~MyCharSeq() {
        delete[] _data_ptr;
    }

    // Métodos para obtener iteradores al principio y al final lógico de la secuencia
    CharSeqIterator begin() { return CharSeqIterator(_data_ptr); }
    CharSeqIterator end() { return CharSeqIterator(_data_ptr + strlen(_data_ptr)); }

private:
    char* _data_ptr; // Puntero a la memoria donde se almacenan los caracteres de la secuencia
    // Se podrían añadir otros miembros como tamaño, capacidad, etc., pero se omiten para simplificar el ejemplo
};

Implementación de Iteradores para Contenedores Dinámicos (Vector)

La construcción de un contenedor dinámico como un vector personalizado, que gestione su propia memoria y objetos, requiere un enfoque más elaborado, especialmante en lo que respecta a la asignación de memoria y la construcción/destrucción de objetos. Aquí es donde entra en juego el concepto de un "asignador" o "gestor de memoria" (allocator). Este componenet es responsable de desacoplar la asignación y liberación de memoria cruda de la construcción y destrucción de objetos en esa memoria.

Un asignador personalizado típicamente implementa cuatro funciones clave:

• request_memory: Asigna un bloque de memoria sin inicializar.
• release_memory: Libera el bloque de memoria previamente asignado.
• create_object: Construye un objeto en una ubicación de memoria específica (utilizando placement new).
• destroy_object: Destruye un objeto en una ubicación de memoria específica (llamando a su destructor).

#include <iostream>
#include <new>     // Para placement new
#include <cstdlib> // Para malloc, free
#include <stdexcept> // Para std::out_of_range

// Gestor de memoria personalizado para tipos T
template<typename T>
struct CustomMemoryHandler {
    // Asigna un bloque de memoria bruta para 'count' elementos de tipo T
    T* request_memory(size_t count) {
        return static_cast<T*>(malloc(sizeof(T) * count));
    }

    // Libera un bloque de memoria bruta previamente asignado
    void release_memory(void* ptr) {
        free(ptr);
    }

    // Construye un objeto de tipo T en la dirección de memoria 'ptr' con el valor 'value'
    void create_object(T* ptr, const T& value) {
        new (ptr) T(value); // Uso de placement new para construir en memoria existente
    }

    // Destruye un objeto de tipo T en la dirección de memoria 'ptr'
    void destroy_object(T* ptr) {
        ptr->~T(); // Llamada explícita al destructor del objeto
    }
};

Utilizando este gestor de memoria, podemos construir una clase DynamicArray que emule el comportamiento de un std::vector. La clase DynamicArray mantiene punteros a su inicio (_start_ptr), al final de los elementos construidos (_finish_ptr) y al final de la capacidad de memoria asignada (_end_of_storage_ptr).

El iterador para DynamicArray es similar al de MyCharSeq, pero opera con punteros a T. Es crucial que el contenedor gestione adecuadamente la memoria en sus constructores, destructor y operador de asignación, asegurándose de que los objetos se construyan y destruyan correctamente solo dentro del rango de elementos válidos.

template<typename T, typename MemAlloc = CustomMemoryHandler<T>>
class DynamicArray {
public:
    // Clase anidada para el iterador del DynamicArray
    class ArrayIterator {
    public:
        ArrayIterator(T* p = nullptr) : _ptr(p) {}

        // Operador de desigualdad para comparar iteradores
        bool operator!=(const ArrayIterator& other) const {
            return _ptr != other._ptr;
        }

        // Operador de pre-incremento para avanzar el iterador
        void operator++() {
            ++_ptr;
        }

        // Operador de desreferencia (versión no const, para modificación)
        T& operator*() { return *_ptr; }

        // Operador de desreferencia (versión const, para lectura)
        const T& operator*() const { return *_ptr; }
    private:
        T* _ptr;
    };

    // Constructor: inicializa el array con una capacidad mínima
    DynamicArray(size_t initial_capacity = 10) {
        _start_ptr = _mem_manager.request_memory(initial_capacity);
        _finish_ptr = _start_ptr;
        _end_of_storage_ptr = _start_ptr + initial_capacity;
    }

    // Destructor: destruye todos los objetos válidos y libera la memoria asignada
    ~DynamicArray() {
        for (T* p = _start_ptr; p != _finish_ptr; ++p) {
            _mem_manager.destroy_object(p);
        }
        _mem_manager.release_memory(_start_ptr);
        _start_ptr = _finish_ptr = _end_of_storage_ptr = nullptr;
    }

    // Constructor de copia: realiza una copia profunda de los elementos
    DynamicArray(const DynamicArray<T>& other) {
        size_t capacity = other._end_of_storage_ptr - other._start_ptr;
        _start_ptr = _mem_manager.request_memory(capacity);
        size_t current_size = other._finish_ptr - other._start_ptr;
        for (size_t i = 0; i < current_size; ++i) {
            _mem_manager.create_object(_start_ptr + i, other._start_ptr[i]);
        }
        _finish_ptr = _start_ptr + current_size;
        _end_of_storage_ptr = _start_ptr + capacity;
    }

    // Operador de asignación: gestiona la auto-asignación y realiza una copia profunda
    DynamicArray& operator=(const DynamicArray<T>& other) {
        if (this == &other) {
            return *this;
        }

        // Destruir elementos actuales y liberar la memoria existente
        for (T* p = _start_ptr; p != _finish_ptr; ++p) {
            _mem_manager.destroy_object(p);
        }
        _mem_manager.release_memory(_start_ptr);

        // Asignar nueva memoria y copiar elementos de 'other'
        size_t capacity = other._end_of_storage_ptr - other._start_ptr;
        _start_ptr = _mem_manager.request_memory(capacity);
        size_t current_size = other._finish_ptr - other._start_ptr;
        for (size_t i = 0; i < current_size; ++i) {
            _mem_manager.create_object(_start_ptr + i, other._start_ptr[i]);
        }
        _finish_ptr = _start_ptr + current_size;
        _end_of_storage_ptr = _start_ptr + capacity;
        return *this;
    }

    // Añadir un elemento al final del array, redimensionando si es necesario
    void push_back(const T& value) {
        if (is_full()) {
            reallocate_and_copy();
        }
        _mem_manager.create_object(_finish_ptr, value);
        _finish_ptr++;
    }

    // Eliminar el último elemento del array, destruyendo el objeto
    void pop_back() {
        if (is_empty()) {
            return;
        }
        --_finish_ptr;
        _mem_manager.destroy_object(_finish_ptr);
    }

    // Acceder al último elemento del array
    T back_element() const {
        if (is_empty()) {
             throw std::out_of_range("Array is empty");
        }
        return *(_finish_ptr - 1);
    }

    // Comprobar si la capacidad de almacenamiento está llena
    bool is_full() const { return _finish_ptr == _end_of_storage_ptr; }

    // Comprobar si el array no contiene elementos
    bool is_empty() const { return _start_ptr == _finish_ptr; }

    // Obtener el número de elementos actualmente en el array
    size_t count() const { return _finish_ptr - _start_ptr; }

    // Operador de acceso por índice (versión no const)
    T& operator[](size_t index) {
        if (index >= count()) {
            throw std::out_of_range("Index out of bounds");
        }
        return _start_ptr[index];
    }
    // Operador de acceso por índice (versión const)
    const T& operator[](size_t index) const {
        if (index >= count()) {
            throw std::out_of_range("Index out of bounds");
        }
        return _start_ptr[index];
    }

    // Métodos para obtener iteradores al principio y al final lógico
    ArrayIterator begin() { return ArrayIterator(_start_ptr); }
    ArrayIterator end() { return ArrayIterator(_finish_ptr); }

private:
    T* _start_ptr;           // Puntero al inicio del bloque de memoria
    T* _finish_ptr;          // Puntero al final de los elementos construidos
    T* _end_of_storage_ptr;  // Puntero al final de la memoria asignada
    MemAlloc _mem_manager;   // Instancia del gestor de memoria

    // Función auxiliar para redimensionar el array y copiar elementos
    void reallocate_and_copy() {
        size_t old_capacity = _end_of_storage_ptr - _start_ptr;
        size_t new_capacity = old_capacity == 0 ? 1 : old_capacity * 2; // Duplicar capacidad o iniciar en 1

        T* new_start_ptr = _mem_manager.request_memory(new_capacity);
        size_t current_size = _finish_ptr - _start_ptr;

        // Copiar y construir objetos en la nueva memoria
        for (size_t i = 0; i < current_size; ++i) {
            _mem_manager.create_object(new_start_ptr + i, _start_ptr[i]);
        }

        // Destruir objetos antiguos y liberar la memoria anterior
        for (T* p = _start_ptr; p != _finish_ptr; ++p) {
            _mem_manager.destroy_object(p);
        }
        _mem_manager.release_memory(_start_ptr);

        // Actualizar punteros para el nuevo bloque de memoria
        _start_ptr = new_start_ptr;
        _finish_ptr = _start_ptr + current_size;
        _end_of_storage_ptr = _start_ptr + new_capacity;
    }
};

// Clase de prueba para observar la vida de los objetos
class TestObject {
public:
    TestObject() { std::cout << "TestObject() - Constructor por defecto" << std::endl; }
    ~TestObject() { std::cout << "~TestObject() - Destructor" << std::endl; }
    TestObject(const TestObject&) { std::cout << "TestObject(const TestObject&) - Constructor de copia" << std::endl; }
    TestObject& operator=(const TestObject&) { std::cout << "TestObject operator=() - Operador de asignación" << std::endl; return *this; }
};

int main() {
    DynamicArray<int> dynamic_int_array;
    std::cout << "--- Llenando array de enteros ---" << std::endl;
    for (int i = 0; i < 20; ++i) {
        dynamic_int_array.push_back(rand() % 100 + 1);
    }

    std::cout << "\n--- Elementos usando el operador [] ---" << std::endl;
    for (size_t i = 0; i < dynamic_int_array.count(); ++i) {
        std::cout << dynamic_int_array[i] << " ";
    }
    std::cout << std::endl;

    std::cout << "\n--- Elementos usando iteradores ---" << std::endl;
    for (auto it = dynamic_int_array.begin(); it != dynamic_int_array.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    std::cout << "\n--- Probando DynamicArray con TestObject ---" << std::endl;
    DynamicArray<TestObject> test_objects_array;
    std::cout << "Agregando primer objeto:" << std::endl;
    test_objects_array.push_back(TestObject()); 
    std::cout << "Agregando segundo objeto:" << std::endl;
    test_objects_array.push_back(TestObject());

    std::cout << "\n--- Fin del main, se llamarán destructores ---" << std::endl;
    return 0;
}