Container-ul bitset (STL)
9Urmatorul articol prezinta avantajele folosirii container-ului bitset din STL (Standard Template Library) si cateva elemente specifice acestuira. Mentionez de la inceput ca pentru o intelegere completa sunt necesare cunostintele de baza in ceea ce priveste STL.
-
Ce este bitset ?
Bitset este un container special creat pentru a retine biti (0 sau 1, true sau fals). Seamana cu un array obisnuit, insa diferentele sunt vadite cand vine vorba despre alocarea memoriei : fiecare element „consuma” exact un bit, ceea ce este de opt ori mai putin decat cel mai mic tip al limbajului C++, char).
Fiecare element poate fi accesat prin pozitia sa. De exemplu avem :
1000010
unde primul bit (bits[0]) are valoarea 0, al doilea are valoarea 1, al treilea valoarea 0 si tot asa. Observam ca bitii sunt numerotati de la 0 incepand din dreapta.
-
Cum declaram si citim un container de tip bitset ?
Pentru a declara un container de tip bitset trebuie sa includem in lista de preprocesare elementul :
#include <bitset>
insotit de
using namespace std;
Declarare propriu-zisa se face astfel :
bitset <8> bits;
Ceea ce inseamna ca am declarat un container numit bits, de 8 elemente (fiecare ocupand cate un bit) de tip bitset.
Citirea se realizeaza astfel :
cout << "Introduceti elementele : "; Â Â /* facultativ */cin >> bits;
Putem defini elementele containerului si astfel :
bitset <4> first (string("1001")); /* putem declara un bitset si ca string */
-
Cum afisam elementele unui bitset ?
Afisam elementele containerului folosindu-ne de variabile.
void afisare (){int i;for (i=0; i<n; ++i) Â Â Â Â Â /* n este numarul de elemente din container */cout << bits[i] << " ";}
Sa vedem acum cateva functii care ne ajuta sa lucram cu bitset :
-
Size ()
Size returneaza dimensiunea (numarul de elemente din container).
bitset <8> bits; cout << "In bits avem " << bits.size () << "elemente.\n";
-
Count ()
Functia .count () numara cate elemente cu valoara 1 se gasesc in container. Daca vrem sa aflam atat numarul de elemente cu valoarea 1, cat si numarul de elemente cu valoarea 0 din container, putem scadea valoare returnata de .count () din dimensiunea containerului (dimensiunea exacta se poate afla folosind.size () ).
bitset <5> bits (string("11010")); printf ("Bits contine %d elemente 1 si %d elemente 0\n", bits.count (), bits.size () - bits.count () );
-
None ()
Verifica daca toti bitii sunt diferiti de 1 (adica sunt 0). Va returna o valoare pozitiva (1) daca in container toate elementele au valoarea 0 si o valoare egala cu 0 daca avem cel putin un element cu valoarea 1.
bitset <5> bits; if (bits.none ()) printf ("In bits toate elementele sunt 0\n"); else printf ("In bits avem cel putin un element cu valorea 1\n");
-
Any ()
Verfica daca exista vreun element cu valoarea 1 in container. Va returna valoarea 0 daca nu avem niciun element cu valoarea 1 si 1 invers.
bitset <5> bitset; if (!bits.any ()) printf ("Nu avem niciun element cu valoarea 1\n"); else printf ("Avem cel putin un element cu valoarea 1\n");
-
Set  ()
Set () fara paramentru transforma toate elementele in 1. Parametrii pe care ii putem specifica sunt :
set (x, y) unde x reprezinta pozitia bitului care va lua valoara y
set (x) unde x reprezinta pozitia care va lua valoarea 1
Exemplu :
bitset <4> bits;bits.set (); Â Â /* 1111 */ bits.set (1, 0); Â /*1101 */ bits.set (0, 0); Â /* 1100 */ bits.set (1); Â Â /* 1110 */
-
Reset ()
Reset () transforma toate elementele in 0.
bitset <4> bits; bits.set (); Â Â /* 1111 */ bits.reset (); Â /* 0000 */
-
Flip  ()
Flip () transforma toti bitii de 0 in 1 si invers.
bitset <5> bits (string("10011"));
bits.flip (); Â Â /* 01100 */
-
Test ()
Test () verifica daca un anumit bit este 0 sau 1.
bitset <5> bits (string("01011")); cout << "Containerul contine :\n"; cout << boolalpha; for (size_t i=0; Â i<bits.size();Â ++i) cout << bits.test (i)Â << "\n";Programul va afisa :
Containerul contine :
true
true
false
true
false
-
To_string ()
Transforma un container bitset intr-un string.
string sir; bitset<4> bits; Â /* Â 0000 */bits.set(); Â Â /* 1111 */sir = bits.to_string<char,char_traits<char>,allocator<char> > ();cout << "sir : " << sir << "\n";
-
To_ulong ()
O functie foarte folositoare (my favourite 🙂 ) este to_ulong () care transforma containerul in numar in baza 10.
bitset <4> bits; cin >> bits; cout << Â bits << " Â in baza 10 este <<Â Â bits.to_ulong () << "\n";
-
Incheiere
Pentru a intelege mai bine cele prezentate mai sus, va sfatuiesc sa implementati chiar voi functiile si sa experimentati cat mai mult. De asemenea, cateva probleme care cer si putina algoritmica s-ar putea rezolva folosind o structura de tip bitset :
O sursa comentata cu toate aceste functii aplicate poate fi consultata mai jos 🙂 :
lorem ipsum /* Program compilat cu Code :: Blocks Autor : Albulescu Cosmina (miculprogramator) */ #include <stdio.h> #include <bitset> #include <iostream> using namespace std; bitset <5> mybit;Â Â Â Â Â /* mybit este gol si are 20 de elemente */ bitset <4> first (string("1001"));Â Â Â Â Â /* putem declara un bitset si ca string, e mai useful */ bitset <4> second (string("1000")); bitset <4> test; int main () { printf ("Bitset este un container care retine in fiecare element o valoare 0 sau 1 (1 bit). Fiecare element din bitset ocupa fix 1 bit.\n"); printf ("Putem face referire la elementele din bitset cu ajutorul pozitiilor (ca la vector), spre exemplu mybitset[3] este al 3-lea element din mybitset\n\n"); printf ("Cateva operatii intre 2 containere bitset : \n\n"); cout << first << " & "<< second << " = " << (first & second) << "\n"; cout << first << " ^ " << second << " = " << (first ^ second) << "\n"; cout << first << " | " << second << " = " << (first | second) << "\n"; printf ("Introduceti un nr in binar (de 5 cifre): "); cin >> mybit;Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â /* mybit.count () numara valorile de 1 din container */ printf ("mybit are %d de 1 si %d de 0\n\n", int (mybit.count()), int(mybit.size() - mybit.count()));Â Â Â Â Â Â /* mybit.size() reprezinta marimea containerului , 5 in acest caz */ cout << "Vom transforma toate valorile de 1 in 0 si toate valorile 0 in 1, din nr cu ajutorul .flip() " << first << "\n"; first.flip ();Â Â Â Â Â /* cand aplicam .flip() fara paramentru actioneaza asupra intregului container */ cout << "Noul container arata asa : " <<Â first << "\n";Â Â Â /* cand aplicam .flip (x) schimba primele x valori */ if (first.none())Â Â Â Â Â Â Â Â Â Â /* .none() este 1 cand nu avem niciun bit 1 si 0 cand avem */ printf ("first nu are niciun bit 1\n\n"); else printf ("first are %d biti 1\n\n", int(first.count())); test[1] = 1; cout << test << "\n"; /* 0010 */ test[2] = 1; cout << test << "\n";Â /* 0110 */ test.reset ();Â Â Â Â Â /* Transformam toti bitii in 0 */ cout << test << "\n";Â Â /* 0000 */ test.set ();Â Â Â /* cand folosim .set() fara parametrii bitiii se transforma in 1 */ cout << test << "\n";Â Â /* 1111 */ test.set (1, 0); /* transformam primul bit in 1; .set(x, y) transforma bitul x in y */ cout << test << "\n";Â Â /* 1101 */ test.set (1);Â Â Â Â Â /* transformam inapoi bitul 1 in 1. .set (x) transforma bitul x in 1 pt ca nu am dat parametru y */ cout << test << "\n"; /* 1111*/ test.reset(); printf ("Introduceti un nr in bianr (4 cifre) : "); cin >> test; cout << test << " in baza 10 este : " << test.to_ulong();Â Â /* .to_ulong() transforma bitset-ul in nr natural ! DE TINUT MINTE !! */ printf ("\n\nBitset : done, sunt multe lucruri useful aici !\n\n"); return 0; }
Daca acest articol contine o greseala, selecteaza cuvintele sau fraza gresita si tasteaza combinatia de taste Shift + Enter sau apasa click aici pentru a o raporta. Multumim!
Felicitari pentru articol! Detaliat si bine structurat.
Multumesc pentru apreciere. 🙂
Un articol foarte util pentru toti cei care invata STL. Asteptam si altele la fel de bine scrise care sa trateze diverse containere ! Felicitari !
Cosmina, cu ce profa faci tu informatica ?
P.S Super articolul.
@ Salut Andrei. Din clasa a 6-a pana in clasa a 8-a am facut informatica , cu doamna profesoara Zaharia Simona . Ea m-a facut sa-mi placa 🙂 . De STL m-am apucat singura.
Acum nu mai invat in Galati, m-am inscris la ICHB in Bucuresti ( clasa a 9a ) .
Thanks a lot for feedback, guys ! 😀
Foarte interesant si bine detaliat articolul, felicitari pentru munca depusa si pentru faptul ca te-ai apucat de C++ (care la olimpiade te avantajeaza foarte mult). Daca te ții de treaba, cu siguranța vei face treaba buna pe olimpiade si concursuri (iar faptul ca te-ai mutat la turci este un avantaj).
Thanks! Interesant , vorba cuiva , bine structurat tot asa!
mersi mult!! articolul este foarte folositor pt cei care sant incepatori in c++/c (asa ca mine)
poate mai vedem si alte articole de la tine
Foarte bun articolul !!! Felicitari !
Pentru mai mult STL vizitati http://www.cplusplus.com/reference/stl/
Pentru bitset http://www.cplusplus.com/reference/stl/bitset/ (In stanga ecranului aveti pentru fiecare container functiile pe care le puteti aplica)
Eu de aici ma inspir pt STL si sincer sunt foarte multumit 😛