const, structs, and C-Style ADTs
Participation
Loading...

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

const, structs, and C-Style ADTs

As we start to work with larger, more complex programs, abstraction helps manage that complexity. We've already discussed procedural abstraction, i.e. using functions to break down the flow of our program into manageable sub-tasks.

Today, we'll introduce Abstract Data Types (ADTs), which serve as a combined abstraction for data and the functions that operate on that data.

Specifically, we'll define some conventions for ADTs as they could be implemented in the C language (which is both the precursor to C++ and also a contemporary language that used in lower-level systems development). We're starting here for a few reasons:

  • The C style will expose more plainly some of the basic fundamentals of ADTs.
  • More practice with pointers! (spoiler alert, we'll be using pointers)
  • Additional language features we'll see for C++ style ADTs will naturally build on conventions we define first in the C style.

But first, let's take a detour to formally acknowledge the const keyeword, which has been showing up and will start showing up even more in the near future…

Updated Fall 2024
1: The const Keyword
1.1 Not Started

The const keyword is a type qualifier that we can add to declarations to tell the compiler that we don't intend for some value to change or be changeable. For it's part, the compiler then double checks for us that we don't accidentally try to do this and gives an error if we do!


1.1 The const Keyword

Provided the declarations below, which of the following assignments cause a compiler error due to a violation of const? (Write "ok" or "error".)

int x = 3;
const int y = x;
const int * ptr1 = &x;
int * const ptr2 = &x;
const int &ref = x;

y = 5;

*ptr1 = 5;

ptr1 = &y;

*ptr2 = 5;

ptr2 = &x;

ref = 5;

x = 5;

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

2: const Conversions
2.1 Not Started

The compiler also needs to decide where implicit conversions involving const should be allowed. The motivating principle is that we should never leave the program "less safe" than it was before in terms of protecting const objects. Let's take a look at a few examples…


Perhaps the most important place these rules are realized is in function call parameters as a part of interface specification. Following the rules above, the compiler will only allow a function to be called on a const object if the parameters also include the necessary const qualification to continue protecting that object. Essentially, only functions that "promise" not to change their parameters are allowed to be called on const objects/variables.


2.1 const in Function Parameters

Consider these function signatures and some variables declared in a main() function.

One of the function calls in main() below is "sus" (i.e. suspicious), in that it would put potentially put const objects at risk if the compiler allowed it. Can you find which one?

void teal(const int *a);
void red(int &a);
void purple(int a);

int main() {
  const int x = 10;
  int y = 10;

  teal(&x);
  red(x);
  purple(x);

  teal(&y);
  red(y);
  purple(y);

}

For which function call does the compiler produce an error? Briefly explain why.

Sample solution… The compiler will prohibit the call to red(x) since the parameter is pass-by-reference and does not maintain the const. If the call were allowed, the implementation of red could then potentially change the value of x, which was supposed to be const.


3: Intro to structs
3.1 Not Started

Now, back to our main event… defining and using compound objects.


To recap the fundamentals:

  • We can define a new compound object type via a struct definition (e.g. Person).
  • The struct definition contains member variable declarations. (e.g. what components does a Person have?)
  • We define objects as instances of that type and use them in the program.
  • Individual members are accessed via the . operator (also called the "member access operator").

If you've got a struct object that is const-qualified, that forbids assignment to the struct as a whole and also forbids assignment to its individual members. That fits with the idea of const as "this shouldn't change".

Finally, we can work with structs via pointers. If you're doing that, the syntax for member access changes. For example, assume obj is a Person object and ptr is a Person* pointer that points to that object. Then you would access the person's age as either:

  • obj.age
  • ptr->age

Use the . for objects and the -> for pointers.

3.1 Exercise: Practice with structs

Complete each of the tasks described in the comments.

Sample solution…

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

  // Task 1: Define a struct called "Sandwich" with the members listed below.
  //         Use the names given and choose an appropriate type for each.
  //  "name"    A name, e.g. "Reuben", "Tofu Bánh mì", "Chicken Shawarma"
  //  "is_veg"  A true/false value indicating whether the sandwich is vegetarian
  //  "price"   The cost to buy the sandiwch, e.g. 7.99
  struct Sandwich {
    string name;
    bool is_veg;
    double price;
  };

  int main() {
    // Task 2: Define and initialize a Sandwich variable as described below:
    // - You may name the variable whatever you like.
    // - The variable should be declared as const.
    // - Use the "= {}" notation to give each member a value.
    const Sandwich s = {"Falafel", true, 7.50};

    // Task 3: Create a pointer variable pointing to that Sandwich.
    const Sandwich *ptr = &s;

    // Task 4: Use the -> operator to print the name of the sandwich.
    cout << ptr->name << endl;
  }


4: structs and Functions
4.1 Not Started

We'll want to package up complex operations on structs into functions to form abstractions. Let's take a look…


Here's a written version of the flowchart in the video, for quick reference:

  • If you need to modify the original object, use pass-by-pointer or pass-by-reference.
  • If you don't modify the original object, use pass-by-pointer-to-const or pass-by-reference-to-const. This protects against accidental modification but more importantly also ensures your function can actually be called on const objects.
  • Only use pass-by-value for primitive objects (e.g. int, double, etc.) or very small compound objects. If the objects are large (e.g. string, vector, your own custom structs, etc.), pass-by-value makes an expensive and unnecessary copy.
4.1 Exercise: structs and Functions

Each of the following implementations of Person_birthday() has a problem - some will not compile while others will run but ultimately not work as expected. Describe what the problem is and one way to fix it.

// Version 1
void Person_birthday(const Person *p) {
  ++p->age;
}

// Version 2
void Person_birthday(Person p) {
  ++p.age;
}

// Version 3
void Person_birthday(Person *p) {
  *(p.age)++;
}

// Version 4
void Person_birthday(Person &p) {
  ++p->age;
}

Sample solution…

  // Version 1
  // There shouldn't be a const in the parameter,
  // since this function IS intended to change
  // the Person it's called on.
  void Person_birthday(const Person *p) {
    ++p->age;
  }

  // Version 2
  // The pass-by-value parameter should be pass-by-reference,
  // otherwise, we can't adjust the original Person's age.
  void Person_birthday(Person p) {
    ++p.age;
  }

  // Version 3
  // The parentheses here are misplaced. They need to be
  // placed as (*p).age++, otherwise the compiler attempts
  // to do the ++ before the *, which won't work.
  void Person_birthday(Person *p) {
    *(p.age)++;
  }

  // Version 4
  // The -> operator can be used as a convenient shorthand
  // for member variable access through a pointer, but not
  // through a reference. For a reference, just use the .
  // operator directly like: ++p.age
  void Person_birthday(Person &p) {
    ++p->age;
  }


5: C-Style ADTs
5.1 Not Started

Structs form the foundation of ADTs in C, acting as a data representation that allows us to model heterogeneous real-world objects. What makes a full ADT is the introduction of associated behaviors (i.e. functions) as well as plain data. We implement these behaviors as associated functions, which operate on an ADT struct via a pointer parameter.

Here's some details:


5.1 Exercise: Triangle_scale()

Let's say we want to add a function to scale a triangle by a given factor. Here's an example:

struct Triangle {
  double a, b, c;
};

int main() {
  Triangle t1 = { 2, 2, 2 };
  cout << Triangle_perimeter(&t1) << endl; // prints 6

  Triangle_scale(&t1, 2); // Scale up by a factor of 2

  cout << Triangle_perimeter(&t1) << endl; // prints 12
}

Which of the implementations of Triangle_scale() below are correct? Write "correct" or "incorrect". For each that is not correct, explain what's wrong with it.

// Implementation #1
void Triangle_scale(const Triangle *tri, double s) {
  tri->a *= s;
  tri->b *= s;
  tri->c *= s;
}

// Implementation #2
void Triangle_scale(Triangle *tri, double s) {
  a *= s;
  b *= s;
  c *= s;
}

// Implementation #3
void Triangle_scale(double s) {
  t1.a *= s;
  t1.b *= s;
  t1.c *= s;
}

// Implementation #4
void Triangle_scale(Triangle *tri, double s) {
  tri->a *= s;
  tri->b *= s;
  tri->c *= s;
}

// Implementation #5
void Triangle_scale(Triangle tri, double s) {
  tri.a *= s;
  tri.b *= s;
  tri.c *= s;
}

Sample solution…

  // Implementation #1
  // **Incorrect** - there should not be a const on the Triangle
  // parameter because the function needs to modify its members
  void Triangle_scale(const Triangle *tri, double s) {
    tri->a *= s;
    tri->b *= s;
    tri->c *= s;
  }

  // Implementation #2
  // **Incorrect** - the member variables a, b, and c must be
  // accessed through the pointer tri, e.g. tri->a
  void Triangle_scale(Triangle *tri, double s) {
    a *= s;
    b *= s;
    c *= s;
  }

  // Implementation #3
  // **Incorrect** - t1 is not in scope for this function.
  // Instead, a pointer to the triangle to work with should
  // be passed in to the function (e.g. pointing at t1).
  void Triangle_scale(double s) {
    t1.a *= s;
    t1.b *= s;
    t1.c *= s;
  }

  // Implementation #4
  // **Correct**
  void Triangle_scale(Triangle *tri, double s) {
    tri->a *= s;
    tri->b *= s;
    tri->c *= s;
  }

  // Implementation #5
  // **Incorrect** - because the triangle is passed by
  // value, the scaling modification is made to a copy
  // and the original triangle remains unchanged
  void Triangle_scale(Triangle tri, double s) {
    tri.a *= s;
    tri.b *= s;
    tri.c *= s;
  }


6: ADT Initialization and Representation Invariants

An essential component of proper ADT design is the use of representation invariants to express conditions that differentiate valid data (e.g. a Triangle with sides 3, 4, and 5) from invalid, nonsense values (e.g. one of the side lengths is -10).


There are two main perspectives on representation invariants when you're implementing code:

  1. There's a responsibility to ensure the invariants are followed and aren't broken by bad code (e.g. don't allow creating an invalid Triangle with negative side lengths).
  2. You may assume the invariants are true when implementing ADT functions, kind of like an implicit REQUIRES clause (e.g. when implementing Triangle_scale() we don't need to worry about "what if the sides are negative??").

#1 is a bit of extra work we put in so that we can rely on #2.

7: Interfaces and Implementations

Just a few high level comments on the relationship between interfaces and implementations in ADT design…

8: ADTs in Project 2
8.1 Not Started

Let's take a quick look at the way abstraction is used in project 2 to build Matrix and Image ADTs.


8.1

Which of the following are true about ADTs in project 2?

9: Function Overloading

In C++ (and some other programming languages), it's allowed to have multiple functions with the same name as long as they have different parameter types. This is called function overloading.

10: Unit Testing ADTs

Of course, just as we write unit tests for functions (which are the realization of procedural abstractions in our code), we should also write tests for ADTs to ensure that the behavior of their implementation matches with their specified interface.

Let's take a look at this with some examples for testing the Matrix ADT, including some specifics for testing C-Style ADTs without breaking their interface.
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.