Sets and Maps in C++

There are two data structures in C++ that are build using balanced binary search trees. They are sets and maps. The language C++ provides standard functions that make it very convenient to work with sets and maps. The programmers will never experience the feeling that they are working with trees.

However, the underlying structures are the trees. The trees that are used are red and black trees. They are variation of balanced binary search trees. They are similar to AVL trees that we covered in these notes.

1. Sets in C++

We will now introduce the library set and show how it is used in C++.

The data structure set has some similarities with sets in mathematics. Most notably, elements cannot repeat. Nothing happens if we try to add an element to the set that already contains it. This is a simple consequence of the fact that sets are implemented using trees.

1.1. Declaration. Insert. Size

We will first learn how to declare sets and how to insert elements in the set. We will also learn how to obtain the size of the set. The commands to insert elements and to print the size are sufficient to write the simplest programs.

First, we must include it at the top of our source file. This is done with the command

#include <set>

If we want the variable myFirstSet to denote one set of integers of type long, then we give the following declaration:

std::set<long> myFirstSet;

The elements are inserted with the commands

myFirstSet.insert(71); myFirstSet.insert(81); or myFirstSet.insert(greenNumber);

where greenNumber is a variable of type long.

If we want to read the size of the set and store that size in the variable sz, then sz must be of some integer type (like int or long). The size will be transfered to the variable sz if we give the command

sz=myFirstSet.size();

The following code declares a set, and insets the numbers 71, 81, and 71 into the set. Finally, the program prints the size of the set. The size will be 2 because the second insertion of 71 does not have any effect.

#include<iostream>
#include<set>
int main(){
   std::set<long> myFirstSet;
   myFirstSet.insert(71); myFirstSet.insert(81); myFirstSet.insert(71);
   long sz;
   sz=myFirstSet.size();
   std::cout<<sz<<"\n";
   return 0;
}

Problem 1.

The user input consists of positive integers. A negative number or 0 is the sign that the input is over. Create the program that prints the total number of different integers that the user has entered. Your code should replace the text // ??? // below.

#include<iostream>
#include<set>
int main(){
   std::set<long> allNumbers;
   long x;
   std::cin>>x;
   while(x>0){
      allNumbers.insert(x);
      std::cin>>x;
   }
   // ??? //
   return 0;
}

Remark. We created a set of integers of type long. We could also create a set of real numbers of type double, or a set of words of type std::string. If you create your own class called Frog, then there is one conditions that Frog has to satisfy before you can make set of Frogs. That condition is: The class Frog must have comparison operator. In other words, the class from must have the methodoperator< or the method operator>. The document Trees in C++ can teach you how create these operators.

1.2. Erase

The following command erases the element 71 from the set:

myFirstSet.erase(71);

If the element is not in the set, then nothing is erased.

Problem 2.

First, the user insert red numbers. The red numbers are positive integers. When the user inserts 0 or a negative number, the user signals that the input of the red numbers is over. After the red numbers, the user inserts the green numbers. The green numbers are also positive integers. A negative number or 0 is the signal that the input of the green numbers is over. Create a C++ program that counts the total number of red numbers that are not green.

1.3. Search

The method find is used to search for an item in the set.

The method find returns a very sophisticated object called iterator. We will learn more about iterators later. For now, we will learn the basics of iterators. We will learn just enough to solve the easiest problems that involve searching in sets.

1.3.1. The iterator end()

Before we learn what iterators actually are, we will meet one very important iterator. That iterator is myFirstSet.end().

The result of search myFirstSet.find(71) is also an iterator. If the search fails and the number 71 is not in the set, then the iterator myFirstSet.find(71) is equal to the iterator myFirstSet.end().

For the time being, we will give the name to myFirstSet.end(). We will call it failure iterator. By comparing the results of the methods find to the failure iterator, we can determine whether an item belongs to the set.

The following program will put few numbers in the set, and then perform one search.

#include<iostream>
#include<set>
int main(){
   std::set<long> myFirstSet;
   myFirstSet.insert(1); myFirstSet.insert(10); myFirstSet.insert(50);
   long x=10;
   if(myFirstSet.find(x) == myFirstSet.end()){
      std::cout<<"Not found! "<<x<<" is not in the set.\n";
   }
   else{
      std::cout<<"Found! "<<x<<" is in the set.\n";
   }
   return 0;
}

