Perché lo std :: swap di bit in un'istanza di std :: bitset non funziona?

Question

Nell'esempio seguente mi aspettavo lo scambio dei bit. Invece il secondo bit viene sovrascritto, ma perché e come posso ottenere il comportamento previsto?

#include <iostream> 
#include <string> 
#include <algorithm> 

using namespace std; 

int main() 
{ 
    bitset<2> test(string("10")); 
    cout << test; // Prints "10" 
    swap(test[0], test[1]); 
    cout << test; // Prints "11", why not "01"? 
} 

Answer 1

Questo è puro brutto. Per prima cosa dobbiamo guardare la dichiarazione di swap:

template<class T> 
void swap(T &left, T &right); 

Ora, operator[]() su bitset ha due overload:

bool operator[](size_type _Pos) const; 
reference operator[](size_type _Pos); 

Qui reference è bitset::reference, una classe annidata in bitset che agisce in modo efficace come un proxy riferimento a uno dei bit sottostanti. Ciò che incapsula è il bitset e una posizione nel bitset. A causa della dichiarazione di swap, il secondo overload viene scelto e stiamo scambiando due bitset::reference s. Ora qui è dove diventa cattivo. Diamo un'occhiata a una tipica implementazione di swap:

template class<T> swap(T &left, T &right) { 
    T temp = left; 
    left = right; 
    right = temp; 
} 

Il problema è che left e right sono entrambi riferimenti a un bitset::reference. Hanno gli stessi dati sottostanti (perché sono dei proxy, lo stesso significato che entrambi puntano allo stesso bitset!) Incapsulano semplicemente diverse posizioni in quello bitset.Quindi, pensa in questo modo left è la posizione 0 in alcuni bitset e right è la posizione 1 in alcuni bitset e che bitset è lo stesso bitset come left! Facciamo sempre riferimento a questo bitset come BS (scelto intenzionalmente).

Quindi,

T temp = left; 

dice che temp è la posizione 0 in BS.

left = right; 

insiemi di posizione 0 in sinistra posizione 1 BS (che cambia simultaneamente posizione 0 temp!)

right = temp; 

insiemi posizione 1 a destra per posizionare 0 a BS (che è stato appena impostato posizione 1 in BS!). Quindi alla fine di questo casino, la posizione 0 è quella che era la posizione 1 e la posizione 1 è invariata! Ora, poiché la posizione 0 è l'LSB e la posizione 1 è l'MSB, abbiamo che "10" diventa "11". Brutta.

È possibile aggirare il problema con un template specialization:

namespace std { 
    template<> 
    void swap<bitset<2>::reference>(
     bitset<2>::reference &left, 
     bitset<2>::reference &right 
    ) { 
     bool temp = (bool)left; 
     left = (bool)right; 
     right = (bool)temp; 
    } 
} 

Poi:

int main() { 
    bitset<2> test(string("10")); 
    cout << test; // Prints "10" 
    swap(test[0], test[1]); 
    cout << test; // Prints "01", hallelujah! 
} 

Answer 2

In realtà, dal momento che i rendimenti test[i] un rvalue di riferimento bitset, io non capisco come swap può compilare qui. Il mio compilatore (g ++ 4.3.3) mi dice:

test.cpp:12: error: no matching function for call to 
    'swap(std::bitset<2u>::reference, std::bitset<2u>::reference)' 
/usr/include/c++/4.3/bits/stl_move.h:80: note: candidates are: 
    void std::swap(_Tp&, _Tp&) [with _Tp = std::bitset<2u>::reference] 

Answer 3

Non c'è alcun tipo di valore in C++ per rappresentare un singolo bit, in modo che quando si utilizza l'operatore [] per accedere a un elemento di un bitset, quello che si ottiene è un oggetto proxy che serve come un alias per il bit richiesto. L'assegnazione a quell'oggetto proxy modifica il valore di bit corrispondente nell'oggetto bitset originale.

Come Victor's answer spettacoli, il codice non viene compilato con GCC. Ma supponiamo che la chiamata a swap si compili. Si otterrebbe codice che equivale a qualcosa di simile:

void swap(std::bitset<2>::reference& a, std::bitset<2>::reference& b) 
{ 
    std::bitset<2>::reference tmp = a; 
    a = b; 
    b = tmp; 
} 

La dichiarazione tmp inizializza la variabile con a, ma che non fa una copia del bit. Invece, si esegue una copia dell'oggetto proxy, così tmpriferisce allo stesso bit nella stessa bitset che a riferisce a. La riga successiva assegna b a a, che copia il valore di bit dalla posizione a fa riferimento e memorizza nella posizione di bit b riferisce a. Infine, c'è l'assegnazione di tmp in b. Ma ricorda che tmp fa ancora riferimento al bit a cui fa riferimento a. La lettura tmp è lo stesso di lettura a, quindi in ultima analisi, ottiene lo stesso effetto che si otterrebbe se swap erano solo queste due righe:

a = b; 
b = a; 

Nel codice, a è 0 e b è 1, quindi con quelli due dichiarazioni di assegnazione, 11 è esattamente ciò che ci aspetteremmo di vedere.