The set and multiset are containers that facilitate a quick lookup of keys in a container that stores them; that is, the keys are the values stored in the one-dimensional container.
The difference between the set and the multiset is that latter allows for duplicates whereas the former can store only unique values.
To faciliate quick searching, STL implementations of the set and multiset internally look like a binary tree. This means that elements inserted in a set or a multiset are sorted on insertion for quicker lookuos. It also means that, unlike in a vector where elements at a position can be replaced by a new element of a different valus. This is true coz the set would ideally like to have it placed in a possible different location in accordance with its value relative to those in the internal tree.
Basic STL set and multiset Operations
Instantiating a std::set Object
View Code
#include <set>
int main ()
{
using namespace std;
set <int> setIntegers;
multiset <int> msetIntegers;
return 0;
}
Inserting Elements in an STL set or multiset
View Code
#include <set>
#include <iostream>
using namespace std;
template <typename Container>
void PrintContents (const Container & stlContainer);
int main ()
{
set <int> setIntegers;
multiset <int> msetIntegers;
setIntegers.insert (60);
setIntegers.insert (-1);
setIntegers.insert (3000);
cout << "Writing the contents of the set to the screen" << endl;
PrintContents (setIntegers);
msetIntegers.insert (setIntegers.begin (), setIntegers.end ());
msetIntegers.insert (3000);
cout << "Writing the contents of the multiset to the screen" << endl;
PrintContents (msetIntegers);
cout << "Number of instances of '3000' in the multiset are: '";
cout << msetIntegers.count (3000) << "'" << endl;
return 0;
}
template <typename Container>
void PrintContents (const Container & stlContainer)
{
Container::const_iterator iElementLocator = stlContainer.begin ();
while (iElementLocator != stlContainer.end ())
{
cout << *iElementLocator << endl;
++ iElementLocator;
}
cout << endl;
}
Output:
Writing the contents of the set to the screen
-1
60
3000
Writing the contents of the multiset to the screen
-1
60
3000
3000
Number of instances of ‘3000’ in the multiset are: ‘2’
Finding Elements in an STL set or multiset
Associative containers like set and multiset, map, and multimap feature find() ---- a member function that allows you to find a value given a key, as demostrated as below. In case of a multiset this function will find the first value that matches the supplied key.
View Code
#include <set>
#include <iostream>
using namespace std;
typedef set <int> SETINT;
int main ()
{
SETINT setIntegers;
// Insert some random values
setIntegers.insert (43);
setIntegers.insert (78);
setIntegers.insert (-1);
setIntegers.insert (124);
SETINT::const_iterator iElement;
// Write contents of the set to the screen
for ( iElement = setIntegers.begin ()
; iElement != setIntegers.end ()
; ++ iElement )
cout << *iElement << endl;
// Try finding an element
SETINT::iterator iElementFound = setIntegers.find (-1);
// Check if found...
if (iElementFound != setIntegers.end ())
cout << "Element " << *iElementFound << " found!" << endl;
else
cout << "Element not found in set!" << endl;
// Try finding another element
SETINT::iterator iAnotherFind = setIntegers.find (12345);
// Check if found...
if (iAnotherFind != setIntegers.end ())
cout << "Element " << *iAnotherFind << " found!" << endl;
else
cout << "Element 12345 not found in set!" << endl;
return 0;
}
Output:
-1
43
78
124
Element -1 found!
Element 12345 not found in set!
Erasing Elements in an STL set or multiset
Associate containers like set and multiset, map, and multimap feature erase(), which is a member function that allows you to delete a value given a key:
setObject.erase (key);
Another form of the erase function allows the deletion of a particular element given aniterator that points to it:
setObject.erase (iElement);
You can erase a range of elements from a set or a multiset using iterators that supplythe bounds:
setObject.erase (iLowerBound, iUpperBound);
View Code
#include <set>
#include <iostream>
using namespace std;
typedef multiset <int> MSETINT;
int main ()
{
MSETINT msetIntegers;
// Insert some random values
msetIntegers.insert (43);
msetIntegers.insert (78);
msetIntegers.insert (78); // Duplicate
msetIntegers.insert (-1);
msetIntegers.insert (124);
MSETINT::const_iterator iElement;
cout << "multiset contains " << msetIntegers.size () << " elements.";
cout << " These are: " << endl;
// Write contents of the multiset to the screen
for ( iElement = msetIntegers.begin ()
; iElement != msetIntegers.end ()
; ++ iElement )
cout << *iElement << endl;
cout << "Please enter a number to be erased from the set" << endl;
int nNumberToErase = 0;
cin >> nNumberToErase;
cout << "Erasing " << msetIntegers.count (nNumberToErase);
cout << " instances of value " << nNumberToErase << endl;
// Try finding an element
msetIntegers.erase (nNumberToErase);
cout << "multiset contains " << msetIntegers.size () << " elements.";
cout << " These are: " << endl;
for ( iElement = msetIntegers.begin ()
; iElement != msetIntegers.end ()
; ++ iElement )
cout << *iElement << endl;
return 0;
}
Output:
multiset contains 5 elements. These are:
-1
43
78
78
124
Please enter a number to be erased from the set
78
Erasing 2 instances of value 78
multiset contains 3 elements. These are:
-1
43
124
Now that you have an overview of the basic set and multiset functions, it’s time toreview a sample that features a practical application made using this container class. The sample below is a simple implementation of a menu-based telephone directorythat allows the user to insert names and telephone numbers, find them, erase them, anddisplay them all.
View Code
#include <set>
#include <iostream>
#include <string>
using namespace std;
enum MenuOptionSelection
{
InsertContactsetEntry = 0,
DisplayEntries = 1,
FindNumber = 2,
EraseEntry = 3,
QuitApplication = 4
};
struct ContactItem
{
string strContactsName;
string strPhoneNumber;
// Constructor
ContactItem (const string& strName, const string & strNumber)
{
strContactsName = strName;
strPhoneNumber = strNumber;
}
bool operator == (const ContactItem& itemToCompare) const
{
return (itemToCompare.strContactsName == this->strContactsName);
}
bool operator < (const ContactItem& itemToCompare) const
{
return (this->strContactsName < itemToCompare.strContactsName);
}
};
int ShowMenu ();
ContactItem GetContactInfo ();
void DisplayContactset (const set <ContactItem>& setContacts);
void FindContact (const set <ContactItem>& setContacts);
void EraseContact (set <ContactItem>& setContacts);
int main ()
{
set <ContactItem> setContacts;
int nUserSelection = InsertContactsetEntry;
while ((nUserSelection = ShowMenu ()) != (int) QuitApplication)
{
switch (nUserSelection)
{
case InsertContactsetEntry:
setContacts.insert (GetContactInfo ());
cout << "Contacts set updated!" << endl << endl;
break;
case DisplayEntries:
DisplayContactset (setContacts);
break;
case FindNumber:
FindContact (setContacts);
break;
case EraseEntry:
EraseContact (setContacts);
DisplayContactset (setContacts);
break;
default:
cout << "Invalid input '" << nUserSelection;
cout << ".' Please choose an option between 0 and 4" << endl;
break;
}
}
cout << "Quitting! Bye!" << endl;
return 0;
}
void DisplayContactset (const set <ContactItem>& setContacts)
{
cout << "*** Displaying contact information ***" << endl;
cout << "There are " << setContacts.size () << " entries:" << endl;
set <ContactItem>::const_iterator iContact;
for ( iContact = setContacts.begin ()
; iContact != setContacts.end ()
; ++ iContact )
cout << "Name: '" << iContact->strContactsName << "' Number: '"
<< iContact->strPhoneNumber << "'" << endl;
cout << endl;
}
ContactItem GetContactInfo ()
{
cout << "*** Feed contact information ***" << endl;
string strName;
cout << "Please enter the person's name" << endl;;
cout << "> ";
cin >> strName;
string strPhoneNumber;
cout << "Please enter "<< strName << "'s phone number" << endl;
cout << "> ";
cin >> strPhoneNumber;
return ContactItem (strName, strPhoneNumber);
}
int ShowMenu ()
{
cout << "*** What would you like to do next? ***" << endl << endl;
cout << "Enter 0 to feed a name and phone number" << endl;
cout << "Enter 1 to Display all entries" << endl;
cout << "Enter 2 to find an entry" << endl;
cout << "Enter 3 to erase an entry" << endl;
cout << "Enter 4 to quit this application" << endl << endl;
cout << "> ";
int nOptionSelected = 0;
// Accept user input
cin >> nOptionSelected ;
cout << endl;
return nOptionSelected;
}
void FindContact (const set <ContactItem>& setContacts)
{
cout << "*** Find a contact ***" << endl;
cout << "Whose number do you wish to find?" << endl;
cout << "> ";
string strName;
cin >> strName;
set <ContactItem>::const_iterator iContactFound
= setContacts.find (ContactItem (strName, ""));
if (iContactFound != setContacts.end ())
{
cout << strName << " is reachable at number: ";
cout << iContactFound->strPhoneNumber << endl;
}
else
cout << strName << " was not found in the contacts list" << endl;
cout << endl;
return;
}
void EraseContact (set <ContactItem>& setContacts)
{
cout << "*** Erase a contact ***" << endl;
cout << "Whose number do you wish to erase?" << endl;
cout << "> ";
string strName;
cin >> strName;
size_t nErased = setContacts.erase (ContactItem (strName, ""));
if (nErased > 0)
cout << strName << "'s contact information erased." << endl;
else
cout << strName << " was not found!" << endl;
cout << endl;
}
Pros and Cons of Using STL set and multiset
The STL set and multiset provide significant advantages in applications that need frequent lookups coz their contents are sorted and therefore quicker to locate. However, to present this advantage, the container needs to sort elements at insertion-time. Thus, there is an overhead in inserting elements coz elements are sorted ---- an overhead that might be a worthwhile compromise if you need to use features and functions like find() that make use of internal binary tree structure. This sorted binary tree structure results in another implicit advantage over sequential containers such as the vector. In a vector, the element pointed to by an iterator can be overwritten by a new value. In case of a set however, elements are sorted by the set class according to their respective values, and therefore overwritting an element using an iterator should never be done, even if that were programmatically possible.