C++ Sets and Multisets

The C++ Set is an associative container that contains a sorted set of unique objects.
Set Operators
  • begin - returns a reference iterator to the beginning of the set
  • clear - deletes all elements from the set
  • count - return the number of elements matching a given key
  • empty - returns 1 ( true ) if there is no element in the set else return 0 ( false ).
  • end - returns a reference iterator just past the last element of a set
  • equal_range - returns a reference iterators to the first and just past of the elements matching a specific key.
  • erase - deletes elements from a set
  • find - returns a reference iterator to specific elements which is given by the user.
  • insert - insert an item into a set
  • key_comp - returns the function that compares keys
  • lower_bound - returns a reference iterator to the first element greater than or equal to a certain value
  • max_size - outputs the maximum number of elements that the set can hold
  • rbegin - returns a reverse_iterator to the end of the set
  • rend - returns a reverse_iterator to the beginning of the set
  • size - outputs the number of items in the set
  • swap - swap the contents of this set with another set.
  • upper_bound - returns a reference iterator to the first element greater than a certain value
  • value_comp - returns the function that compares values
C++ Multisets are like sets, in that they are associative containers containing a sorted set of objects, but differ in that they allow duplicate objects. Meaning say you want to insert elements 1,2,3,1,2,3,4 in a set then it will hold { 1, 2, 3, 4 } ie. no repetition is allowed. In multiset you can have { 1, 1, 2, 2, 3, 3, 4 } ie. duplication is allowed.

Multiset Operators
  • begin - returns a reference iterator to the beginning of the set
  • clear - deletes all elements from the set
  • count - returns the number of elements matching the given value.
  • empty - returns 1 ( true ) if there is no element in the set else return 0 ( false ). 
  • end - returns a reference iterator just past the last element of a set
  • equal_range - returns a reference iterators to the first and just past of the elements matching a specific key
  • erase - deletes elements from a set
  • find - returns a reference iterator to given element if it finds in a set else return a reference to the just past the last element of the set.
  • insert - insert items into a set
  • key_comp - returns the function that compares keys
  • lower_bound - returns a reference iterator to the first element greater than or equal to a certain value
  • max_size - outputs the maximum number of elements that the set can hold
  • rbegin - returns a reverse_iterator to the end of the set
  • rend - returns a reverse_iterator to the beginning of the set
  • size - outputss the number of items in the set
  • swap - swap the contents of this multiset with another multiset.
  • upper_bound - returns a reference iterator to the first element greater than a certain value
  • value_comp - returns the function that compares values

Below is the implementation of Set Operators.


Description of each function and other set operators:

begin()

  • The begin() returns a reference iterator to the first element of the set. 
  • begin() runs in constant time O(1).

clear()

  • The clear() deletes all of the elements in the set. clear() runs in linear time O(n).

count()

  • This count() returns the number of occurrences of a given key value in the set. In a set, it will return 1 if the element is present else 0. In multiset, it will return the occurrences of a given key value in the multiset.
  • clear() runs in linear time O(1).

empty()

  • The empty() returns true (1) if the set has no elements, false(0) otherwise.

end()

  • The end() returns a reference iterator just past the end of the set.
  • Note that before you can access the last element of the set using an iterator that you get from a call to end(), you'll have to decrement the iterator first.

equal_range()

  • This function returns two reference iterators- one to the first element that contains the key, another to a point just after the last element that contains the key.

erase()

  • The erase() either erase the element at the position, erases the elements between start and end or erases all elements that have a value of key.

find()

  • The find() function returns a reference iterator to key, or an iterator to the end of the set if the key is not found.
  • find() runs in logarithmic time.

insert()

  • The function insert() either:
    • inserts value after the element at position (where the position is really just a suggestion as to where the value should go since sets and maps are ordered) and return a reference iterator to that element.
    • inserts a range of elements from start to end.
    • inserts value, but only if the value doesn't already exist. The return value is an iterator to
    • the element inserted, and a boolean describing whether an insertion took place.

key_comp()

  • The key_conp() returns the function that compares keys.
  • key_comp() runs in constant time O(1).

lower_bound()

  • The lower_bound() returns an iterator to the first element which has a value greater than or equal to key.
  • lower_bound() runs in logarithmic time O(logn).

max_size()

  • The max_size() outputs the maximum number of elements that the set can hold.
  • The max_size() should not be confused with the size() or (C++ Strings) capacity()

rbegin()

  • The rbegin() function returns a reverse_iterator to the end of the current set.
  • rbegin() runs in constant time.

rend()

  • The rend() returns a reverse_iterator to the beginning of the current set.
  • rend() runs in constant time.

size()

  • The size() outputs the number of elements in the current set.

swap()

  • The swap() function exchanges the elements of the current set with another set. 
  • This function operates in constant time.

upper_bound()

  • Thi function upper_bound() returns a reference iterator to the first element in the set with a key greater than key.

value_comp()

  • The value_comp() returns the function that compares values.
  • value_comp() runs in constant time.

Comments