Exercises on vectors in C++

1. The mathematics

An array or vector of int values is a list of values. Each item in the list has an index from $0$ to $s - 1$ where $s$ is the size of the vector. Such arrays can be used to represent sets of integers in mathematics provided that we can arrange that there is no repeated entry in the list and that we choose to ignore the order of the items in the list.

Amongst the relations and operations you'd like to model are the following,

element-of: $x \in y$
union: $x \cup y = \{u: u \in x \lor u \in y\}$
intersection: $x \cap y = \{u: u \in x \land u \in y\}$
setdifference: $x ∖ y = \{u: u \in x \land u \notin y\}$

The symbol $\land$ means "and" and $\lor$ means "or".

Note that we can also have vectors of vectors, which represent "sets of sets". For such objects we want to model,

big union: $⋃ x = \{u: \exists y \in x u \in y\}$
big intersection: $⋂ x = \{u: \forall y \in x u \in y\}$

2. C++ code

A lot of this section will contain short functions that model certain set operations using C++'s vector<int>. You are free to copy these into your own code to use them. In some cases there are exercises for you to do.

For reasons explained elsewhere, vector arguments to functions are always done using call-by-reference, hence the ampersand (&) characters.

Note that it is good style to always include a detailed comment before a function to say what the function does and what conditions if any are expected of its inputs. Also please do not change the names (or signature) of any of the functions here.

Example.

We start with printing vectors. Since we want to think of vectors here as sets, we want to print them with curly brackets. The following works reasonably well.

/* prints the vector l as a list inside { .. } */
void printvector( vector<int>& l) {
  int s = l.size();
  cout << "{ ";
  for (int i=0; i<s-1; i++) {
    cout << l[i] << ", ";
  }
  if (s>0) { cout << l[s-1]; }
  cout << " }" << endl;
}

Example.

We may want to print vectors of vectors too. Fortunately we can simply call the previous function in a loop.

/* prints the vector< vector<int> > l as a list inside { .. } */
void printvectorvector(vector< vector<int> >& l) {
  int s = l.size();
  cout << "{ " << endl;
  for (int i=0; i<s-1; i++) {
    printvector( l[i] );
    cout << ", ";
  }
  if (s>0) { printvector( l[s-1] ); }
  cout << " }" << endl;
}

Example.

To give us something to print in the first place we might want a function to populate a vector with entries. The following does this for the triangle numbers 0,1,3,6,10,...

/* clears the vector "answer" and fills it with all triangle 
 * numbers starting at 0 and up to and possibly including the 
 * maximum "maxval". */
void triangle( int maxval, vector<int>& answer) {
  // resize answer to be empty
  answer.resize(0);
  int t = 0; // the first triangle number
  int c = 1; // a "counter"
  while (t <= maxval) {
    // while t is small enough, add it to the vector
    answer.push_back(t);
    t = t + c;
    c = c + 1;
  }
}

