Abstract Data Types

As of yet, you've only used built-in, or primitive, data types, as well as a couple advanced types for file IO. By now, you've probably noticed that working with large quantities of data quickly becomes tedious, even when using arrays. For example, if you need to pass a function a x, y, and z coordinate, you have to specify three parameters. The most powerful feature of object-oriented languages such as C++ is the ability to define and use your own data types. Other purely procedural languages, such as C, provide a less powerful way to do the same. In C++, it is conventional to use classes as the base for object-oriented programming and advanced types, but for simpler types, and in C, structures are used instead. They're basically bare bones classes.


Advanced types are called “abstract” because they abstract lower-level data into higher-level types. You define them yourself, to your specifications. One ADT can reference or contain other ADTs—you can see how this can quickly become complicated. However, you should keep in mind that even the most complicated ADTs are, at their core, still made up of the primitive types. At some point, everything is integers, floating points, booleans, pointers, etc.

So, what exactly is a structure in C++? A defined structure is just like any other data type, like an int or a double, in that it simply describes data. But, the important part is that a single instance of a structure can hold multiple pieces of data, and what they are is up to you. Say you need to pass x, y, and z to a function, with structs, you can instead pass a structure containing all three values. Remember, structures and variables of their type are used in exactly the same way as the primitives.

Defining Structures

The syntax for defining a structure is relatively simple: to start, type the keyword "struct." Then, the type name of your structure. You're not declaring a variable here—you're specifying what the new data type will be called. For example, if you create a struct with the type name “student,” you can consequently create variables of type “student." The variable itself can have a completely unrelated identifier.

Next, add a pair of curly brackets and a closing semicolon and you’re technically done. However, your new type doesn't hold any data. To describe the data, simply add values within your brackets as if you were declaring variables. They can be of any type—primitives or other ADTs. These types are called data members, because they “belong” to the struct. Remember that these aren’t actually variables—you're simply describing what data the struct will hold. The actual data in memory will be created later.

struct student {
	string name;
	float gpa;

This example defines a “student” structure. Later in your code, you can now declare variables of type “student.” Creating a variable of your abstract type is called creating an instance of that type. An instance acts like any other variable—it can be passed as a parameter, it can be pointed to, it can be returned from a function, etc.

int main() {
	student someone;
	// Creates a new variable of type “student,” or in other words a new instance of “student.” 
	// Because you described a “student” previously, this variable will hold a string and a float.

	student anotherStudent;
	// You can create as many of these as you want, just like you would with, for example, integers

Here, we create two variables of type "student." Note that "student" is the data type, and the variable identifiers can be anything. Each student holds both a string and a name.

Using Structures

Now, you can create a variable of your ADT, but you have no way to access its data. Enter the dot operator (“.”). The dot operator allows you to access data members within an instance of an ADT. This is why you named your data members—you use the member identifiers to access them. Member names are the same across all instances of your ADT.

The syntax is extremely straightforward—simply type your variable identifier, the dot operator, and finally the member identifier. This statement acts as a variable of the member data type. You can assign values to the member, test on the member, read values from the member, pass the member to functions, etc.

Note that you cannot use the dot operator on the the type name itself (“student” for example). This is because the type name simply describes the data structure, and does not actually hold data. You need an instance of that type to access actual memory.

int main() {
	student aStudent;
	aStudent.name = “Steve”;
	aStudent.gpa = 3.7;
	cout << “Student name: “ << aStudent.name << endl;

In this example, we create an instance of "student" and assign values to its name and GPA. Then, we output the name to the console.

Pointers and Structures

Pointers to ADTs work in much the same ways as pointers to primitive data types. They are declared in the same way. Dereferencing works the same as well. However, dereferencing an ADT pointer still represents an abstract type. This means that when you deference an ADT pointer, you must then use the dot operator to access data members.

student myStudent;
student* stuPtr = &myStudent;

Here, we create a student and a student pointer to the student.

Because of the order of operations in C++, if you were to use the pointer like this...

cout << *stuPtr.name << endl;

...you will get a complier error, because your program is trying to use the dot operator before the dereference operator. Using the dot operator on a pointer doesn’t make sense, as a pointer does not contain data members. Hence, you must force your program to dereference first...

cout << (*stuPtr).name << endl;

...which works as expected. This syntax is quite clunky and annoying to type. But there is a better way—the arrow operator (“->”). The arrow operator does the exact same logical operation as dereferencing and using the dot operator (in the correct order). It is much easier and cleaner to work with.

cout << stuPtr->name << endl;

This code works exactly the same way as the previous example.

Dynamic Memory and Structures

Finally, there’s the use of dynamic memory with ADTs. Allocating dynamic arrays of ADTs is exactly the same as allocating dynamic arrays of any other type. You use the same “new” and “delete” syntax. However, because structures can contain any data type, including pointers, it follows that they can contain their own dynamically allocated memory. This process is not any different than what we've used previously, except that the memory address is stored in a data member. This means that when allocating the memory, you assign the address to a data member within an instance of your ADT. You must eventually delete the memory from the data member as well.

Don't worry if this causes some code mess—when we get into classes, this process will become much cleaner.

struct student {
	char* firstName;
	char* lastName;
	float gpa;

int main() {
	student s1;
	// Allocate the dynamic strings
	s1.firstName = new char[10];
	s1.lastName = new char[20];
	// Assign names
	strcpy(s1.firstName, “Steve”);
	strcpy(s1.lastName, “Irwin”);
	// Output names
	cout << “Student name: “ << s1.firstName << “ “ << s1.lastName << endl;
	// Always remember to delete all allocated memory
	delete[] s1.firstName;
	delete[] s1.lastName;

In this example, we define a "student" ADT. It has two character pointer data members to be used as dynamically allocated c-strings. In the first part of main, we create an instance of student and allocate two strings to its data members. Next, values are assigned and output. Finally, we must delete allocated memory. The data members hold the address of our strings, so we can deleted from them directly.

Programming Exercises

  1. Create a "card" ADT and a simple deck using an array of "card" instances. Try inputting cards from a file, outputting cards to the console, and shuffling the deck.
  2. [Maze Game Project] Try defining your player and other relevant concepts (the board, etc.) as their own ADTs.
  3. Create a cataloging system for “student” instances. You should be able to add a students and their relevant data, print them, sort them, and remove them. Include as many data members in your student type as you wish, but at least include “ID” and “name” data members.