Sorted Data Structures, Templates
Participation
Loading...

Export your exercise answers to use with another computer or browser.

Sorted Data Structures, Templates

Continuing from last time, we'll consider another potential implementation of a set, this time based on an underlying array that is kept in sorted order. The addition of a sorting invariant means some of our functions are more complicated (i.e. you can't just put elements wherever), but searching for elements in the array can be done much more efficiently.

We'll also introduce templates, which are a C++ mechanism for compile-time parametric polymorphism and can be used to implement generic containers with flexible element types (e.g. set<int> or set<string>).

But first, we'll cover a few miscellaneous topics that didn't fit in the last lecture:

  • The difference between the prefix and postfix versions of the ++ and -- operators.

  • Overloading operators with member functions (as opposed to regular, non-member functions).

Updated Winter 2025
1: Prefix ++ vs. Postfix ++

Ever wanted to know the difference between ++i and i++? Here's the scoop:

2: Member vs. Non-Member Operator Overloads
2.1 Not Started

You know the only thing cooler than a set ADT? A set ADT with custom operators!

We'll look at two different examples:

  • operator<<, which is implemented as a non-member function operator overload.
  • operator[], which is implemented as a member function operator overload.


2.1 Exercise: Overloading += on IntSet

Let's add a += operator to our IntSet class, which allows a nice syntax for adding elements to the set. Here's an example of how we might use it:

class IntSet {
  // operator+= overload
};
int main() {
  IntSet set;
  set += 3;
  set += 5;
  cout << set; // {3, 5}
}

The += operator can be implemented either as a member function overload or a non-member function overload. Consider each of the potential implementations of += below. For each, indicate how the operator+= overload function is being defined (write "member" or "non-member") and whether or not it is implemented correctly (write "correct" or "incorrect").

// Version 1
void operator+=(IntSet &s, int v) {
  s.insert(v);
}

// Version 2
void IntSet::operator+=(int v) {
  this->insert(v);
}

// Version 3
void IntSet::operator+=(IntSet &s, int v) {
  s.insert(v);
}

// Version 4
void operator+=(IntSet &s, int v) {
  this->insert(v);
}

// Version 5
void IntSet::operator+=(int v) {
  insert(v);
}

You're welcome to check your solution with this walkthrough video:

3: A Sorted IntSet
3.1 Not Started

Let's make a key change to the fundamental strategy and data representation for our set - keeping all the elements in sorted order - and see if we can improve the performance of the data structure…


3.1 Exercise: SortedIntSet::insert()

Implement the insert() member function for the SortedIntSet class. If the given value is not already in the set, it should be inserted into the elts array at the appropriate position to maintain the sorting invariant. Elements greater than the inserted value will need to be shifted to the right to create the space to insert the element. elts_size should also increase by 1. However, if the value is already in the array, insert() does nothing.

The main() function provided includes testing code to verify your implementation.

You're welcome to check your solution with this walkthrough video:

Note: This walkthrough uses several different files for the code, which is different than the above, where we had everthing embedded into one file. (The solution for insert() is the same, though!)

4: Templates
4.1 Not Started

Finally, let's use templates to implement a generic set container with a flexible element type.


4.1 Exercise: fillFromArray() Function Template

Fill in the blanks to make the function work as intended (the main function shows examples).

template <>
void fillFromArray( set,  arr, int n) {
  for (int i = 0; i < n; ++i) {
    
  }
}
int main() {
  UnsortedSet<int> set1;
  int arr1[4] = { 1, 2, 3, 2 };
  fillFromArray(set1, arr1, 4); // set1 now contains 1, 2, 3
  UnsortedSet<char> set2;
  char arr2[3] = { 'a', 'b', 'a' };
  fillFromArray(set2, arr2, 3); // set2 now contains 'a', 'b'
}

You're welcome to check your solution with this walkthrough video:
You've reached the end of this lecture! Your work on any exercises will be saved if you re-open this page in the same web browser.

Participation Credit
Make sure to sign in to the page, complete each of the exercises, and double check the participation indicator at the top left of this page to ensure you've earned credit.