Abstract Data Types

• Built-In Types

  • The types int, float, double, char, and bool are built-in types.  That is, they are part of the C++ language.

• Defined Types

  • By contrast, the string type is not built-in (i.e., we have to include <string> to get its definition).

  • However, string acts just like a built-in type in many situations:  declaration, assignment, I/O, parameter passing, etc.

  • When we build a new type with a rich set of operations which allow it to fit "naturally" within the C++ language, this new type is called an Abstract Data Type or ADT.

  • ADTs are created in C++ using the class construct.

  • Common ADTs include:

    • String

    • Vector

    • List

    • Stack

    • Queue

    • Binary Search Tree

    • Balanced Trees (AVL Tree, B-Tree, Red-Black Tree, 2-4 Tree)

    • Dequeue (pronounced "deck")

    • Bag

    • Set

    • ... and many, many more