The program would print that 10 is in the set. If you replace 10 by 20, then the program would print that 20 is not in the set.

Problem 3.

The input consists of an array of words that may contain repetitions. The word endOfInput denotes the end of input array and is not to be considered a member of the array. The array is followed by a single word v. Write a program whose output is Yes or No depending on whether \(v\) is a member of the input array.

Your code should replace the text // ??? // below.

#include<iostream>
#include<set>
int main(){
   std::set<std::string> allWords;
   std::string wordFromUser;
   std::cin>>wordFromUser;
   while(wordFromUser!="endOfInput"){
      allWords.insert(wordFromUser);
      std::cin>>wordFromUser;
   }
   std::string v;
   std::cin>>v;
   // ??? //
   return 0;
}

Problem 4.

The user input consists of positive integers. A negative number or \(0\) is a sign that the input is over. Create the program that reads the numbers from the user input and counts the total number of elements from the input that appear odd number of times.

1.4. Iterators. Listing of all elements

Iterators are objects that are similar to pointers.

In subsection 1.3.0 we learned the very basics of iterators. We learned that myFirstSet.end() is one iterator. We learned that search operations such as myFirstSet.find(71) result in other iterators. When search operations return the iterator that is equal to myFirstSet.end(), then we know that the search has failed.

Iterators are special objects. When properly declared, they can be given names as i, j, it. Such object i can then receive the result of the search in the following way:

i=myFirstSet.find(71);

1.4.1. Declaration of iterator

The iterator can be declared using one of the following two lines:

std::set<long>::iterator i;
std::set<long>::const_iterator j;

The iterator i is non-constant iterator and can be used to change the data structure. The iterator j is a constant iterator and it can't change the data structure. The constant iterators are preferred. In addition, if we are inside the function to which set is passed by argument, then we must use constant iterators that are declared using the second command.

1.4.2. Operations on iterators

The three operations on iterators are: *, ++, and --. These three operators that can be applied to iterators are called dereference, increment, and decrement operators.

1.4.2.1. Dereference of iterators

If i is an iterator that corresponds to the element x of the set, the we can use *i to retrieve the value x.

1.4.2.2. Increment of iterators

If i is an iterator that corresponds to the element x, then ++i is an iterator that correspond to the successor of x. The successor of x is the next element in the set, i.e. the smallest element in the set that is bigger than x.

1.4.2.3. Derement of iterators

If i is an iterator that corresponds to the element x, then --i is an iterator that correspond to the predecessor of x. The predecessor of x is the previous element in the set, i.e. the biggest element in the set that is smaller than x.

1.4.2.4. Example of operations on iterators

The following program inserts few integers in the set, and then prints the predecessor and the successor of the number 71.

#include<iostream>
#include<set>
int main(){
   std::set<long> a;
   a.insert(55); a.insert(90); a.insert(68); a.insert(80); a.insert(71); 
   a.insert(77);
   std::set<long>::const_iterator i;
   i=a.find(71);
   --i;
   std::cout<<"The predecessor is "<< *i <<"\n";
   ++i;
   std::cout<<"The iterator i is back where it started. \n";
   std::cout<<"Dereferencing gives us: "<< *i<<"\n";
   ++i;
   std::cout<<"The successor is "<<*i<<"\n";
   return 0;
}

1.4.3. The iterator begin()

The method begin() applied to a set returns the iterator to its first, smallest, element.

The following code prints all the elements of the set from the smallest to the largest.

#include<iostream>
#include<set>
int main(){
   std::set<long> a;
   a.insert(55); a.insert(90); a.insert(68); a.insert(80); a.insert(71); 
   a.insert(77);
   std::set<long>::const_iterator i;
   i=a.begin();
   while(i!=a.end()){
      std::cout<<*i<<" ";
      ++i;
   }
   std::cout<<"\n";
   return 0;
}

Problem 5.

The user input consists of positive integers. A negative number or \(0\) is a sign that the input is over. Create the program that reads the numbers from the user input and prints all elements from the input that appear odd number of times.

2. Maps in C++

The elements of the data structure map have two components. They are called key and value. They do not have to be of the same type. Keys must be unique and their type must have the comparison operator. Comparison operator is operator< or operator>.

2.1. Declaration. Insert. Size

Maps can be used if the top of the C++ source file contains the command

#include <map>

