c++ - libreria - ¿Se pueden usar punteros sin procesar en lugar de iteradores con algoritmos STL para contenedores con almacenamiento lineal?

map c++

Question

Tengo un contenedor de vector personalizado que almacena internamente el elemento en una matriz lineal. Ayer por la noche, estaba tratando de implementar iteradores personalizados para mi clase para poder usarlos con algoritmos STL. He tenido cierto éxito que puedes ver aquí:

Ejemplo en vivo con iteradores personalizados

Mientras lo hacía, descubrí que simplemente podía pasar punteros sin procesar al algoritmo STL y simplemente parecen funcionar bien. Aquí está el ejemplo sin iteradores:

#include <cstddef>
#include <iostream>
#include <iterator>
#include <algorithm>

template<typename T>
class my_array{
    T* data_;
    std::size_t size_;

public:

    my_array()
        : data_(NULL), size_(0)
    {}
    my_array(std::size_t size)
        : data_(new T[size]), size_(size)
    {}
    my_array(const my_array<T>& other){
        size_ = other.size_;
        data_ = new T[size_];
        for (std::size_t i = 0; i<size_; i++)
            data_[i] = other.data_[i];
    }
    my_array(const T* first, const T* last){
        size_ = last - first;
        data_ = new T[size_];

        for (std::size_t i = 0; i<size_; i++)
            data_[i] = first[i];
    }

    ~my_array(){
        delete [] data_;
    }
    const my_array<T>& operator=(const my_array<T>& other){
        size_ = other.size_;
        data_ = new T[size_];
        for (std::size_t i = 0; i<size_; i++)
            data_[i] = other.data_[i];
        return other;
    }
    const T& operator[](std::size_t idx) const {return data_[idx];}
    T& operator[](std::size_t& idx) {return data_[idx];}
    std::size_t size(){return size_;}

    T* begin(){return data_;}
    T* end(){return data_+size_;}
};

template<typename T>
void print(T t) {
    std::cout << t << std::endl;
}

int main(){


    typedef float scalar_t;
    scalar_t list [] = {1, 3, 5, 2, 4, 3, 5, 10, 10};
    my_array<scalar_t> a(list, list+sizeof(list)/sizeof(scalar_t));

    // works!
    for (scalar_t* it = a.begin(), *end = a.end();
         it != end; ++it)
        std::cout << '' '' << *it;
    std::cout << std::endl;

    // works!
    std::for_each(a.begin(), a.end(), print<scalar_t>);
    std::cout << std::endl;

    // works!
    my_array<int> b(a.size());
    std::copy(a.begin(), a.end(), b.begin());

    // works!
    scalar_t* end = std::remove(a.begin(), a.end(), 5);
    std::for_each(a.begin(), end, print<scalar_t>);
    std::cout << std::endl;

    // works!
    std::random_shuffle(a.begin(), end);
    std::for_each(a.begin(), end, print<scalar_t>);
    std::cout << std::endl;

    // works!
    std::cout << "Counts of 3 in array = " << std::count(a.begin(), end, 3) << std::endl << std::endl;

    // works!
    std::sort(a.begin(), end);
    std::for_each(a.begin(), end, print<scalar_t>);
    std::cout << std::endl;

    // works!
    if (!std::binary_search(a.begin(), a.end(), 5))
        std::cout << "Removed!" << std::endl;

    return 0;
}

Ejemplo en vivo sin iteradores

Mis preguntas aquí son las siguientes:

1. ¿Esto siempre funciona para contenedores que tienen almacenamiento lineal? Sé que esto no funcionaría para listas enlazadas, por ejemplo.
2. Si funcionan en esta situación, ¿por qué debería pasar por la molestia de implementar iteradores de todos modos? Sé cómo los iteradores generalizan mi código y otras cosas, pero si este conjunto simple es todo lo que necesito, entonces no veo el punto.
3. ¿Cuáles son los problemas negativos de lo que estoy haciendo si este enfoque siempre funciona? Por un lado, puedo ver que estoy rompiendo la encapsulación de datos.

Answer 1

¿Esto siempre funciona para contenedores que tienen almacenamiento lineal?

