Dividere un elenco STL?

Question

Ho un elenco collegato circolare che sembra qualcosa di simile:

4 -> 3 -> 2 -> 5 -> 0 -> 1 -> beginning

Voglio dividere questa lista in due segmenti, invertire uno dei segmenti, e poi ricongiungersi con la lista. Qualcosa di simile a questo:

Spalato, un O (1) Operazione 4 ** 3 -> 2 -> 5 ** 0 -> 1 -> beginning

inversa, un O (n) 0 ** 3 -> 2 -> 5 ** 4 -> 1 -> beginning

Rejoin, un O (1) Operazione 0 -> 3 -> 2 -> 5 -> 4 -> 1 -> beginning

Non sembra che STL abbia una lista circolare circolare, ma spero di riuscire a farla franca rappresentando la lista come una lista (in avanti). Questo, richiede: * Un modo per dividere le liste in sottoliste * Un modo per unire le liste insieme

La fusione delle liste parziali insieme dovrebbe essere facile utilizzando std::list::splice, e dovrebbe essere un O (1) il funzionamento. Sìì!

Tuttavia, non riesco a trovare un buon modo O (1) per dividere le liste in sottoliste. One approach utilizza gli iteratori, ma non penso che funzioni nel mio caso perché la sottolista esce dalla fine della lista e riprende all'inizio della lista.

Esiste un modo efficace per implementare questo algoritmo utilizzando l'STL? O dovrei semplicemente rinunciare e scrivere la mia biblioteca circolare collegata?

Grazie!

Answer 1

io non sono sicuro di come utile questa è, ma qui è:

template<typename I> 
void inner(I b, I e) 
{ 
    std::reverse(b, e); // l = {4 5 2 3 0 1} 
} 

template<typename L, typename I> 
void outer(L& l, I b, I e) 
{ 
    l.splice(l.begin(), l, e, l.end()); // l = {0 1 4 3 2 5} 
    std::reverse(l.begin(), b);   // l = {4 1 0 3 2 5} 
} 

int main() 
{ 
    std::list<int> t, l{4, 3, 2, 5, 0, 1}; 
    std::cout << l << std::endl; 

    auto b = l.begin(), e = l.begin(); 
    std::advance(b, 1); 
    std::advance(e, 4); 
    bool in = true; 

    in ? inner(b, e) : outer(l, b, e); 
    std::cout << l << std::endl; 
} 

ci sono due opzioni:

• invertire la interno parte della lista (3 2 5)
• invertire la parte esterna parte (0 1 -> 4)

e potresti voler invertire quello più corto, ma dovrai contare per questo, che è tempo lineare. Ho scritto due funzioni separate inner,outer per queste due attività.

inner è molto semplice (nient'altro che un involucro) e funziona come previsto. Tuttavia, outer lascia l'elenco in uno stato che è equivalente al modulo previsto di una certa rotazione (spostamento circolare). Se stai modellando una lista circolare, dovrebbe andare bene. Ma se vuoi l'output esattamente come nel tuo esempio, dovrai contare nuovamente, per trovare il punto giusto in cui ruotare. Eviterei questo, dato che è tempo lineare.

Si noti che nessuna divisione è effettivamente necessaria, perché l'inversione è sul posto. Inoltre, operazione

l.splice(l.begin(), l, e, l.end()); 

è un tempo costante.

Controllare live example.