Play interactively with C++ - Sequence Containers

STL Sequence Containers

The Standard Template Library (STL) is a programmer's dream. It offers efficient ways to:

  • store
  • access
  • manipulate
  • view data

and is designed for maximum extensibility. Once a programmer has gotten over the initial syntax hurdles, they quickly learn to appreciate the STL's sheer power and flexibility.

Overview of STL

Source: CS106L-Stanford

  • Containers: a collection of container classes. For example:

    • map: an associative collection of key/value pairs
    • vector: a growing list of elements.
  • Iterators: objects that view and modify ranges of stored data. Each STL container exports iterators. Iterators have a common interface, allowing the programmer to write code that operates on data stored in arbitrary containers.

  • Algorithms: functions that operate over ranges of data specified by iterators.

  • Adapters: objects which transform an object from one form into another. For instance:

    • stack adapter transforms a regular vector or list into a LIFO (Last In First Out) container.
    • istream_iterator transforms a standard C++ stream inot an STL iterator.
  • Functions: facilities for creating and modifying functions at runtime.

  • Allocators: allow clients of the container classes to customize how memory is allocated and deallocated, either for diagnostic or performance reasons.

Vectors

A std::vector is an object that represents a sequence of elements. The elements in a vector are indexed, meaning that they can have a well-defined position in the sequence.

In [1]:
#include <iostream>
#include <vector>  // Necessary to use vector
#include <string>
#include <sstream>
In [2]:
// Create a vector containing integers
std::vector<int> v = {7, 10, 15, 8, 98, 0};

Add two more integers to vector using push_back()

In [3]:
v.push_back(45);
v.push_back(56);

Helper function to iterate and print values of vector

In [4]:
void PrintVector(std::vector<int>& v){
    for(int n : v){
        std::cout << n << ' ';
        
    }
    
    std::cout << std::endl;
}
In [5]:
PrintVector(v)
7 10 15 8 98 0 45 56 

The storage of the vector is handled automatically, being expanded and contracted as needed. Vectors usually occupy more space than static arrays, because more memory is allocated to handle future growth. This way a vector does not need to reallocate each time an element is inserted, but only when the additional memory is exhausted.

Grow the vector, setting new elements to 0

In [6]:
v.resize(10);
PrintVector(v)
7 10 15 8 98 0 45 56 0 0 

The total amount of allocated memory can be queried using capacity() function. Extra memory can be returned to the system via a call to shrink_to_fit()

capacity(): returns the number of element that can be held in currently allocated storage

In [7]:
v.capacity()
(unsigned long) 12

shrink_to_fit(): reduces memory usage by freeing unused memory

In [8]:
v.shrink_to_fit()
In [9]:
v.capacity()
(unsigned long) 10

resize(): changes the number of elements stored. E.g; Grow the vector, setting new elements to 100**

In [10]:
v.resize(13, 100);
PrintVector(v);
7 10 15 8 98 0 45 56 0 0 100 100 100 
In [11]:
v.capacity()
(unsigned long) 20

pop_back(): removes the last element

In [12]:
v.pop_back();
PrintVector(v);
7 10 15 8 98 0 45 56 0 0 100 100 

NOTE: for detailed information about std::vector, check out the C++ reference.

In [13]:
?std::deque

deque

There are several aspects of the vector that can be troublesome in certain applications. In particular, the vector is only designed to grow in one direction; calling push_back() inserts elements at the end of the vector, and resize() always appends elements to the end.

A std:deque is an indexed sequence container that allows fast insertion and deletion at both its beginning and its end. As opposed to std:vector, the elements of a deque are not stored contiguously: typical implementations use a sequence of individually allocated fixed-size arrays, with additional bookkeeping, which means indexed access to deque must perform two pointer dereferences, compared to vector's indexed access which performs only one.

In [14]:
#include <iostream>
#include <deque>

Create a deque (pronounced "deck") containing integers

In [15]:
std::deque<int> d = {45, 48, 40, 79};
In [16]:
void PrintDeque(std::deque<int>& d){
    for(int n : d){
        std::cout << n << ' ';
        
    }
    
    std::cout << std::endl;
}
In [17]:
PrintDeque(d);
45 48 40 79 

Add an integer to the beginning and end of the queue

In [18]:
d.push_front(13);
d.push_back(25);
In [19]:
PrintDeque(d);
13 45 48 40 79 25 

A deque can do everything a vector can do and also unlike a vector, it is possible (and fast) to push_front and pop_front

NOTE: for detailed information about std::deque, check out the C++ reference or just type ?std::queue in a notebook cell to get live documentation.

Container Adapters

How can we implement stack and queue using the containers we have?

Stack

Stack is a type of container adapters with LIFO (Last In First Out) or FILO (First in, Last Out) data structure, where a new element is added at one end and (top) an element is removed from that end only.

Stack: just limit the functionality of a vector/deque to only allow push_back and pop_back.

The functions associated with stack are:

  • empty() -- Returns whether the stack is empty
  • size() -- Returns the size of the stack
  • top() -- Returns a reference to the top most element of the stack
  • push(g) -- Adds the element 'g' at the top of the stack
  • pop() -- Deletes the top most element of the stack
In [20]:
#include <stack>

Create a stack of integers

In [21]:
std::stack<int> s;

Helper function to show the stack

In [22]:
void ShowStack(std::stack<int> mystack){
    
    std::stack<int> s = mystack;
    while (!s.empty()){
        
        std::cout << '\t' << s.top();
        s.pop();
    }
    
    std::cout << std::endl;
}
In [23]:
ShowStack(s)

Push some elements onto the stack

In [24]:
s.push(10);
s.push(30);
s.push(20);
s.push(5);
In [25]:
ShowStack(s)
	5	20	30	10

Get stack size

In [26]:
s.size()
(unsigned long) 4

Get the top of the stack

In [27]:
s.top()
(int) 5

Pop top of the stack

In [28]:
s.pop();
In [29]:
ShowStack(s)
	20	30	10

Queue

Queue is a type of container adaptors which operate in a first in first out (FIFO) type of arrangement. Elements are inserted at the back (end) and are deleted from the front.

The functions supported by queue are:

  • empty() -- Returns whether the queue is empty
  • size() -- Returns the size of the queue
  • front() -- Returns a reference to the first element of the queue.
  • back() -- Returns a reference to the last element of the queue
  • push(g) -- Adds the element g at the end of the queue
  • pop() -- Deletes the first element of the queue.
In [30]:
#include <queue>

Create an empty queue

In [31]:
std::queue<int> q;

Helper function to show content of the queue

In [32]:
void ShowQueue(std::queue<int> myqueue){
    
    std::queue<int> q = myqueue;
    while (!q.empty()){
        
        std::cout << '\t' << q.front();
        q.pop();
    }
    
    std::cout << std::endl;
}
In [33]:
ShowQueue(q)

Add some elements to the queue

In [34]:
q.push(10);
q.push(20);
In [35]:
ShowQueue(q)
	10	20

Get queue size

In [36]:
q.size()
(unsigned long) 2

Get front of the queue

In [37]:
q.front()
(int) 10

Get back of the queue

In [38]:
q.back()
(int) 20

Pop front of the queue

In [39]:
q.pop()
In [40]:
ShowQueue(q)
	20

Next Time: Associative Containers and Iterators

Comments