Sets

Sets are containers which store only unique values and permit easy look ups.

The values in the sets are stored in some specific order (like ascending or descending).

Elements can only be inserted or deleted, but cannot be modified.

We can access and traverse set elements using iterators just like vectors.

Internally implemented as binary search tree.

Operations( Member functions )

Function	What it does ?	Complexity
begin( )	Returns an iterator to the first element of the set.	O(1)
end( )	Returns an iterator pointing to a position which is next to the last element	O(1)
clear( )	Deletes all the elements in the set and the set will be empty.	O(N)
count( )	Returns 1 or 0 if the element is in the set or not respectively.	O(logN)
empty( )	Returns true if the set is empty and false if the set has at least one element	O(1)
erase( )	Deletes a particular element or a range of elements from the set.	O(N)
find( )	Searches for a particular element and returns the iterator pointing to the element if the element is found otherwise it will return the iterator returned by end().	O(logN)
size( )	Returns the size of the set or the number of elements in the set.	O(1)
insert( )	insert a new element.	O(logN)

Implementation

// declaratation

set<int> s1;                               // Empty Set
int a[]= {1, 2, 3, 4, 5, 5};
set<int> s2 (a, a + 6);                    // s2 = {1, 2, 3, 4, 5}
set<int> s4 (s3.begin(), s3.end());         // Set created using iterators

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

int main()
{
        set <int> s;
        set <int>::iterator it;         // iterator to traverse
        int A[] = {3, 5, 2, 1, 5, 4};
        for(int i = 0;i < 6;++i)
                s.insert(A[i]);
        s.erase(A[3]);                  // erases 1 form the set
        printf("size of set %d\n",(int)s.size());
        for(it = s.begin();it != s.end();++it)
                cout << *it << ' ';
        cout << endl;
        return 0;

}

Output:

size of set 4
2 3 4 5

Problems

• codechef
  

Unordered-Sets

Unordered sets are containers that store unique elements in no particular order, and which allow for fast retrieval of individual elements based on their value.

Pros : Faster than sets (promises amortized O(1) for search).

Cons : Look up not guaranteed to be O(1) Therotical worst case is O(n)

Note : Implementation && Member functions are similar as Sets .

Problems

• codechef
  

Multiset

Multisets are a type of associative containers similar to set, with an exception that multiple elements can have same values.

Internally, the elements in a multiset are always sorted following a specific strict weak ordering criterion indicated by its internal comparison object (of type Compare).

        multiset <int , greater<int> > m ;
        m.insert(40);
        m.insert(60);
        m.insert(20);
        m.insert(60); // 60 will be added again to the multiset unlike set

Note : Implementation && Member functions are same as Sets .

Extending This :

Function	What it does ?	Complexity
rbegin()	Returns a reverse iterator pointing to the last element in the container	O(1)
rend()	Returns a reverse iterator pointing to the theoretical element right before the first element in the container	O(1)
equal_range()	The function returns a pair, whose member pair::first is the lower bound of the range (the same as lower_bound), and pair::second is the upper bound	O(logN)

Problems

• codechef