Ottieni elementi casuali e rimuovilo

Question

Problema: ho bisogno di ottenere un elemento casuale per un contenitore e di cancellarlo anche da quel contenitore. Il contenitore non ha bisogno di essere ordinato. Non mi interessa l'ordine.

• Vector me può ottenere elemento casuale in O(1) ma eliminarlo solo nel O(N)
• Lista cancella elemento O(1) ma può ottenere solo elemento casuale in O(N)

Così mi è venuta un'idea di creare un vettore personalizzato che consente di rimuovere qualsiasi elemento dal suo indice con la complessità O(1)+. L'idea è di scambiare l'ultimo elemento e un elemento che si desidera rimuovere e quindi pop_back(). Se è necessario rimuovere l'ultimo elemento - solo pop_back(). L'ordine del vettore non sarà lo stesso ma si ottiene un metodo di rimozione veloce.

Come posso capire che deque ha un accesso più lento per indice e una complessità di rimozione peggiore della mia soluzione, ma non sono sicuro al 100%.

Sono curioso ci sono strutture di dati che hanno accesso casuale e rimozione elemento in O(1) o O(logN) per indice o mb per valore?

Answer 1

Hai la soluzione, e sembra perfettamente a posto. Il modo idiomatico di scrivere in C++ è di non creare un'altra classe (e pregadon't inherit from std::vector), ma solo per scrivere una funzione:

template <typename T> 
void remove_at(std::vector<T>& v, typename std::vector<T>::size_type n) 
{ 
    std::swap(v[n], v.back()); 
    v.pop_back(); 
} 

Usage:

remove_at(v, 42); 

Questo offre la stessa eccezione garanzia come std::swap<T>.

Ora se si desidera restituire l'oggetto e si ha accesso a un compilatore C++ 11, è possibile farlo nel modo seguente. La parte difficile è quello di fornire la garanzia eccezione di base in tutti i casi:

template <typename T> 
T remove_at(std::vector<T>&v, typename std::vector<T>::size_type n) 
{ 
    T ans = std::move_if_noexcept(v[n]); 
    v[n] = std::move_if_noexcept(v.back()); 
    v.pop_back(); 
    return ans; 
} 

In effetti, non si vuole il vettore per essere lasciato in uno stato non valido se viene generata un'eccezione durante un'operazione di spostamento.

Answer 2

Con O (n) la complessità

vec.erase (vec.begin() + randomIdx); randomIdx dovrebbe essere compreso tra 0 e vec.size() - 1

Se si desidera la complessità O (1), è possibile utilizzare il contenitore dell'elenco per esempio oppure scambiare l'elemento con l'ultimo e cancellarlo. (Come menzionato dagli altri)

Answer 3

Sì, c'è una soluzione, un albero binario ben bilanciato.

Per ogni nodo è necessario memorizzare il numero di nodi su ciascun lato. Da questo è O (log N) per trovare l'ennesimo elemento.

La rimozione dell'ennesimo elemento è anch'essa O (log N) come si deve attraversare indietro all'albero per correggere tutti i conteggi. Qualsiasi ribilanciamento sarebbe O (log N) anche al massimo.

Un albero è considerato ben bilanciato se nessun nodo foglia è più profondo di 2 nodi rispetto a un altro. Cerca gli alberi AVL per ottenere un algoritmo di rabalancing.

In realtà sarebbe utile se la libreria standard "aprisse" l'uso degli alberi utilizzati per std :: set e std :: map come interfaccia pubblica da utilizzare in alberi personalizzati.