{ "cells": [ { "cell_type": "markdown", "metadata": { "toc": true }, "source": [ "

Table of Contents

\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# STL Sequence Containers" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "The Standard Template Library (STL) is a programmer's dream. It offers efficient ways to:\n", "- store\n", "- access\n", "- manipulate\n", "- view data\n", "\n", "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. \n", "\n", "## Overview of STL\n", "\n", "![](https://i.imgur.com/zO1sozu.png)\n", "Source: CS106L-Stanford\n", "" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "- **Containers:** a collection of container classes. For example:\n", " - `map:` an associative collection of key/value pairs\n", " - `vector:` a growing list of elements.\n", " \n", "- **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. \n", "\n", "- **Algorithms:** functions that operate over ranges of data specified by iterators. \n", "\n", "- **Adapters:** objects which transform an object from one form into another. For instance:\n", " - `stack` adapter transforms a regular vector or list into a LIFO (Last In First Out) container.\n", " - `istream_iterator` transforms a standard C++ stream inot an STL iterator.\n", " \n", "- **Functions:** facilities for creating and modifying functions at runtime.\n", "\n", "- **Allocators:** allow clients of the container classes to customize how memory is allocated and deallocated, either for diagnostic or performance reasons. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Vectors" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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. " ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "#include \n", "#include // Necessary to use vector\n", "#include \n", "#include " ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "// Create a vector containing integers\n", "std::vector v = {7, 10, 15, 8, 98, 0};" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Add two more integers to vector using `push_back()`**" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": [ "v.push_back(45);\n", "v.push_back(56);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Helper function to iterate and print values of vector**" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [], "source": [ "void PrintVector(std::vector& v){\n", " for(int n : v){\n", " std::cout << n << ' ';\n", " \n", " }\n", " \n", " std::cout << std::endl;\n", "}" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "7 10 15 8 98 0 45 56 \n" ] } ], "source": [ "PrintVector(v)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Grow the vector, setting new elements to 0**" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "7 10 15 8 98 0 45 56 0 0 \n" ] } ], "source": [ "v.resize(10);\n", "PrintVector(v)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ " 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()`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**`capacity()`: returns the number of element that can be held in currently allocated storage**" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(unsigned long) 12\n" ] } ], "source": [ "v.capacity()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**`shrink_to_fit()`: reduces memory usage by freeing unused memory**" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": [ "v.shrink_to_fit()" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(unsigned long) 10\n" ] } ], "source": [ "v.capacity()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**`resize()`: changes the number of elements stored**. E.g; Grow the vector, setting new elements to 100**" ] }, { "cell_type": "code", "execution_count": 10, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "7 10 15 8 98 0 45 56 0 0 100 100 100 \n" ] } ], "source": [ "v.resize(13, 100);\n", "PrintVector(v);" ] }, { "cell_type": "code", "execution_count": 11, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(unsigned long) 20\n" ] } ], "source": [ "v.capacity()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**`pop_back()`: removes the last element**" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "7 10 15 8 98 0 45 56 0 0 100 100 \n" ] } ], "source": [ "v.pop_back();\n", "PrintVector(v);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**NOTE:** for detailed information about `std::vector`, check out the [C++ reference](http://en.cppreference.com/w/cpp/container/vector)." ] }, { "cell_type": "code", "execution_count": 13, "metadata": {}, "outputs": [], "source": [ "?std::deque" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## deque" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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. \n", "\n", "\n", "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. \n", "\n", " \n" ] }, { "cell_type": "code", "execution_count": 14, "metadata": {}, "outputs": [], "source": [ "#include \n", "#include " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Create a deque (pronounced \"deck\") containing integers**" ] }, { "cell_type": "code", "execution_count": 15, "metadata": {}, "outputs": [], "source": [ "std::deque d = {45, 48, 40, 79};" ] }, { "cell_type": "code", "execution_count": 16, "metadata": {}, "outputs": [], "source": [ "void PrintDeque(std::deque& d){\n", " for(int n : d){\n", " std::cout << n << ' ';\n", " \n", " }\n", " \n", " std::cout << std::endl;\n", "}" ] }, { "cell_type": "code", "execution_count": 17, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "45 48 40 79 \n" ] } ], "source": [ "PrintDeque(d);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Add an integer to the beginning and end of the queue**" ] }, { "cell_type": "code", "execution_count": 18, "metadata": {}, "outputs": [], "source": [ "d.push_front(13);\n", "d.push_back(25);" ] }, { "cell_type": "code", "execution_count": 19, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "13 45 48 40 79 25 \n" ] } ], "source": [ "PrintDeque(d);" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**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`" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**NOTE:** for detailed information about `std::deque`, check out the [C++ reference](http://en.cppreference.com/w/cpp/container/deque) or just type `?std::queue` in a notebook cell to get live documentation." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Container Adapters\n", "\n", "How can we implement stack and queue using the containers we have?\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Stack" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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.\n", "\n", "\n", "**Stack:** just limit the functionality of a vector/deque to only allow `push_back` and `pop_back`." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The functions associated with stack are:\n", "- `empty()` -- Returns whether the stack is empty\n", "- `size()` -- Returns the size of the stack\n", "- `top()` -- Returns a reference to the top most element of the stack\n", "- `push(g)` -- Adds the element 'g' at the top of the stack\n", "- `pop()` -- Deletes the top most element of the stack" ] }, { "cell_type": "code", "execution_count": 20, "metadata": {}, "outputs": [], "source": [ "#include " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Create a stack of integers**" ] }, { "cell_type": "code", "execution_count": 21, "metadata": {}, "outputs": [], "source": [ "std::stack s;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Helper function to show the stack**" ] }, { "cell_type": "code", "execution_count": 22, "metadata": {}, "outputs": [], "source": [ "void ShowStack(std::stack mystack){\n", " \n", " std::stack s = mystack;\n", " while (!s.empty()){\n", " \n", " std::cout << '\\t' << s.top();\n", " s.pop();\n", " }\n", " \n", " std::cout << std::endl;\n", "}" ] }, { "cell_type": "code", "execution_count": 23, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n" ] } ], "source": [ "ShowStack(s)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Push some elements onto the stack**" ] }, { "cell_type": "code", "execution_count": 24, "metadata": {}, "outputs": [], "source": [ "s.push(10);\n", "s.push(30);\n", "s.push(20);\n", "s.push(5);" ] }, { "cell_type": "code", "execution_count": 25, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\t5\t20\t30\t10\n" ] } ], "source": [ "ShowStack(s)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "** Get stack size**" ] }, { "cell_type": "code", "execution_count": 26, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(unsigned long) 4\n" ] } ], "source": [ "s.size()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Get the top of the stack**" ] }, { "cell_type": "code", "execution_count": 27, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(int) 5\n" ] } ], "source": [ "s.top()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Pop top of the stack**" ] }, { "cell_type": "code", "execution_count": 28, "metadata": {}, "outputs": [], "source": [ "s.pop();" ] }, { "cell_type": "code", "execution_count": 29, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\t20\t30\t10\n" ] } ], "source": [ "ShowStack(s)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Queue" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "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. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "The functions supported by queue are:\n", "- `empty()` -- Returns whether the queue is empty\n", "- `size()` -- Returns the size of the queue\n", "- `front()` -- Returns a reference to the first element of the queue.\n", "- `back()` -- Returns a reference to the last element of the queue\n", "- `push(g)` -- Adds the element `g` at the end of the queue\n", "- `pop()` -- Deletes the first element of the queue." ] }, { "cell_type": "code", "execution_count": 30, "metadata": {}, "outputs": [], "source": [ "#include " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Create an empty queue**" ] }, { "cell_type": "code", "execution_count": 31, "metadata": {}, "outputs": [], "source": [ "std::queue q;" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Helper function to show content of the queue**" ] }, { "cell_type": "code", "execution_count": 32, "metadata": {}, "outputs": [], "source": [ "void ShowQueue(std::queue myqueue){\n", " \n", " std::queue q = myqueue;\n", " while (!q.empty()){\n", " \n", " std::cout << '\\t' << q.front();\n", " q.pop();\n", " }\n", " \n", " std::cout << std::endl;\n", "}" ] }, { "cell_type": "code", "execution_count": 33, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n" ] } ], "source": [ "ShowQueue(q)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Add some elements to the queue**" ] }, { "cell_type": "code", "execution_count": 34, "metadata": {}, "outputs": [], "source": [ "q.push(10);\n", "q.push(20);" ] }, { "cell_type": "code", "execution_count": 35, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\t10\t20\n" ] } ], "source": [ "ShowQueue(q)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Get queue size**" ] }, { "cell_type": "code", "execution_count": 36, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(unsigned long) 2\n" ] } ], "source": [ "q.size()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Get front of the queue**" ] }, { "cell_type": "code", "execution_count": 37, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(int) 10\n" ] } ], "source": [ "q.front()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Get back of the queue**" ] }, { "cell_type": "code", "execution_count": 38, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "(int) 20\n" ] } ], "source": [ "q.back()" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Pop front of the queue**" ] }, { "cell_type": "code", "execution_count": 39, "metadata": {}, "outputs": [], "source": [ "q.pop()" ] }, { "cell_type": "code", "execution_count": 40, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\t20\n" ] } ], "source": [ "ShowQueue(q)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Next Time: Associative Containers and Iterators" ] } ], "metadata": { "kernelspec": { "display_name": "xeus C++14", "language": "", "name": "xeus-cling-cpp14" }, "language_info": { "codemirror_mode": "text/x-c++src", "file_extension": ".cpp", "mimetype": "text/x-c++src", "name": "c++", "version": "" }, "toc": { "nav_menu": {}, "number_sections": true, "sideBar": true, "skip_h1_title": false, "toc_cell": true, "toc_position": {}, "toc_section_display": "block", "toc_window_display": true } }, "nbformat": 4, "nbformat_minor": 2 }