Last Updated : 05 Jul, 2024
Comments
Improve
Summarize
Suggest changes
Like Article
Like
Save
Report
Sets are a type of associative container in which each element has to be unique because the value of the element identifies it. The values are stored in a specific sorted order i.e. either ascending or descending.
The std::set class is the part of C++ Standard Template Library (STL) and it is defined inside the <set> header file.
Syntax:
std::set <data_type> set_name;Datatype: Set can take any data type depending on the values, e.g. int, char, float, etc.
Example:
set<int> val; // defining an empty set
set<int> val = {6, 10, 5, 1}; // defining a set with values
Program:
// C++ Program to Demonstrate// the basic working of STL#include <iostream>#include <set>int main(){ std::set<char> a; a.insert('G'); a.insert('F'); a.insert('G'); for (auto& str : a) { std::cout << str << ' '; } std::cout << '\n'; return 0;}
Output
F G
Time complexity: O(N) // N is the size of the set.
Auxiliary Space: O(N)
The reason it printed only F and G is that set does not take multiple same values it only accepts a unique value. We can use Multiset if we want to store multiple same values.
Set Sorted in Descending Order
By default, the std::set is sorted in ascending order. However, we have the option to change the sorting order by using the following syntax.
std::set <data_type, greater<data_type>> set_name;Example:
// C++ program to demonstrate the creation of descending// order set container#include <iostream>#include <set>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;}
Output
12 10 5 4
Time complexity: O(N) // N is the size of the set.
Auxiliary Space: O(N)
Note: We can use any comparator in place of greater<data_type> to give set a custom order sorting.
Properties
- Storing order – The set stores the elements in sorted order.
- Values Characteristics – All the elements in a set have unique values.
- Values Nature – The value of the element cannot be modified once it is added to the set, though it is possible to remove and then add the modified value of that element. Thus, the values are immutable.
- Search Technique – Sets follow the Binary search tree implementation.
- Arrangingorder – The values in a set are unindexed.
Note: To store the elements in an unsorted(random) order, unordered_set() can be used.
Some Basic Functions Associated with Set
- begin() – Returns an iterator to the first element in the set.
- end() – Returns an iterator to the theoretical element that follows the last element in the set.
- size() – Returns the number of elements in the set.
- max_size() – Returns the maximum number of elements that the set can hold.
- empty() – Returns whether the set is empty.
The time complexities for doing various operations on sets are:
- Insertion of Elements – O(log N)
- Deletion of Elements – O(log N)
// C++ program to demonstrate various functions of// STL#include <iostream>#include <iterator>#include <set>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 << "\nThe set s1 is : \n"; 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 << "\nThe set s2 after assign from s1 is : \n"; for (itr = s2.begin(); itr != s2.end(); itr++) { cout << *itr << " "; } cout << endl; // remove all elements up to 30 in s2 cout << "\ns2 after removal of elements less than 30 " ":\n"; 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 << "\ns2.erase(50) : "; cout << num << " removed\n"; 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;}
Output
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 removed30 40 60 s1.lower_bound(40) : 40s1.upper_bound(40) : 30s2.lower_bound(40) : 40s2.upper_bound(40) : 60
Different Function of Set in C++ STL
| Function | Description |
|---|---|
| begin() | Returns an iterator to the first element in the set. |
| end() | Returns an iterator to the theoretical element that follows the last element in the set. |
| rbegin() | Returns a reverse iterator pointing to the last element in the container. |
| rend() | Returns a reverse iterator pointing to the theoretical element right before the first element in the set container. |
| crbegin() | Returns a constant iterator pointing to the last element in the container. |
| crend() | Returns a constant iterator pointing to the position just before the first element in the container. |
| cbegin() | Returns a constant iterator pointing to the first element in the container. |
| cend() | Returns a constant iterator pointing to the position past the last element in the container. |
| size() | Returns the number of elements in the set. |
| max_size() | Returns the maximum number of elements that the set can hold. |
| empty() | Returns whether the set is empty. |
| insert(const g) | Adds a new element ‘g’ to the set. |
| iterator insert (iterator position, const g) | Adds a new element ‘g’ at the position pointed by the iterator. |
| erase(iterator position) | Removes the element at the position pointed by the iterator. |
| erase(const g) | Removes the value ‘g’ from the set. |
| clear() | Removes all the elements from the set. |
| key_comp() / value_comp() | Returns the object that determines how the elements in the set are ordered (‘<‘ by default). |
| find(const g) | Returns an iterator to the element ‘g’ in the set if found, else returns the iterator to the end. |
| count(const g) | Returns 1 or 0 based on whether the element ‘g’ is present in the set or not. |
| lower_bound(const g) | Returns an iterator to the first element that is equivalent to ‘g’ or definitely will not go before the element ‘g’ in the set. |
| upper_bound(const g) | Returns an iterator to the first element that will go after the element ‘g’ in the set. |
| equal_range() | The function returns an iterator of pairs. (key_comp). The pair refers to the range that includes all the elements in the container which have a key equivalent to k. |
| emplace() | This function is used to insert a new element into the set container, only if the element to be inserted is unique and does not already exist in the set. |
| emplace_hint() | Returns an iterator pointing to the position where the insertion is done. If the element passed in the parameter already exists, then it returns an iterator pointing to the position where the existing element is. |
| swap() | This function is used to exchange the contents of two sets but the sets must be of the same type, although sizes may differ. |
| operator= | The ‘=’ is an operator in C++ STL that copies (or moves) a set to another set and set::operator= is the corresponding operator function. |
| get_allocator() | Returns the copy of the allocator object associated with the set. |
Difference between Set and Unordered Set
Set | Unordered Set |
|---|---|
| Set stores elements in a sorted order | Unordered Set stores elements in an unsorted order |
| Set stores/acquire unique elements only | Unordered Set stores/acquire only unique values |
| Set uses Binary Search Trees for implementation | Unordered Set uses Hash Tables for implementation |
| More than one element can be erased by giving the starting and ending iterator | We can erase that element for which the iterator position is given |
| set<datatype> Set_Name; | unordered_set<datatype> UnorderedSet_Name; |
For more information, you can refer to the article – Sets vs Unordered Set.
${secondsToHms(duration)}
${getTagsString(tags)}
'; } else{ let view_all_url = `${GFG_SITE_URL}videos/`; videos_content+=`
View All
`; } // videos_content+= '
'; } } return videos_content; } //function to show main video content with related videos content async function showMainVideoContent(main_video, course_link){ //Load main video $(".video-main").html(`
`); require(["ima"], function() { var player = videojs('article-video', { controls: true, // autoplay: true, // muted: true, controlBar: { pictureInPictureToggle: false }, playbackRates: [0.5, 0.75, 1, 1.25, 1.5, 2], poster: main_video['meta']['largeThumbnail'], sources: [{src: main_video['source'], type: 'application/x-mpegURL'}], tracks: [{src: main_video['subtitle'], kind:'captions', srclang: 'en', label: 'English', default: true}] },function() { player.qualityLevels(); try { player.hlsQualitySelector(); } catch (error) { console.log("HLS not working - ") } document.getElementById('article-video-tab-content').style.display = 'block'; } ); const video = document.querySelector("video"); const events =[ { 'name':'play', 'callback':()=>{videoPlayCallback(main_video['slug'])} }, ]; events.forEach(event=>{ video.addEventListener(event.name,event.callback); }); // error handling for no compatible source player.on('error', function() { var error = player.error(); console.log("Video Error: ", error); if (error && error.code === 4) { console.log("No compatible source was found for this media."); hideVideoPlayer(); } }); }, function(err) { var player = videojs('article-video'); player.createModal('Something went wrong. Please refresh the page to load the video.'); hideVideoPlayer(); // hiding video in case of timeout (requirejs) console.log(err); }); // function to hide the video player function hideVideoPlayer() { var videoPlayer = document.getElementById('article-video'); if (videoPlayer) { videoPlayer.parentNode.removeChild(videoPlayer); } } /*let video_date = main_video['time']; video_date = video_date.split("/"); video_date = formatDate(video_date[2], video_date[1], video_date[0]); let share_section_content = `
${video_date}
`;*/ let hasLikeBtn = false; // console.log(share_section_content); var data = {}; if(false){ try { if((loginData && loginData.isLoggedIn == true)){ const resp = await fetch(`${API_SCRIPT_URL}logged-in-video-details/${main_video['slug']}/`,{ credentials: 'include' }) if(resp.status == 200 || resp.status == 201){ data = await resp.json(); share_section_content+= `
`; hasLikeBtn = true; } else { share_section_content+= `
`; } } else { share_section_content+= `
`; } //Load share section // $(".video-share-section").html(share_section_content); // let exitCond = 0; // const delay = (delayInms) => { // return new Promise(resolve => setTimeout(resolve, delayInms)); // } // while(!loginData){ // let delayres = await delay(1000); // exitCond+=1; // console.log(exitCond); // if(exitCond>5){ // break; // } // } // console.log(loginData); /*if(hasLikeBtn && loginData && loginData.isLoggedIn == true){ setLiked(data.liked) setSaved(data.watchlist) }*/ } catch (error) { console.log(error); } } //Load video content like title, description if(false){ $(".video-content-section").html(`
${main_video['title']}
${hideMainVideoDescription(main_video['description'], main_video['id'])}
${getTagsString(main_video['category'])} ${(course_link.length)? `
View Course
`:''} `); let related_vidoes = main_video['recommendations']; if(!!videos && videos.length>0){ //Load related videos $(".related-videos-content").html(getvideosContent()); } } //show video content // element = document.getElementById('article-video-tab-content'); // element.style.display = 'block'; $('.spinner-loading-overlay:eq(0)').remove(); $('.spinner-loading-overlay:eq(0)').remove(); } await showMainVideoContent(video_data, course_link); // fitRelatedVideosDescription(); } catch (error) { console.log(error); } } getVideoData(); /* $(window).resize(function(){ onWidthChangeEventsListener(); }); $('#video_nav_tab').click('on', function(){ fitRelatedVideosDescription(); });*/ });
