Skip to main content

set

set is an Associative Container that contains a sorted set of UNIQUE objects of type Key. Sorting is done using the key comparison function Compare. Search, removal, and insertion operations have logarithmic complexity O(long n). Sets are usually implemented as red-black trees​

Declaration​

Initialisation​

Initialising set from vector​

set<int> st(vec.begin(), vec.end());

Initialising set from deque​

set<int> st(dequeName.begin(), dequeName.end());

Not available in set​

Index Number not available with set​

caution
  • Element Access using Index Number is not possible
  • NO methods are available for element access in set

insert(positon, begin(), end()) not available with set​

caution
  • Can't copy elements from other Data Sructures like deque pr vector into set

Must Refer and Research: https://www.google.com/search?q=element+access+in+set+c%2B%2B&oq=element+access+in+set+c%2B%2B&aqs=chrome..69i57j0i22i30l3j0i390l2.10800j0j7&sourceid=chrome&ie=UTF-8

TO ADD Other Topics

set Methods​

Modifiers​

insert()​

  • Inserts elements or nodes

erase()​

clear()​

swap()​

extract()​

merge()​

emplace()​

emplace_hint()​

Lookup​

💣 binary_search() from STL MUST not be used with set, multiset, map, multimap. 💣​

caution
  • use find() for search element's Index No.
  • use contains() for checking element present or not: ⇢⇢ ☠️ Don't use binary_search() ☠️
    • returns true or false ~~ from C++ 20
  • use count() for checking element present or not: ⇢⇢ ☠️ Don't use binary_search() ☠️
    • returns 1 or 0

💣 binary_search() from STL MUST not be used with set, multiset, map, multimap. 💣​

  • binary_search() becomes O(n) when used with set, multiset, map, multimap, unordered_set, unordered_multiset, unordered_map, unordered_multimap.

  • All the Associative Containers have O(log n) alternative of binary_search() ↠

    • find() for IndexNo. of target search element

    • contains() for element present or not -- true or false

    • count() for element present or not -- 1 or 0

    • lower_bound() ⇢ container's own lower_bound()

    • upper_bound() ⇢ container's own upper_bound()

    • equal_range() ⇢ container's own equal_range()

      unordered_set, unordered_multiset, unordered_map, unordered_multimap don't have lower_bound() , upper_bound()

Hence, binary_search() must not be used with Associative Containers

tip

  • https://discuss.codechef.com/t/set-find-vs-binary-search-help-needed-asap/23991/6

  • binary_search has a logarithmic time complexity only for LegacyRandomAccessIterators . This is the case of std::vector iterators, for example. Sets/multisets are trees, so their iterators don’t allow random access. This makes binary_search() run in linear time, which is significantly slower for a large range. This is why std::set and std::multiset have a “find” function, while vector doesn’t. They need their own binary search implementation to be able to run in logarithmic time.

  • For instance, if your range spans over 1000 elements, binary_search() will want to look at the element at position 500 first. Vector iterators are more or less pointers, it’s easy to do begin + 500 with pointer arithmetics. Since the elements are sorted, we can remove half of the range with a single comparison. That’s why binary_search() is very efficient, with logarithmic complexity.

  • ❎ BUT, In a set or multiset, nodes that are neighbors in the tree are not necessarily neighbors in memory. So, binary_search() would not even be able to know how many elements are in the range, end - begin is not supported. So the search starts at begin the iterator is incremented, until it reaches a value not lower than the one we are searching for. This is why binary_search() has poor performance with sets, and you should use the find() function provided by that particular container, that has a more suitable search strategy.

find()​

caution

Time Complexity is :~ O(log n)​

caution
  • element present -- ( it != setName.end() );
    • because find() funtion in map or set returns Iterator to an element with key equivalent to key. If no such element is found, end() iterator is returned.
  • element NOT present -- ( it == setName.end() );
if (it != setName.end())
{
    cout << "Found " << (*it) << endl;
}
 set<int> setName = {1, 2, 3, 4};

    auto search = setName.find(2);    // iterator to store the location
    if (search != setName.end()) {    // if iterator value is not the end(), i.e. element is present.
    // if iterator value == end(), i.e. element is NOT present.
        cout << "Found " << (*search) << '\n';
    } else {
        cout << "Not found\n";
    }

count()​

caution

Time Complexity is :~ O(log n)​

  • setName.count(targetValue)

count() accepts the element as argument and search for its number of occurrence count in the set. As set can contain only unique elements, so occurrence count of the given element can be only 0 or 1 i.e, If found then 1 else 0

tip
  • count() returns 1 if the set or map contains the element and 0 if it doesn't.

contains() ~~ C++ 20​

caution

Time Complexity is :~ O(log n)​

  • contains() returns true if the set or map contains the element and false if it doesn't.

lower_bound()​

  • unodered_set has no member lower_bound or upper_bound
caution

Time Complexity is :~ O(log n)​

Returns: Iterator pointing to first element equal to or greater than key, or end().

  • If element/key is present This function returns the first element of a subsequence of elements that matches the given key.

  • If element not present it returns an iterator pointing to the first element that has a greater value than given key or end() if no such element exists.

info

lower_bound(v.begin(), v.end(), key) - v.begin()

  • Must be like this -> lower_bound(v.begin(), v.end(), key) - v.begin() because lower_bound() returns iterator and hence, we MUST subtract v.begin() from the lower_bound()
if (!binary_search(v.begin(), v.end(), key))   // if element is not present return -1
{
    return -1;
}
else
{
    return (lower_bound(v.begin(), v.end(), key) - v.begin());     // "lower_bound()" returns `iterator` and hence, we MUST `subtract` `v.begin()` from the `lower_bound()`
}

to get the element from lower_bound then use *lowboundIteratorName​

set<int> st = {4566, 565465, 56, 557567, 342, 56756};

auto lb = st.lower_bound(342);
cout << "____" << (*lb) << endl
        << endl;

// set is [56 342 4566 56756 557567 565465 ]
/*
Output:

'____342'
*/

upper_bound()​

  • unodered_set has no member lower_bound or upper_bound
caution

Time Complexity is :~ O(log n)​

Returns: Iterator pointing to the first element greater than key, or end().

set<int> st = {4566, 565465, 56, 557567, 342, 56756};

auto ub = st.upper_bound(342);
cout << "____" << (*ub) << endl
        << endl;

// set is [56 342 4566 56756 557567 565465 ]
/*
Output:

'____4566'
*/

Common Problems of set​

Last Element of a set​

  • *a.rbegin()
  • auto it = s.end(); then it--;
// va = [ 1 2 3 4 6 9 12 18 36  ]
// vb = [ 1 2 3 6 9 18 27 54  ]

set<ll> tmp;    // declaring empty set

set_intersection(av.begin(), av.end(), bv.begin(), bv.end(), inserter(tmp, tmp.begin()));   // inserting all common values of 'set' "av" & "bv" in 'set' "tmp"
// tmp becomes  [ 1 2 3 6 9 18  ]   ;   'tmp' returns the intersection of "av" & "bv"

cout << *tmp.rbegin() << endl;  // 👉 returns the "last" element of the 'set', "*" gives the value at that particular iterator '*tmp.rbegin()'