Let us create the map bakery whose keys are strings that represent the names of items that the bakery sells. The values are the prices of the items in the bakery. We use the following declaration:

std::map<std::string,double> bakery;

The elements are inserted with the commands

bakery["sesameBagel"]=3.71;, bakery["chocolateMuffin"]=4.81;, or bakery[itemX]=priceY;,

where itemX is a variable of type std::string while priceY is a variable of type double.

If we want to read the size of the map and store that size in the variable sz, then sz must be of some integer type (such as int or long). The size will be transfered to the variable sz if we give the command

sz=bakery.size();

The keys must be unique. If two insert commands use the same key, then the value provided in the second command will overwrite the value from the first.

2.2. Search. Iterators

The method find is used to search the map. The method must have one argument. The argument has to be of the same type as the key. If the key is not found in the map, then the method returns the iterator bakery.end(). If the key is found, then the method returns the iterator to the corresponding item.

When the iterator is dereferenced, it has two components. They are called first and second. The first component is the key. The second component is the value. The increments and decrements to the iterators are the same as in the case of sets.

2.3. Erase

The method erase for maps is very similar to the erase for sets. Its simplest form requires us to provide the name of the key. If the key was found, the corresponding item is removed from the map.

2.4. Examples

The following program illustrates the insertion of elements, removal of elements, search operation, and listing of all elements using the iterators.

#include<iostream>
#include<map>
int main(){
   std::map<std::string,double> bakery;
   bakery["sesameBagel"]=3.51; bakery["blueberryBagel"]=3.71; 
   bakery["walnutBagel"]=3.87; bakery["chocolateMuffin"]=4.81; 
   bakery["plainDonut"]=2.55; bakery["pinkDonut"]=2.55;
   bakery["sesameBagel"]=3.71; //The old value 3.51 is 
                         // lost and replaced with 3.71
   long sz;
   sz=bakery.size();
   std::cout << "The size of the map is "<<sz<<"\n\n";
   std::string desert="chocolateDonut";
   std::map<std::string,double>::const_iterator i;
   i=bakery.find(desert);
   if( i == bakery.end() ){
      std::cout << desert << " is not in the map.\n\n";
   }
   else{
      std::cout << desert << " is in the map.\n\n";
   }
   std::string breakfast="plainDonut";
   i=bakery.find(breakfast);
   if( i != bakery.end() ){
      std::cout << breakfast << " is found in the map.\n";
      std::cout << "The key is " << (*i).first ;
      std::cout <<". This is the same as "<< breakfast <<"\n";
      std::cout << "The corresponding value is " << (*i).second << "\n\n";
   }
   bakery.erase(breakfast);
   std::cout << breakfast <<" is erased from the map.\n\n";
   std::cout <<"This is the list of all items and their prices\n";
   i=bakery.begin();
   while( i != bakery.end() ){
      std::cout << (*i).first << " has price " << (*i).second << "\n";
      ++i;
   }
   return 0;
}

Problem 6.

Each item that bakery sells has name of type std::string and price of type double. The user inputs the names and prices. The input ends when the user provides the word endOfInput instead of a name for an item. Create a program that checks whether chocolateDonut is in the map. If it is, then the program should print its price. If chocolateDonut is not in the map, then the program should print Not found.

Your code should replace the text // ??? // below.

#include<iostream>
#include<map>
int main(){
   std::map<std::string, double> bakery;
   std::string itemFromUser;
   double priceFromUser;
   std::cin>>itemFromUser;
   while(itemFromUser!="endOfInput"){
      std::cin>>priceFromUser;
      bakery[itemFromUser]=priceFromUser;
      std::cin>>itemFromUser;
   }
   // ??? //
   return 0;
}

Problem 7.

Each item that bakery sells has name of type std::string and price of type double. The user inputs the names and prices. The input ends when the user provides the word endOfInput instead of a name for an item. After the items are inserted in the bakery, the user inserts a shopping list. The shopping list is an array of items that ends with the word endOfShoppingList. Create a program that prints the total price that someone has to pay for all the items on the shopping list. If any of the items on the shopping list is not in the bakery, then the program should print the number -1 instead of the total price.

Your code should replace the text // ??? // below.

