SET I C++ STANDARD TEMPLATE LIBRARY (STL) - TECHCODEVIEW.COM

Uppsättningar är en typ av associativ behållare där varje element måste vara unikt eftersom värdet på elementet identifierar det. Värdena lagras i en specifik sorterad ordning, dvs antingen stigande eller fallande.

De std::set klass är en del av C++ Standard Template Library (STL) och den är definierad inuti header-fil.

Syntax:

std::set set_name;

Data typ: Set kan ta vilken datatyp som helst beroende på värdena, t.ex. int, char, float, etc.

Exempel:

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

Program:

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;> }>

Produktion

F G

Tidskomplexitet: O(N) // N är storleken på mängden.

Hjälputrymme: PÅ)

Anledningen till att det bara skrevs ut F och G är att uppsättningen inte tar flera samma värden utan bara accepterar ett unikt värde. Vi kan använda Multiset om vi vill lagra flera samma värden.

Uppsättningen sorterad i fallande ordning

Som standard sorteras std::set i stigande ordning. Vi har dock möjlighet att ändra sorteringsordningen genom att använda följande syntax.

std::set  set_name;

Exempel:

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;> }>

Produktion

12 10 5 4

Tidskomplexitet: O(N) // N är storleken på mängden.

Hjälputrymme: PÅ)

Notera: Vi kan använda vilken komparator som helst i stället för större för att ge en anpassad sortering.

Egenskaper

Lagring av order – Setet lagrar elementen i sorterad beställa.
Värden Egenskaper – Alla element i en uppsättning har unika värden .
Värderar naturen – Värdet på elementet kan inte ändras när det väl har lagts till i uppsättningen, men det är möjligt att ta bort och sedan lägga till det modifierade värdet för det elementet. Alltså värdena är oföränderlig .
Sökteknik – Uppsättningar följer Binärt sökträd genomförande.
Ordna ordning – Värdena i en uppsättning är oindexerad .

Notera: För att lagra elementen i en osorterad (slumpmässig) ordning, unordered_set() kan användas.

Några grundläggande funktioner associerade med Set

Börja() – Returnerar en iterator till det första elementet i uppsättningen.
slutet() – Returnerar en iterator till det teoretiska elementet som följer efter det sista elementet i mängden.
storlek() – Returnerar antalet element i uppsättningen.
max_size() – Returnerar det maximala antalet element som uppsättningen kan innehålla.
tömma() – Returnerar om uppsättningen är tom.

Tidskomplexiteten för att utföra olika operationer på uppsättningar är:

Insättning av element – O(log N)
Radering av element – 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;> }>

Produktion

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

Olika funktioner för Set i C++ STL

Fungera	Beskrivning
Börja()	Returnerar en iterator till det första elementet i uppsättningen.
slutet()	Returnerar en iterator till det teoretiska elementet som följer efter det sista elementet i mängden.
rbegin()	Returnerar en omvänd iterator som pekar på det sista elementet i behållaren.
framställa()	Returnerar en omvänd iterator som pekar på det teoretiska elementet precis före det första elementet i uppsättningsbehållaren.
crbegin()	Returnerar en konstant iterator som pekar på det sista elementet i behållaren.
crend()	Returnerar en konstant iterator som pekar på positionen precis före det första elementet i behållaren.
cbegin()	Returnerar en konstant iterator som pekar på det första elementet i behållaren.
några()	Returnerar en konstant iterator som pekar på positionen förbi det sista elementet i behållaren.
storlek()	Returnerar antalet element i uppsättningen.
max_size()	Returnerar det maximala antalet element som uppsättningen kan innehålla.
tömma()	Returnerar om uppsättningen är tom.
infoga (konst g)	Lägger till ett nytt element 'g' till uppsättningen.
iterator insert (iterator position, const g)	Lägger till ett nytt element 'g' vid den position som iteratorn pekar på.
radera (iteratorposition)	Tar bort elementet vid den position som iteratorn pekar på.
radera(konst g)	Tar bort värdet 'g' från uppsättningen.
klar()	Tar bort alla element från setet.
key_comp() / värde_komp()	Returnerar objektet som bestämmer hur elementen i uppsättningen är ordnade (' <' som standard).
hitta (konst g)	Returnerar en iterator till elementet 'g' i uppsättningen om den hittas, annars returnerar iteratorn till slutet.
räkna (konst g)	Returnerar 1 eller 0 baserat på om elementet 'g' finns i mängden eller inte.
nedre_gräns(konst g)	Returnerar en iterator till det första elementet som är ekvivalent med 'g' eller som definitivt inte kommer att gå före elementet 'g' i uppsättningen.
upper_bound(const g)	Returnerar en iterator till det första elementet som kommer efter elementet 'g' i uppsättningen.
lika_intervall()	Funktionen returnerar en iterator av par. (key_comp). Paret hänvisar till intervallet som inkluderar alla element i behållaren som har en nyckel som motsvarar k.
emplace()	Denna funktion används för att infoga ett nytt element i uppsättningsbehållaren, endast om elementet som ska infogas är unikt och inte redan finns i uppsättningen.
emplace_hint()	Returnerar en iterator som pekar på positionen där infogningen görs. Om elementet som skickas i parametern redan existerar, returnerar det en iterator som pekar på positionen där det befintliga elementet är.
byta()	Denna funktion används för att utbyta innehållet i två set men seten måste vara av samma typ, även om storlekarna kan skilja sig åt.
operator=	'=' är en operator i C++ STL som kopierar (eller flyttar) en uppsättning till en annan uppsättning och set::operator= är motsvarande operatorfunktion.
get_allocator()	Returnerar kopian av allokeringsobjektet som är associerat med uppsättningen.

Skillnaden mellan uppsättning och oordnad uppsättning

Uppsättning	Oordnat set
Set lagrar element i en sorterad ordning	Oordnad uppsättning lagrar element i osorterad ordning
Ställ in butiker/skaffa endast unika element	Oordnat set lagrar/skaffar endast unika värden
Set använder binära sökträd för implementering	Unordered Set använder Hash-tabeller för implementering
Mer än ett element kan raderas genom att ge start- och slutiteratorn	Vi kan radera det element för vilket iteratorpositionen är given
set Set_Name;	unordered_set UnorderedSet_Name;