Classes are often written to model something in the "real world". For example, you might have a class that represents information about a student, or a bank account (classic textbook classes), or represents a calculator.
However, there is a category of classes called container classes. As you might guess from the name "container", they store items. The most common container you've seen isn't even a class: it's an array. Yet, arrays may not always behave the way you want.
For example, suppose you would like to an object to represent a set. A set supports the following operations:
The number of elements in a set.
Combine two sets together to create a new set, containing elements that appear in either set.
Remove the elements of one set that appear in a second set.
Combine two sets together to create a new set containing elements that appear in both sets.
However, a set can also be thought of as the operations that can be applied to a set.
That leads us to the idea of an abstract data type.
It's called "abstract", because we're not thinking about code. When your math teacher talks about sets, or ordered pairs, these are abstract ideas. They aren't C++ code.
However, you can implement these ADTs into classes. In fact, classes are a great way to implement ADTs. After all, what are classes? A class contains data, which is hidden as private (at least, you're supposed to), and methods, which are applied to objects.
Before classes, programmers would write structures, where the data was public, and this made ADTs less abstract. Programmers could "see" the inner workings.
An abstract data type consists of an abstract notion of data, and operations that can be performed on the data.One reason to create ADTs is to give you the freedom to imagine something that doesn't exist natively in the programming language, e.g. a set, a queue, a stack, etc., and think about what operations it ought to support, and then implement it.
That leads to the next step: implementing ADTs.
An implementation of an ADT is where the programmer decides on the data representation.At some point, an ADT is implemented. That means, the programmer decides how to represent the data. The representation is merely something that has to be done in order to make the create a class from an ADT. As far as the user of the class is concerned, the data representation is unimportant, since they only deal with the interface (i.e., the methods). But as the implementer of interface, you need to decide how to represent the data.
For example, think about how one should implement a set of numbers. You can pick an array, or a linked list, or a dynamic array. You can use an STL vector, or an STL list. No matter what you pick, the behavior of the set should remain the same.
Oh, there's an exception. Sometimes, the set may fail because it's too large. For example, if you picked a static array, then you have a maximum size. Up until you reach the maximum size, the set should behave as desired. However, add an element beyond the maximum size, and the set doesn't work (after all, you don't have space for it).
Of course, this is a problem with any structure, not just static arrays. You will have a maximum size problem with dynamic arrays too, except that the problem should occur much later, because you can keep growing the size of the array until you run out of memory.
So, if all the ways you can implement an ADT don't particularly matter, then
As you should recall, an ADT consists of some "abtract" notion of data, AND operations that can be performed on that data. Again, this corresponds to the private data and public methods of a class (although the private data is considered to be "concrete", rather than abstract).
To think of a sorted list, consider a vector. A vector is an ordered n-tuple. For example, <1, 3, 7> is an ordered 3-tuple. By "ordered", it means the order matters (unlike a set, where the order doesn't matter). Thus, the tuple <1, 3, 7> and the tuple <3, 1, 7> are not the same, since the order is different.
The main features of a tuple are the number of elements in the tuple (it can be zero), and the value stored at each position of the tuple. For the time being, you can think of it as an array, although, in general, we like to think of a tuple without regard to any programming language, but to think of it as an array is fine.
A sorted list is a tuple that contains a particular kind of data. Normally, you would store a data type that can be compared such as integers. That way, it can be sorted. For example, < 1, 3, 7 > is sorted in increasing order.
There are some kinds of data type which aren't comparable, or at least, it isn't obvious how to compare them. For example, suppose you have coordinates, (x, y). What does it mean to have one coordinate be bigger than another?
What we're interested in is data types which can be compared, i.e., where the relational operators make sense.
In a database (which can be thought of as a sorted list), the "primary" key is what data is uniquely sorted under. For example, a student ID would be a primary key. There aren't two student records that contain the same primary key (that would be a conflict!).
The value associated with the key is the rest of the data associated with the student. Thus a student record consists of a key and value, and it is sorted based on the key.
Clearly, one important property of a key, if it is to be used in a sorted list, is that it can be compared using comparison operators.
There needs to be some operation that exists which allows the list to be process in sorted order. In this class, this will be achieved via iterators.
An iterator is basically a pointer, which will allow you to process a list from front to end. If the list is assumed to be sorted by key, then the iterator should process each object in the list in sorted order. Read about iterators.