logo

TechCodeview

Estableix a la biblioteca de plantilles estàndard (STL) de C++

Els conjunts són un tipus de contenidor associatiu en què cada element ha de ser únic perquè el valor de l'element l'identifica. Els valors s'emmagatzemen en un ordre específic, és a dir, ascendent o descendent.

El std::set class és la part de la biblioteca de plantilles estàndard (STL) de C++ i es defineix dins del fitxer fitxer de capçalera.



Sintaxi:

vaja conceptes 
std::set set_name;>

Tipus de dades: Set pot prendre qualsevol tipus de dades en funció dels valors, p. int, char, float, etc.

Exemple: 



set val; // defining an empty set set val = {6, 10, 5, 1}; // defining a set with values>

Programa:

C++






// C++ Program to Demonstrate> // the basic working of STL> #include> #include> int> main()> {> >std::set<>char>>a;> >a.insert(>'G'>);> >a.insert(>'F'>);> >a.insert(>'G'>);> >for> (>auto>& str : a) {> >std::cout << str <<>' '>;> >}> >std::cout <<>' '>;> >return> 0;> }> 

>

>

per cada java
Sortida 

F G>

Complexitat temporal: O(N) // N és la mida del conjunt.

Espai auxiliar: O(N)

La raó per la qual només va imprimir F i G és que el conjunt no pren diversos valors iguals, només accepta un valor únic. Podem utilitzar Multiconjunt si volem emmagatzemar diversos valors iguals.

Conjunt ordenat en ordre descendent

Per defecte, l'estd::set s'ordena en ordre ascendent. Tanmateix, tenim l'opció de canviar l'ordre d'ordenació mitjançant la sintaxi següent.

std::set  set_name;>

Exemple:

C++




// C++ program to demonstrate the creation of descending> // order set container> #include> #include> using> namespace> std;> int> main()> {> >set<>int>, greater<>int>>> s1;> >s1.insert(10);> >s1.insert(5);> >s1.insert(12);> >s1.insert(4);> >for> (>auto> i : s1) {> >cout << i <<>' '>;> >}> >return> 0;> }> 

>

>

diferència entre $ i $$
Sortida 

12 10 5 4>

Complexitat temporal: O(N) // N és la mida del conjunt.

Espai auxiliar: O(N)

Nota: Podem utilitzar qualsevol comparador en lloc de major per oferir una ordenació d'ordres personalitzada.

Propietats

  1. Emmagatzematge de l'ordre - El conjunt emmagatzema els elements ordenat ordre.
  2. Valors Característiques – Tots els elements d'un conjunt tenen valors únics .
  3. Valors Natura – El valor de l'element no es pot modificar un cop s'ha afegit al conjunt, tot i que és possible eliminar i afegir el valor modificat d'aquest element. Així, els valors són immutable .
  4. Tècnica de cerca – Els conjunts segueixen el Arbre de cerca binari implementació.
  5. Ordenació de l'ordre - Els valors d'un conjunt són sense indexar .

Nota: Per emmagatzemar els elements en un ordre no ordenat (aleatori), conjunt_desordenat() pot ser utilitzat.

Algunes funcions bàsiques associades a Set

  • començar () – Retorna un iterador al primer element del conjunt.
  • final() – Retorna un iterador a l'element teòric que segueix l'últim element del conjunt.
  • mida () – Retorna el nombre d'elements del conjunt.
  • mida_màx () – Retorna el nombre màxim d'elements que pot contenir el conjunt.
  • buit() – Retorna si el conjunt està buit.

Les complexitats temporals per fer diverses operacions als platós són:

  • Inserció d'elements - O (log N)
  • Supressió d'elements - O (log N)

CPP




// C++ program to demonstrate various functions of> // STL> #include> #include> #include> using> namespace> std;> int> main()> {> >// empty set container> >set<>int>, greater<>int>>> s1;> >// insert elements in random order> >s1.insert(40);> >s1.insert(30);> >s1.insert(60);> >s1.insert(20);> >s1.insert(50);> >// only one 50 will be added to the set> >s1.insert(50);> >s1.insert(10);> >// printing set s1> >set<>int>, greater<>int>>>::iterator itr;> >cout <<>' The set s1 is : '>;> >for> (itr = s1.begin(); itr != s1.end(); itr++) {> >cout << *itr <<>' '>;> >}> >cout << endl;> >// assigning the elements from s1 to s2> >set<>int>>s2(s1.begin(), s1.end());> >// print all elements of the set s2> >cout <<>' The set s2 after assign from s1 is : '>;> >for> (itr = s2.begin(); itr != s2.end(); itr++) {> >cout << *itr <<>' '>;> >}> >cout << endl;> >// remove all elements up to 30 in s2> >cout <<>' s2 after removal of elements less than 30 '> >': '>;> >s2.erase(s2.begin(), s2.find(30));> >for> (itr = s2.begin(); itr != s2.end(); itr++) {> >cout << *itr <<>' '>;> >}> >// remove element with value 50 in s2> >int> num;> >num = s2.erase(50);> >cout <<>' s2.erase(50) : '>;> >cout << num <<>' removed '>;> >for> (itr = s2.begin(); itr != s2.end(); itr++) {> >cout << *itr <<>' '>;> >}> >cout << endl;> >// lower bound and upper bound for set s1> >cout <<>'s1.lower_bound(40) : '> ><< *s1.lower_bound(40) << endl;> >cout <<>'s1.upper_bound(40) : '> ><< *s1.upper_bound(40) << endl;> >// lower bound and upper bound for set s2> >cout <<>'s2.lower_bound(40) : '> ><< *s2.lower_bound(40) << endl;> >cout <<>'s2.upper_bound(40) : '> ><< *s2.upper_bound(40) << endl;> >return> 0;> }> 

