Unit 07: The Standard Template Library

  1. Introduction
  2. STL Array
  3. STL Vector
  4. STL List
  5. STL Map
  6. STL Stack
  7. STL Queue

  8. Example code and additional resources

This week's stuff:

Accessibility

You can read through / play the audio for each slide at your own pace, or

Introduction

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.

STL Array

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;
}

STL Vector

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;
}

STL List

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;
}

STL Map

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;
}

STL Stack

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();
}

STL Queue

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 and additional resources

Example code: (repository)

  1. STL Array
  2. STL Vector
  3. STL List
  4. STL Map
  5. STL Queue
  6. STL Stack
  7. STL Map: Word counter

Archived videos and class lectures: