c++ - que - punteros y matrices en c

Búsqueda de puntero sin formato para conjuntos de unique_ptrs

Question

A menudo me encuentro queriendo escribir código como este:

class MyClass
{
public:
  void addObject(std::unique_ptr<Object>&& newObject);

  void removeObject(const Object* target);

private:
  std::set<std::unique_ptr<Object>> objects;
};

Sin embargo, gran parte de la interfaz std :: set es inútil con std :: unique_ptrs ya que las funciones de búsqueda requieren los parámetros std :: unique_ptr (que obviamente no tengo porque son propiedad del propio conjunto).

Puedo pensar en dos soluciones principales para esto.

1. Crea un unique_ptr temporal para la búsqueda. Por ejemplo, el removeObject () anterior podría implementarse como:

   void MyClass::removeObject(const Object* target)
   {
     std::unique_ptr<Object> targetSmartPtr(target);
     objects.erase(targetSmartPtr);
     targetSmartPtr.release();
   }

2. Reemplace el conjunto con un mapa de punteros sin procesar a unique_ptrs.

     // ...
     std::map<const Object*, std::unique_ptr<Object>> objects;
   };

Sin embargo, ambos me parecen un poco estúpidos. En la solución 1, erase () no es noexcept, por lo que el unique_ptr temporal podría eliminar el objeto que realmente no posee, y 2 requiere el doble de almacenamiento para el contenedor innecesariamente.

Sé sobre los contenedores de punteros de Boost, pero sus características actuales son limitadas en comparación con los contenedores de bibliotecas estándares modernos de C ++ 11.

Hace poco estuve leyendo sobre C ++ 14 y encontré "Agregar búsqueda de comparación heterogénea a contenedores asociativos". Pero a mi entender, los tipos de búsqueda deben ser comparables a los tipos de clave, pero los punteros crudos no son comparables a unique_ptrs.

¿Alguien sabe de una solución más elegante o una próxima adición a C ++ que resuelve este problema?

Answer 1

Aunque definitivamente es un truco, me acabo de dar cuenta de que es posible construir un unique_ptr "estúpido" temporal con ubicación nueva y sin riesgo de desasignación. removeObject() podría escribirse algo como esto:

void MyClass::removeObject(const Object* target)
{
  alignas(std::unique_ptr<Object>)
  char dumbPtrData[sizeof(std::unique_ptr<Object>)];

  objects.erase(
      *::new (dumbPtrData) std::unique_ptr<Object>(const_cast<Object *>(target)));
}

Esta solución funcionaría para std::unordered_set , std::map keys, y std::unordered_map keys también, todas usando solo C ++ 11 estándar, con prácticamente cero sobrecarga innecesaria.

Answer 2

En C++14 , std::set<Key>::find es una función de template si existe Compare::is_transparent . El tipo que ingrese no necesita ser Key , solo equivalente bajo su comparador.

Entonces escribe un comparador:

template<class T>
struct pointer_comp {
  typedef std::true_type is_transparent;
  // helper does some magic in order to reduce the number of
  // pairs of types we need to know how to compare: it turns
  // everything into a pointer, and then uses `std::less<T*>`
  // to do the comparison:
  struct helper {
    T* ptr;
    helper():ptr(nullptr) {}
    helper(helper const&) = default;
    helper(T* p):ptr(p) {}
    template<class U, class...Ts>
    helper( std::shared_ptr<U,Ts...> const& sp ):ptr(sp.get()) {}
    template<class U, class...Ts>
    helper( std::unique_ptr<U, Ts...> const& up ):ptr(up.get()) {}
    // && optional: enforces rvalue use only
    bool operator<( helper o ) const {
      return std::less<T*>()( ptr, o.ptr );
    }
  };
  // without helper, we would need 2^n different overloads, where
  // n is the number of types we want to support (so, 8 with
  // raw pointers, unique pointers, and shared pointers).  That
  // seems silly:
  // && helps enforce rvalue use only
  bool operator()( helper const&& lhs, helper const&& rhs ) const {
    return lhs < rhs;
  }
};

luego úsalo:

typedef std::set< std::unique_ptr<Foo>, pointer_comp<Foo> > owning_foo_set;

ahora, owning_foo_set::find aceptará unique_ptr<Foo> o Foo* o shared_ptr<Foo> (o cualquier clase derivada de Foo ) y encontrará el elemento correcto.

Fuera de C ++ 14, se ve obligado a utilizar el map en el enfoque unique_ptr , o algo equivalente, ya que la firma del find es demasiado restrictiva. O escribe tu propio set equivalentes.

Answer 3

Estás usando pinters únicos aquí. Esto significa que su conjunto tiene propiedad exclusiva de los objetos. Ahora, esto debería significar que si el objeto existe, está en el conjunto o tiene un puntero único. Ni siquiera necesita buscar el conjunto en este caso.

Pero para mí parece que no es el caso. Supongo que está mejor con un puntero compartido en este caso. Simplemente almacene punteros compartidos y páselos, ya que alguien junto a este conjunto los almacena claramente.

