• 1.1: Abstract Data Types

    • An abstract data type allows us to group native built-in data types into a compound type whose instances can be individually referenced. Far from just containing the data itself, an abstract data type also contains functions that operate on its data. There can be many instances of (specific uses of) an individual abstract data type. The data contained in each instance and the operations on that data are independent of all other instances. It is also possible for an abstract data type to be composed of other abstract data types. Within object-oriented programming, abstract data types are referred to as classes. An instance of a class is called an object. If we do not embed functions (methods) within an abstract data type then we are left with a data structure that is common in modular programming. Abstract data types are the foundation for understanding and applying specific data types, native or user-defined. They also form the foundation for structured and object-oriented programming. Ultimately, these lead to parallel and distributed processing.

    • John DeNero's Composing Programs: "Data Abstraction" Page

      Read this section, which expands the discussion and illustrates with native built-in types. The discussion in 2.2.1 is true of all native built-in types, and the tiny bit of Python code at the end of 2.2.1 should be easily understandable. Each of the built-in types have their own methods, which apply to them and which operate appropriately according to their type. Also, their internal representation is hidden at the code-level perspective.

    • Stanford University: Julie Zelenski's "Programming Abstractions: Sort Template with Callback" Page

      While all languages include abstract data types in the form of native data types and their operations, there is also the matter of user-defined compound types. These abstract data types are introduced this video, which you should watch starting at 44:30. This begins a language-agnostic discussion that is very valuable.

    • Stanford University: Julie Zelenski's "Programming Abstractions: Abstract Data Types" Page

      The discussion from the previous video continues in this lecture. Watch from the beginning until 7:00.

    • Derrick Robinson's "Intermediate C++" Page

      Read these sections, which discuss the foundation of ADTs and the way they are implemented in C (as structures) and C++ (as classes). The Standard Template Library (STL) is now officially part of C++. The STL continues a natural progression from structures (data only) to classes (data plus operations on that data) to a library of trusted classes that implement often-needed data/method containers. Since the STL is largely data-type agnostic, templates begin to be very useful.

    • Stanford University: Keith Schwarz's "Programming Abstractions: Standard Template Library" Page

      This lecture introduces the C++ Standard Template Library (STL) from 21:08 to 29:25. STL is a formal part of the C++ language, and is a set of class templates for many important and commonly-used program components. It is very much worth your while to be familiar and practiced with this library.