Sí, los conceptos del iterador se diseñaron para que los punteros pudieran actuar como iteradores sobre las matrices.

Si funcionan en esta situación, ¿por qué debería pasar por la molestia de implementar iteradores de todos modos?

No hay una buena razón para definir su propio tipo de iterador en esta situación, a menos que desee hacer algo como comprobación de límites que no se puede hacer con un simple puntero.

Un pequeño beneficio sería que podría incluir typedefs anidados para los rasgos del iterador, como lo hacen algunos de los tipos de iteradores estándar; pero usando punteros estos están disponibles de std::iterator_traits<T*> todos modos.

¿Cuáles son los problemas negativos de lo que estoy haciendo si este enfoque siempre funciona? Por un lado, puedo ver que estoy rompiendo la encapsulación de datos.

Para que la interfaz sea más coherente con los contenedores de estilo STL, debe definir los tipos const_iterator y const_iterator ( typedef alias para los punteros) y proporcionar const sobrecargas de begin y end ; y quizás cbegin y cend para la cend de C ++ 11.

Hay varios otros requisitos con los que quizás desee cumplir; ver la sección 23.2 del estándar de C ++ para los detalles sangrientos. Pero, en general, es más importante hacer que los iteradores cumplan con sus requisitos, ya que los algoritmos de estilo STL funcionan con iteradores en lugar de contenedores, y al usar punteros, usted ya cumple con esos requisitos.

Answer 2

1. Sí. Ver STL efectivo, artículo 16 , que demuestra con contenedores de almacenamiento lineal que simplemente puede tomar la dirección de un elemento y trabajar con ese puntero como si apuntara a una matriz simple.
2. Creo que respondiste tu propia pregunta, probablemente no deberías, si sabes que la matriz simple es todo lo que necesitarás.
3. Probablemente el mayor problema es simplemente eso: romper la encapsulación de datos. Considere si una abstracción, como un tipo de iterador explícito, le compraría algo en comparación con el costo.

Answer 3

Sucede que los punteros proporcionan la interfaz requerida de los iteradores de acceso aleatorio (desreferencia, incremento, adición, diferencia, etc.) y pueden tratarse como iteradores.

1. Siempre debería funcionar para contenedores con almacenamiento contiguo.
2. Es posible que desee crear sus propios iteradores por la misma razón que usa métodos en lugar de todos los datos públicos en sus clases: para encapsular lo que está sucediendo con una interfaz, puede modificarla si es necesario. Siempre que defina su T* en un tipo de iterador, esto probablemente no sea un problema importante. Además, algunos algoritmos pueden beneficiarse de un iterador etiquetado con el tipo de iterador, que no se puede usar para tipos de puntero simples.

Answer 4

Una de las características de los iteradores que se basan en la sobrecarga del operador es que los punteros ya son iteradores de acceso aleatorio. Esta fue una gran victoria de diseño en los primeros días de STL, ya que facilitaba el uso de algoritmos con el código existente (además de hacer que la interfaz sea más familiar para los programadores). Es perfectamente razonable para envolver una matriz, agregar typedef T* iterator; typedef const T* const_iterator typedef T* iterator; typedef const T* const_iterator , return &array[0] de your begin() y &array[size] de tu end() , y luego usa tu contenedor con cualquier algoritmo basado en iterador. Como ya sabe, esto funcionará para cualquier contenedor donde los elementos estén contiguos en la memoria (como una matriz).

Puede implementar iteradores ''reales'' si:

• Tienes un contenedor de forma diferente (como un árbol o una lista);
• Desea poder cambiar el tamaño de la matriz sin invalidar los iteradores;
• Desea agregar comprobaciones de depuración al uso de su iterador, por ejemplo, para verificar si el iterador se usa después de ser invalidado o después de que se haya eliminado el contenedor, o para verificar los límites;
• Desea introducir seguridad de tipo y asegúrese de que las personas no puedan asignar accidentalmente una T* arbitraria a un my_array::iterator .

Yo diría que esta última ventaja por sí sola bien vale la pena escribir una clase de contenedor trivial. Si no aprovecha el sistema de tipos de C ++ haciendo que diferentes tipos de cosas tengan diferentes tipos, también puede cambiar a Javascript :-)