MTH4300 Home

Sets in C++

Our implementation of the tree has a flaw: If the data is sorted before insertion, then the tree becomes a linked list. Inserting, deleting, and searching become long operations of complexity \(O(\log N)\), where \(N\) is the number of elements. In class we have seen the AVL algorithm that guarantees that the tree will be balanced.

In C++ the library set is implemented using a similar algorithm that maintains a tree structure and ensures that the tree satisfies some balancing conditions. The std library uses red and black trees to implement sets and maps.

Example 1

The input consists of an array of strings that may contain repetitions. The string 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 string \(v\). Write a program whose output is Yes or No depending on whether \(v\) is a member of the input array. Also, print the total number of different strings that occur in the array and the all of the strings in alphabetical order.

Example 2

Use sets to create a program that sorts the sequence of \(n\) integers provided through the standard input.

Example 3

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)\).

Exercises

Problem 1.

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), 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 2.

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.