Run this with the following main. (You will also need to #include both <iostream> and <vector>, and do using namespace std;, and also include the functions you use.)

int main() {
  vector<int> v;   // declare an empty vector
  triangle(100,v); // fill with triangle numbers
  printvector(v);  // print it
  return 0;
}

Exercise.

Make a function that clears an input vector, and fills it with an arithmetic progression starting at some number with a given common difference and maximum value. Your function should look like this.

/* clears the vector "answer" and fills it with a AP 
 * starting at "nstart" and with common difference "cdiff",
 * up to and possibly including the maximum "maxval". */
void ap( int nstart, int cdiff, int maxval, vector<int>& answer) {
   // your code goes here
}

Example.

To determine if an int is a member of a vector or not, we need a loop to test all possible items. The following is worth studying carefully.

/* returns true if x is an element of the list l, false otherwise */
bool elementof(int x, vector<int>& l) {
  int s = l.size();
  for (int i=0; i<s; i++) {
    if (x == l[i]) return true; // found!
  }
  return false; // tried everything and not found
}

Example.

There will be occasions when we want to add an int to a vector, but to do that we need to check it is not already there (to prevent repetitions).

/* if x is not already an item in answer adds it using push_back, 
 * otherwise does not change answer */
void addtolist(int x, vector<int>& answer) {
  if (elementof(x,answer)) return; // do nothing
  answer.push_back(x); // not found, so add it
}

Example.

The function addtolist gets used as follows,

/* computes the union of x,y, i.e. a list (without repetitions)
 * of all elements in either x or y.  (It doesn't matter if x or y
 * have repetitions or not!) */
void setunion(vector<int>& x,vector<int>& y, vector<int>& answer) {
  answer.resize(0);
  int s = x.size();
  for (int i=0 ; i<s; i++) {
    addtolist(x[i], answer);
  }
  s = y.size();
  for (int i=0 ; i<s; i++) {
    addtolist(y[i], answer);
  }
}

/* computes the intersection of x,y, i.e. a list (without repetitions)
 * of all elements in both x and y, putting the answer in "answer" */
void setintersection(vector<int>& x, vector<int>& y, vector<int>& answer) {
  answer.resize(0);
  int s = x.size();
  for (int i=0 ; i<s; i++) {
    if (elementof(x[i], y)) {
      addtolist(x[i], answer);
    }
  }
}

Note that "union" is a keyword in C++ so cannot be used as a variable or function name.

Exercise.

Write a similar function for set difference. Use the following.

/* computes the set difference of x minus y, putting the answer in "answer" */
void setdifference(vector<int>& x,vector<int>& y, vector<int>& answer) {
  // your code here
}

Example.

To compute the big intersection of a vector of vectors, something like a loop inside a loop is required. The following is worth study.

/* computes the bigintersection of x, i.e. a list (without repetitions)
 * of all elements in all the x[i]. If x has size 0, i.e. is an empty
 * set of vectors this also returns the empty list in answer */
void bigintersection(vector< vector<int> >& x, vector<int>& answer) {
  answer.resize(0);
  int s = x.size();
  if (s==0) return; // nothing in x: return empty list
  vector<int> first = x[0];
  int t = first.size();  
  for (int i=0; i<t; i++) {
    int u = first[i];
    // now decide if u goes in the intersection by testing all the other x[j]
    bool isin = true;
    for (int j=1 ; j<s; j++) {
      if (!elementof(u, x[j])) { isin = false; break; }
    }
    if (isin) answer.push_back(u);
  }
}

When you read this you must keep a clear head for all the types: Since x has type (reference to) vector< vector<int> > each x[i] has type vector<int> i.e. is a vector and each x[i][j] is an int.

Example.

To test bigintersection, a main like the following could be used.

int main () {
  vector<vector<int>> vv;
  vector<int> e;         // empty vector
  vv.push_back(e);       // add copy of empty vector to vv
  triangle(50,vv[0]);    // fill vv[0] with triangle numbers
  vv.push_back(e);       // add copy of empty vector to vv
  ap(0,3,50,vv[1]);      // fill vv[1] with an AP
  printvectorvector(vv);
  bigintersection(vv,e); // make e = bigintersection of vv
  printvector(e);
  return 0;
}

The following exercise is similar to bigintersection, but much easier. By all means use similar ideas but do not copy them slavishly because you will go wrong. Instead concentrate on what "addtolist" does and how you can use it effectively.

Exercise.

Write a similar function for big union. Use the following.

/* computes the bigunion of x, i.e. a list (without repetitions)
 * of all elements in some x[i]. */
void bigunion(vector< vector<int> >& x, vector<int>& answer) {
  // your code here
}

3. Putting it all together

You should write and test the three functions you have written one after the other, as indicated above. Test them individually first using very simple "main" functions of your own choosing.

Only when you have done this should you put it all together in the following program.

#include <iostream>
#include <vector>
using namespace std;

// any necessary functions go here

int main() {
  int maxn;
  cout << "Enter maximum int value: " ;
  cin >> maxn;

  // empty vector of 0 elements
  vector<int> emptyv(0);
  
  // empty vector of vector of 0 elements
  vector<vector<int>> vv(0);

  int index = -1;
  for (int i=2; i<maxn; i++) {
    // in the next line || means "or"
    if (index<0 || vv[index].size()>0 ) {
      index++;
      // add empty vector to vv, called vv[j]
      vv.push_back(emptyv);
    }
    // add an ap to this vector vv[index]
    ap(2*i,i,maxn,vv[index]);    
  }

  printvectorvector( vv );

  vector<int> setu;
  vector<int> univ;
  vector<int> setd;

  ap(2,1,maxn,univ);
  bigunion(vv, setu);
  setdifference(univ,setu,setd);
  printvector( univ );
  printvector( setu );
  printvector( setd );

  return 0;
}

You should try it and see what it does. You should try to understand how it works too!