Kopas ir asociatīvā konteinera veids, kurā katram elementam ir jābūt unikālam, jo elementa vērtība to identificē. Vērtības tiek saglabātas noteiktā secībā, t.i., augošā vai dilstošā secībā.
The std::set klase ir C++ standarta veidņu bibliotēkas (STL) daļa, un tā ir definēta iekšā galvenes fails.
Sintakse:
papildinātājs pilns papildinātājs
std::set set_name;>
Datu tips: Kopā var būt jebkurš datu tips atkarībā no vērtībām, piem. int, char, float utt.
Piemērs:
set val; // defining an empty set set val = {6, 10, 5, 1}; // defining a set with values> Programma:
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;> }> |
>
>Izvade
F G>
Laika sarežģītība: O(N) // N ir kopas izmērs.
Palīgtelpa: O(N)
pilsēta ASV
Iemesls, kāpēc tas drukā tikai F un G, ir tāds, ka komplektam nav vajadzīgas vairākas vienādas vērtības, tā pieņem tikai unikālu vērtību. Varam izmantot Multiset ja vēlamies saglabāt vairākas vienādas vērtības.
Komplekts sakārtots dilstošā secībā
Pēc noklusējuma std::set tiek sakārtots augošā secībā. Tomēr mums ir iespēja mainīt kārtošanas secību, izmantojot šādu sintaksi.
std::set set_name;>
Piemērs:
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;> }> |
>
java parseint
>Izvade
12 10 5 4>
Laika sarežģītība: O(N) // N ir kopas izmērs.
Palīgtelpa: O(N)
Piezīme: Mēs varam izmantot jebkuru salīdzinājumu lielāka vietā, lai nodrošinātu pielāgotu secību šķirošanu.
Īpašības
- Pasūtījuma uzglabāšana - Komplektā tiek glabāti elementi sakārtoti pasūtījums.
- Vērtības Raksturlielumi – Visiem komplekta elementiem ir unikālas vērtības .
- Vērtības Daba – Elementa vērtību nevar mainīt, kad tas ir pievienots kopai, lai gan ir iespējams noņemt un pēc tam pievienot šī elementa modificēto vērtību. Tādējādi vērtības ir nemainīgs .
- Meklēšanas tehnika – Komplekti seko Binārais meklēšanas koks īstenošana.
- Kārtības sakārtošana - Kopā esošās vērtības ir neindeksēts .
Piezīme: Lai saglabātu elementus nešķirotā (nejaušajā) secībā, unordered_set() Var izmantot.
Dažas ar komplektu saistītās pamatfunkcijas
- sākt () – Atgriež iteratoru pirmajam kopas elementam.
- beigas () – Atgriež iteratoru uz teorētisko elementu, kas seko pēdējam kopas elementam.
- Izmērs() – Atgriež elementu skaitu komplektā.
- max_size() – Atgriež maksimālo elementu skaitu, ko komplektā var saturēt.
- tukšs () – Atgriež, ja komplekts ir tukšs.
Laika sarežģītība dažādu darbību veikšanai komplektos ir:
- Elementu ievietošana - O(log N)
- Elementu dzēšana - 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 notīrīt kešatmiņuIzvade
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>
Atšķirīga kopas funkcija C++ STL
| Funkcija | Apraksts |
|---|---|
| sākt () | Atgriež iteratoru pirmajam kopas elementam. |
| beigas () | Atgriež iteratoru teorētiskajam elementam, kas seko pēdējam kopas elementam. |
| rbegin() | Atgriež apgriezto iteratoru, kas norāda uz pēdējo konteinera elementu. |
| renderēt () | Atgriež apgriezto iteratoru, kas norāda uz teorētisko elementu tieši pirms pirmā elementa iestatītajā konteinerā. |
| crbegin() | Atgriež konstantu iteratoru, kas norāda uz pēdējo konteinera elementu. |
| crend () | Atgriež pastāvīgu iteratoru, kas norāda uz pozīciju tieši pirms pirmā elementa konteinerā. |
| cbegin() | Atgriež pastāvīgu iteratoru, kas norāda uz konteinera pirmo elementu. |
| daži() | Atgriež pastāvīgu iteratoru, kas norāda uz pozīciju aiz pēdējā konteinera elementa. |
| Izmērs() | Atgriež elementu skaitu komplektā. |
| max_size() | Atgriež maksimālo elementu skaitu, ko var saturēt kopā. |
| tukšs () | Atgriež, ja komplekts ir tukšs. |
| ievietot (konst. g) | Kopai pievieno jaunu elementu “g”. |
| iteratora ieliktnis (iteratora pozīcija, konst. g) | Iteratora norādītajā vietā pievieno jaunu elementu “g”. |
| dzēst (iteratora pozīcija) | Noņem elementu iteratora norādītajā pozīcijā. |
| dzēst (konst. g) | No kopas noņem vērtību “g”. |
| skaidrs () | No komplekta noņem visus elementus. |
| key_comp() / value_comp() | Atgriež objektu, kas nosaka, kā elementi tiek sakārtoti kopā (pēc noklusējuma '<'). |
| atrast (const g) | Atgriež iteratoru uz elementu “g” kopā, ja tas tiek atrasts, pretējā gadījumā atgriež iteratoru līdz beigām. |
| skaits (konst. g) | Atgriež 1 vai 0 atkarībā no tā, vai elements “g” ir vai nav kopā. |
| apakšējā_ robeža(konst. g) | Atgriež iteratoru uz pirmo elementu, kas ir līdzvērtīgs “g” vai noteikti neaizies pirms elementa “g” kopā. |
| augšējā_ robeža(konst. g) | Atgriež iteratoru uz pirmo elementu, kas komplektā ies aiz elementa “g”. |
| vienāds_diapazons() | Funkcija atgriež pāru iteratoru. (key_comp). Pāris attiecas uz diapazonu, kas ietver visus konteinera elementus, kuru atslēga ir ekvivalenta k. |
| emplace () | Šī funkcija tiek izmantota, lai ievietotu jaunu elementu kopas konteinerā, tikai tad, ja ievietojamais elements ir unikāls un komplektā jau neeksistē. |
| emplace_hint() | Atgriež iteratoru, kas norāda uz vietu, kur tiek veikta ievietošana. Ja parametrā nodotais elements jau pastāv, tas atgriež iteratoru, kas norāda uz vietu, kur atrodas esošais elements. |
| apmainīt () | Šo funkciju izmanto, lai apmainītos ar divu komplektu saturu, taču komplektiem ir jābūt viena veida, lai gan izmēri var atšķirties. |
| operators= | “=” ir operators C++ STL, kas kopē (vai pārvieto) kopu uz citu kopu, un set::operator= ir atbilstošā operatora funkcija. |
| get_allocator() | Atgriež ar kopu saistītā piešķirtāja objekta kopiju. |
Atšķirība starp komplektu un nesakārtotu komplektu
| Iestatīt | Nesakārtots komplekts |
|---|---|
| Iestatīt saglabā elementus sakārtotā secībā | Unordered Set saglabā elementus nešķirotā secībā |
| Iestatīt veikalus/iegādāties tikai unikālus elementus | Nekārtots Iestatīt saglabā/iegūst tikai unikālas vērtības |
| Ieviešanai komplekts izmanto bināros meklēšanas kokus | Nesakārtotā kopa ieviešanai izmanto jaucējtabulas |
| Vairāk nekā vienu elementu var izdzēst, norādot sākuma un beigu iteratoru | Mēs varam izdzēst to elementu, kuram ir norādīta iteratora pozīcija |
| iestatīt Set_Name; | unordered_set UnorderedSet_Name; |
Lai iegūtu vairāk informācijas, skatiet rakstu - Komplekti pret nesakārtoto komplektu .