>

>

npm esborra la memòria cau
Sortida 

The set s1 is : 60 50 40 30 20 10 The set s2 after assign from s1 is : 10 20 30 40 50 60 s2 after removal of elements less than 30 : 30 40 50 60 s2.erase(50) : 1 removed 30 40 60 s1.lower_bound(40) : 40 s1.upper_bound(40) : 30 s2.lower_bound(40) : 40 s2.upper_bound(40) : 60>

Funció diferent del conjunt en C++ STL

Funció Descripció
començar () Retorna un iterador al primer element del conjunt.
final() Retorna un iterador a l'element teòric que segueix l'últim element del conjunt.
rbegin() Retorna un iterador invers que apunta a l'últim element del contenidor.
render () Retorna un iterador invers que apunta a l'element teòric just abans del primer element del contenidor de conjunt.
crbegin() Retorna un iterador constant que apunta a l'últim element del contenidor.
crend() Retorna un iterador constant que apunta a la posició just abans del primer element del contenidor.
cbegin() Retorna un iterador constant que apunta al primer element del contenidor.
uns quants() Retorna un iterador constant que apunta a la posició més enllà de l'últim element del contenidor.
mida () Retorna el nombre d'elements del conjunt.
mida_màx () Retorna el nombre màxim d'elements que pot contenir el conjunt.
buit() Retorna si el conjunt està buit.
inserir (const g) Afegeix un nou element 'g' al conjunt.
insert d'iterador (posició de l'iterador, const g) Afegeix un nou element 'g' a la posició assenyalada per l'iterador.
esborrar (posició de l'iterador) Elimina l'element a la posició assenyalada per l'iterador.
esborrar (const g) Elimina el valor 'g' del conjunt.
clar () Elimina tots els elements del conjunt.
key_comp() / valor_comp() Retorna l'objecte que determina com estan ordenats els elements del conjunt ('<' per defecte).
trobar (const g) Retorna un iterador a l'element 'g' del conjunt si es troba, sinó torna l'iterador al final.
comptar (const g) Retorna 1 o 0 en funció de si l'element 'g' està present al conjunt o no.
límit_inferior (const g) Retorna un iterador al primer element que és equivalent a 'g' o que definitivament no anirà abans de l'element 'g' al conjunt.
límit_superior (const g) Retorna un iterador al primer element que anirà després de l'element 'g' del conjunt.
rang_igual() La funció retorna un iterador de parells. (key_comp). La parella fa referència al rang que inclou tots els elements del contenidor que tenen una clau equivalent a k.
emplace () Aquesta funció s'utilitza per inserir un element nou al contenidor del conjunt, només si l'element a inserir és únic i encara no existeix al conjunt.
emplace_hint() Retorna un iterador que apunta a la posició on es fa la inserció. Si l'element passat al paràmetre ja existeix, retorna un iterador que apunta a la posició on es troba l'element existent.
intercanviar () Aquesta funció s'utilitza per intercanviar el contingut de dos jocs, però els conjunts han de ser del mateix tipus, encara que les mides poden ser diferents.
operador= El '=' és un operador en C++ STL que copia (o mou) un conjunt a un altre conjunt i set::operator= és la funció d'operador corresponent.
get_allocator() Retorna la còpia de l'objecte assignador associat al conjunt.

Diferència entre conjunt i conjunt no ordenat

Conjunt

Conjunt no ordenat
Set emmagatzema elements en un ordre ordenat El conjunt no ordenat emmagatzema els elements en un ordre no ordenat
Estableix botigues/adquireix només elements únics No ordenat Estableix emmagatzema/adquireix només valors únics
El conjunt utilitza arbres de cerca binaris per a la implementació El conjunt no ordenat utilitza taules hash per a la implementació
Es pot esborrar més d'un element donant l'iterador inicial i final Podem esborrar aquell element per al qual es dóna la posició de l'iterador
set Set_Name; unordered_set UnorderedSet_Name;

Per a més informació, podeu consultar l'article - Sets vs conjunt no ordenat .