#include<iostream>
#include<map>
int main(){
   std::map<std::string, double> bakery;
   std::string itemFromUser;
   double priceFromUser;
   std::cin>>itemFromUser;
   while(itemFromUser!="endOfInput"){
      std::cin>>priceFromUser;
      bakery[itemFromUser]=priceFromUser;
      std::cin>>itemFromUser;
   }
   // ??? //
   return 0;
}

3. Exercises

Problem 8.

Use sets to create a program that sorts the sequence of \(n\) integers provided through the standard input. You should not assume that all elements of the input sequence are different.

Problem 9. The user provides a positive integer \(k\) and a sequence of positive real numbers that ends with a negative real number which is not the part of the sequence. Assume that the given real numbers are \(x_0\), \(x_1\), \(\cdots\), \(x_{n-1}\). Print on the standard output the sequence \(y_0\), \(y_1\), \(y_2\), \(\dots\), \(y_{n-k-1}\), where \(y_i\) is defined as \[y_i=\max\left\{x_i,x_{i+1}, \dots, x_{i+k-1}\right\}.\] The program should have complexity \(O(n\log k)\).

Problem 10.

Using the data structure of a tree that we built in class, create a class SetOfFractions with the following declaration.

class SetOfFractions{
private:
    TNode* root;
public:
    SetOfFractions();
    SetOfFractions(const SetOfFractions & );
    SetOfFractions(SetOfFractions &&);
    void operator=(const SetOfFractions &);
    void operator=(SetOfFractions &&);
    long isElement(const Frac &) const;
    long insertInS(const Frac &);
    void printAllFractions() const;
    ~SetOfFractions();
};
  • (a) The default constructor SetOfFractions() should initialize an empty tree. The copy constructor SetOfFractions(const SetOfFractions & copyFrom) should create the set of fractions with the same elements as the set copyFrom. Make sure that the elements are not shared - if subsequent changes are made in the object copyFrom the changes should not affect the object created with copy constructor.
  • (b) Copy assignment operator void operator=(const SetOfFractions & copySet) copies the content of the set over the existing elements. Make sure you properly deallocate the memory before copying to prevent memory leak.
  • (c) The methods SetOfFractions(SetOfFractions && moveFrom) and void operator=(SetOfFractions && moveFrom) are move constructor and move assignment operator.
  • (d) The method long isElement(const Frac & el) should return 1 if el is an element of the set and \(0\) otherwise.
  • (e) The method long insertInS(const Frac & fr) should insert the element fr in the set, if the element is not in the set already. If it is in the set, then no insertion should be performed.
  • (f) The method void printAllFractions() should print all the fractions in the set.
  • (g) The method ~SetOfFractions() should be the destructor that deallocates the memory occupied by the tree structure.

After creating the described class, use the following function main() to test the implementation of the class.

int main(){
  long a,b,c;
  Frac tempFr;
  SetOfFractions setF;
  a=1;
  while(a!=0){
      std::cout<<"Choose one of: 0 (exit), 1 (add), ";
      std::cout<<"2 (check for element), "; 
      std::cout<<"or 3 (print all)"<<std::endl;
      std::cin>>a;
      if(a==1){
          std::cout<<"Insertion.";
          std::cout<<" What are numerator and denominator? ";
          std::cin>>b>>c;
          tempFr.setNum(b);
          tempFr.setDen(c);
          setF.insertInS(tempFr);
      }
      if(a==2){
          std::cout<<"Checking for element.";
          std::cout<<" What are numerator and denominator? ";
          std::cin>>b>>c;
          tempFr.setNum(b);
          tempFr.setDen(c);
          std::cout<<setF.isElement(tempFr)<<std::endl;
      }
      if(a==3){
          std::cout<<"Printing all fractions."<<std::endl;
          setF.printAllFractions();
          std::cout<<std::endl;
      }
  }

  return 0;
}

Problem 11.

A pair of prime numbers \((p,q)\) is called an \(\alpha\)-couple if \(p^2+q^2+\alpha\) is a prime number.

The user first provides the positive integer \(\alpha\). Then the user provides pairs \(p\), \(q\) of non-negative integers. Once the user enters 0 or a negative number instead of \(p\) or \(q\), the user informs us that he/she does not want to provide any more input and that the program should stop. For each of the pairs, determine whether it is an \(\alpha\)-couple.

Remark. If one of the numbers \(p\) or \(q\) is not prime, then \((p,q)\) is not an \(\alpha\)-couple.