Answer 4

Otra posibilidad, cercana a la respuesta aceptada, pero un poco diferente y simplificada.

Podemos aprovechar el hecho de que el comparador estándar std::less<> (sin argumentos de plantilla) es transparente. Entonces, podemos suministrar nuestras propias funciones de comparación en el espacio de nombres global:

// These two are enough to be able to call objects.find(raw_ptr) bool operator<(const unique_ptr<Object>& lhs, const Object* rhs) { return std::less<const Object*>()(lhs.get(), rhs); } bool operator<(const Object* lhs, const unique_ptr<Object>& rhs) { return std::less<const Object*>()(lhs, rhs.get()); } class MyClass { // ... private: std::set<std::unique_ptr<Object>, std::less<>> objects; // Note std::less<> here };

Answer 5

Puede intentar utilizar boost :: multi_index_container con indexación adicional por Object *. Algo como esto:

typedef std::unique_ptr<Object> Ptr;
typedef multi_index_container<
  Ptr,
  indexed_by<
    hashed_unique<Ptr>,
    ordered_unique<const_mem_fun<Ptr,Object*,&Ptr::get> >
  >
> Objects;

Para obtener más información, consulte la documentación Boost Multi-index Containers.

¿O puede ser que pueda usar std :: shared_ptr en cualquier lugar, o usar punteros sin procesar en conjunto?

¿Por qué necesita buscar por pinter crudo? Si lo almacena en cualquier lugar y comprueba que el objeto con este puntero es válido, entonces mejor usar std :: shared_ptr para almacenar en contenedor y std :: weak_ptr para otros objetos. En este caso, antes del uso, no necesita buscar por puntero sin procesar.

Answer 6

ACTUALIZACIÓN 2: Yakk es correcto , no hay forma de hacerlo con los contenedores estándar C ++ 11 sin compromisos significativos. O algo se ejecutará en tiempo lineal en el peor de los casos o existen esas soluciones provisionales que usted escribe en su pregunta.

Hay dos soluciones que consideraría.

Intentaría un std::vector clasificado, de forma similar a boost::container::flat_set . Sí, las inserciones / borrados serán tiempos lineales en el peor de los casos. Aún así, podría ser mucho más rápido de lo que probablemente piense: los contenedores contiguos son muy amigables con la caché en comparación con los contenedores basados ​​en nodos, como std::set . Por favor, lea lo que escriben en boost::container::flat_set . Si este compromiso es aceptable para usted, no puedo decirlo / medirlo.

Otros también mencionaron std::share_ptr . Personalmente trato de evitarlos, principalmente porque "un puntero compartido es tan bueno como una variable global" (Sean Parent). Otra razón por la que no los uso es porque son muy pesados, en parte debido a todas las cosas de multi-threading que generalmente no necesito. Sin embargo, boost::shared_ptr , cuando se define BOOST_SP_DISABLE_THREADS , elimina toda esa sobrecarga asociada con multi-threading. Creo que usar boost::shared_ptr sería la solución más fácil en su caso.

ACTUALIZACIÓN: Como amablemente señaló Yakk , mi enfoque tiene complejidad de tiempo lineal ... :(

(La primera versión)

Puede hacerlo pasando un comparador personalizado a std::lower_bound() . Aquí hay una implementación rudimentaria de cómo:

#include <algorithm>
#include <cassert>
#include <iostream>
#include <memory>
#include <set>
#include <string>

using namespace std;

template <typename T>
class Set {

private:

    struct custom_comparator {
        bool operator()(const unique_ptr<T>& a, const T* const & b){
            return a.get() < b;
        }
    } cmp;

    set<unique_ptr<T>> objects; // decltype at begin() and end()
                                // needs objects to be declared here
public:

    auto begin() const -> decltype(objects.begin()) { return objects.begin(); }

    auto   end() const -> decltype(objects.end()  ) { return objects.end();   }

    void addObject(unique_ptr<T>&& newObject) {

        objects.insert(move(newObject));
    }

    void removeObject(const T* target) {

        auto pos = lower_bound(objects.begin(), objects.end(), target, cmp);

        assert (pos!=objects.end()); // What to do if not found?

        objects.erase(pos);
    }
};

void test() {

    typedef string T;

    Set<T> mySet;

    unique_ptr<T> a{new T("a")};
    unique_ptr<T> b{new T("b")};
    unique_ptr<T> c{new T("c")};

    T* b_ptr = b.get();

    mySet.addObject(move(a));
    mySet.addObject(move(b));
    mySet.addObject(move(c));

    cout << "The set now contains: " << endl;

    for (const auto& s_ptr : mySet) {

        cout << *s_ptr << endl;
    }

    mySet.removeObject(b_ptr);

    cout << "After erasing b by the pointer to it:" << endl;

    for (const auto& s_ptr : mySet) {

        cout << *s_ptr << endl;
    }
}

int main() {

    test();
}