Unit 07: The Standard Template Library
This week's stuff:
You can read through / play the audio for each slide at your own pace, or
In a Data Structures class we learn about how data structures are built and we learn to make our own. This helps us make the best choices, design-wise. However, in the real world you're probably not going to be creating your own vectors and lists - you'll probably be using whatever data structures are provided in your library, because they've already been written, tested, and optimized.
Let's take a look at some of the common data structures that are part of C++'s Standard Template Library. These are also structures that we will be learning to write ourselves in CS 250.
Documentation: https://cplusplus.com/reference/array/array/
The STL Array wraps a basic, fixed-length array. It is also fixed-length, but provides some basic functionality
such as .size()
to get the amount of items in the array without having to create a separate variable to track that.
array<int, 100> myArray;
cout << "Size: " << myArray.size();
cout << "Enter item 0: ";
cin >> myArray[0];
for ( int i = 0; i < myArray.size(); i++ )
{
cout << i << " = " << myArray[i] << endl;
}
Documentation: https://cplusplus.com/reference/vector/vector/
The STL Vector is a class that wraps a dynamic array so we get the resizability of a dynamic array without having to worry about the memory management side.
vector<int> myVector;
cout << "Size: " << myVector.size();
cout << "Enter item 0: ";
int item;
cin >> item;
myVector.push_back( item );
for ( int i = 0; i < myVector.size(); i++ )
{
cout << i << " = " << myVector[i] << endl;
}
Documentation: https://cplusplus.com/reference/list/list/
The STL List is a class that wraps a linked list, so again we get resizability without having to do memory management, but lists don't provide random access like an array-based structure does.
list<int> myList;
cout << "Size: " << myList.size();
myList.push_front( 1 ); // Stored at the start of the list
myList.push_back( 10 ); // Stored at the end of the list
cout << "Front item: " << myList.get_front() << endl;
cout << "Back item: " << myList.get_back() << endl;
myList.pop_front();
myList.pop_back();
for ( auto& item : myList )
{
cout << item << endl;
}
Documentation: https://cplusplus.com/reference/map/map/
The STL Map allows us to create a set of key-value pairs that are stored together. Each key must be unique. The key and the value data types can be any data type.
map<int, string> area_codes;
area_codes[913] = "Northeastern Kansas";
area_codes[816] = "Northwestern Missouri";
cout << "Size: " << area_codes.size();
int key;
cout << "Enter an area code: ";
cin >> key;
cout << "The region for that is: " << area_codes[ key ];
for ( auto& item : area_codes )
{
cout << "Key: " << item.first << ", Value: " << item.second << endl;
}
Documentation: https://cplusplus.com/reference/stack/stack/
A Stack is a type of restricted-access data type that is especially useful in computer science. We only have access to the top of the stack at any given time.
stack<char> myStack;
cout << "Size: " << myStack.size();
myStack.push( 'A' );
myStack.push( 'B' );
myStack.push( 'C' );
cout << "Top item is: " << myStack.top() << endl;
myStack.pop(); // Remove top item
while ( !myStack.empty() )
{
cout << "Top: " << myStack.top() << endl;
myStack.pop();
}
Documentation: https://cplusplus.com/reference/queue/queue/
A Queue is a type of restricted-access data type that is common in the real world (and also useful for computer science. :) We add new items to the back of the queue, and access and remove items at the front of the queue.
queue<char> myQueue;
cout << "Size: " << myQueue.size();
myQueue.push( 'A' );
myQueue.push( 'B' );
myQueue.push( 'C' );
cout << "Front item is: " << myQueue.front() << endl;
myQueue.pop(); // Remove front item
while ( !myQueue.empty() )
{
cout << "Front: " << myQueue.front() << endl;
myQueue.pop();
}
Example code: (repository)
Archived videos and class lectures: