Ricerca puntatore raw per set di unique_ptrs

Spesso mi trovo a voler scrivere un codice come questo:

class MyClass { public: void addObject(std::unique_ptr&& newObject); void removeObject(const Object* target); private: std::set<std::unique_ptr> objects; }; 

Tuttavia, gran parte dell’interfaccia std :: set è praticamente inutile con std :: unique_ptrs poiché le funzioni di ricerca richiedono i parametri std :: unique_ptr (che ovviamente non ho perché appartengono al set stesso).

Posso pensare a due soluzioni principali a questo.

  1. Crea un unique_ptr temporaneo per la ricerca. Ad esempio, il precedente removeObject () potrebbe essere implementato come:

     void MyClass::removeObject(const Object* target) { std::unique_ptr targetSmartPtr(target); objects.erase(targetSmartPtr); targetSmartPtr.release(); } 
  2. Sostituisci il set con una mappa di puntatori grezzi su unique_ptrs.

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

Tuttavia, entrambi sembrano leggermente stupidi per me. Nella soluzione 1, cancella () non è nient’affatto, quindi il temporaneo unique_ptr potrebbe eliminare l’object che non possiede realmente e 2 richiede il doppio della memoria per il contenitore inutilmente.

Conosco i contenitori puntatori di Boost, ma le loro attuali caratteristiche sono limitate rispetto ai moderni contenitori di libreria standard C ++ 11.

Recentemente ho letto su C ++ 14 e mi sono imbattuto in “Aggiunta di una ricerca di confronto eterogeneo a contenitori associativi”. Ma dalla mia comprensione, i tipi di ricerca devono essere paragonabili ai tipi di chiavi, ma i puntatori grezzi non sono paragonabili a unique_ptrs.

Qualcuno sa di una soluzione più elegante o di un’imminente aggiunta a C ++ che risolva questo problema?

In C ++ 14 , std::set::find è una funzione template se Compare::is_transparent esiste. Il tipo che passi non deve essere Key , solo equivalente sotto il tuo comparatore.

Quindi scrivi un comparatore:

 template 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` // to do the comparison: struct helper { T* ptr; helper():ptr(nullptr) {} helper(helper const&) = default; helper(T* p):ptr(p) {} template helper( std::shared_ptr const& sp ):ptr(sp.get()) {} template helper( std::unique_ptr const& up ):ptr(up.get()) {} // && optional: enforces rvalue use only bool operator<( helper o ) const { return std::less()( 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; } }; 

quindi usalo:

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

ora, owning_foo_set::find accetterà unique_ptr o Foo* o shared_ptr (o qualsiasi class derivata di Foo ) e trova l'elemento corretto.

Al di fuori di C ++ 14, sei costretto ad usare la map per approccio unique_ptr , o qualcosa di equivalente, dato che la firma di find è eccessivamente restrittiva. O scrivi il tuo equivalente personale.

Puoi provare a utilizzare boost :: multi_index_container con indicizzazione aggiuntiva per Oggetto *. Qualcosa come questo:

 typedef std::unique_ptr Ptr; typedef multi_index_container< Ptr, indexed_by< hashed_unique, ordered_unique > > > Objects; 

Per maggiori informazioni consulta la documentazione di Boost Multi-index Containers

O potresti essere in grado di usare std :: shared_ptr ovunque, o usare invece i puntatori raw nel set?

Perché è necessario cercare da Pinter crudo? Se lo memorizzi ovunque e controlla che l’object con questo puntatore sia valido, meglio usare std :: shared_ptr per l’archiviazione in container e std :: weak_ptr per altri oggetti. In questo caso, prima dell’uso, non è necessario cercare il puntatore raw.

Nonostante sia decisamente un hack, ho appena realizzato che è ansible build un unique_ptr “stupido” temporaneo con collocamento nuovo e non azzardare la disallocazione. removeObject() potrebbe essere scritto qualcosa come questo:

 void MyClass::removeObject(const Object* target) { alignas(std::unique_ptr) char dumbPtrData[sizeof(std::unique_ptr)]; objects.erase( *::new (dumbPtrData) std::unique_ptr(const_cast(target))); } 

Questa soluzione funzionerebbe anche per le chiavi std::unordered_set , std::map e std::unordered_map , tutte utilizzando solo C ++ 11 standard, con praticamente nessun sovraccarico non necessario.

AGGIORNAMENTO 2: Yakk è corretto , non c’è modo di farlo con contenitori C ++ 11 standard senza compromessi significativi. O qualcosa funzionerà in tempo lineare nel peggiore dei casi o ci sono quei workaround che scrivi nella tua domanda.

Esistono due soluzioni alternative che prenderei in considerazione.

Proverei un file std::vector , analogamente a boost :: container :: flat_set . Sì, gli inserti / cancellazioni saranno temporali nel peggiore dei casi. Tuttavia, potrebbe essere molto più veloce di quanto pensiate: i contenitori contigui sono molto più facili da usare rispetto ai contenitori basati su nodes, come std::set . Si prega di leggere ciò che scrivono su boost :: container :: flat_set . Non posso dire / misurare questo compromesso accettabile per te.

Altri hanno anche menzionato std::share_ptr . Io personalmente cerco di evitarli, principalmente perché “un puntatore condiviso è buono come una variabile globale” (Sean Parent). Un altro motivo per cui non li uso è perché sono di peso elevato, in parte a causa di tutte le cose multi-threading che di solito non ho bisogno. Tuttavia, boost::shared_ptr , quando BOOST_SP_DISABLE_THREADS è definito, rimuove tutto l’overhead associato al multi-threading. Credo che l’utilizzo di boost::shared_ptr sia la soluzione più semplice nel tuo caso.


AGGIORNAMENTO: Come Yakk ha gentilmente sottolineato , il mio approccio ha una complessità temporale lineare … 🙁



(La prima versione.)

Puoi farlo passando un comparatore personalizzato a std::lower_bound() . Ecco una implementazione rudimentale come:

 #include  #include  #include  #include  #include  #include  using namespace std; template  class Set { private: struct custom_comparator { bool operator()(const unique_ptr& a, const T* const & b){ return a.get() < b; } } cmp; set> 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&& 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 mySet; unique_ptr a{new T("a")}; unique_ptr b{new T("b")}; unique_ptr 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(); } 

Stai usando dei pinters unici qui. Questo significa che il tuo set ha una proprietà esclusiva degli oggetti. Ora, questo dovrebbe significare che se l’object esiste, è nell’insieme o con un puntatore univoco. In questo caso non è nemmeno necessario cercare il set.

Ma a me sembra che non sia il caso. Suppongo che tu stia meglio con il puntatore condiviso in questo caso. Basta memorizzare i puntatori condivisi e passarli in giro poiché qualcuno accanto a questo set li memorizza chiaramente.