C++ Sets
Ordered vs Unordered Sets
Sets are different from maps in a way that map stores key-value pairs whereas set stores only keys.
C++ STL provides std::set container which stores the elements in sorted order.
Another STL container std::unordered_set stores the elements in random order.
All the elements should be unique in both the containers.
An example usage is as below:
#include <iostream>
#include <set>
#include <unordered_set>
int main()
{
std::set<std::string> empNames;
// insert an entry
empNames.insert("Maria");
empNames.insert("Christoph");
empNames.insert("Sebastian");
std::cout << "Employee Names using Ordered set\n";
for (const auto& name : empNames)
std::cout << "Emp Name: " << name << std::endl;
std::cout << std::endl << std::endl;
std::unordered_set<std::string> empNamesUnOrder;
// insert an entry
empNamesUnOrder.insert("Maria");
empNamesUnOrder.insert("Sebastian");
empNamesUnOrder.insert("Christoph");
std::cout << "Employee Names using Unordered Set\n";
for (const auto& name : empNamesUnOrder)
std::cout << "Emp Name: " << name << std::endl;
return 0;
}
Output:
Employee Records using Ordered Map
Emp Code: CHR , Emp Name: Christoph
Emp Code: MAR , Emp Name: Maria
Emp Code: SEB , Emp Name: Sebastian
Employee Records using Unordered Map
Emp Code: MAR , Emp Name: Maria
Emp Code: CHR , Emp Name: Christoph
Emp Code: SEB , Emp Name: Sebastian
Internally, the maps and sets are implemented in the same manner. The sets are implemented using Self-balancing Binary Search Tree (like Red-Black Tree). The complexity of all three operations - search, insert and delete is log(n). Unordered sets are implemented using Hash Table. The elements of the unordered set are hashed into indices of the hash table so that the insertion is always randomized. The average time complexity is O(1) and O(n) in worst case for insert, delete and search operations.
Multisets
We read above about sets and that each element in the set should be unique i.e sets does not allow duplicate elements. Multisets are different from sets in a way that it allows duplicate values. Like sets, multisets are also ordered (std::multiset) and unordered (std::unordered_multiset). The internal implementation of ordered/unordered multiset is similar to ordered/unordered set in that they both use self-balancing BST/hash table, but in case of multiset, a separate count value is also associated with each element to denote the number of entries for each element.