STL

what does the STL do?

separates Algorithms from Data to allow for Code Reuse

what are the 3 categories within the STL?

algorithms, iterators, containers

what are containers? types of containers?

• containers are data structures that hold objects/data of arbitrary type

• types

  • sequence containers

  • associative containers (ordered and unordered)

  • container adapters

what are iterators? types?

• iterators are objects of arbitrary type that can step through elements of containers

• types

  • input

  • output

  • forward

  • bidirectional

  • random access

what are algorithms? types?

• algorithms are common operations used to manipulate elements in data structure

• types

  • mutating

  • non-mutating

  • sorting

  • numeric

  • removing

sequence containers

• implement data structures that can be accessed sequentially

• data arranged in a linear manner

• element order is independent from its value

• implemented using arrays or linked lists

• ex: vector, deque, list, array, forward_list

associative containers

• ordered

  • data arranged to facilitate fast associative operations

  • keys ordered by operator< to support efficient operations on elements

  • implemented using (balanced) binary search trees

  • ex: set, multiset, map, multimap

• unordered

  • unsorted collections

  • position of elements is irrelevant

  • implemented using hash tables

  • ex: unordered_set, unordered_multiset, unordered_map, unordered_multimap

container adapters

• are NOT containers

• provide different ways to access sequential and associative containers

• ex: stack, queue, priority_queue

details of array?

• a sequence container

• Static contiguous array (class template)

• array based

details of vector?

• a sequence container

• Dynamic contiguous array (class template)

• array based

details of deque?

• a sequence container

• Double-ended queue (class template)

• array based

details of forward_list?

• a sequence container

• Singly-linked list (class template)

• doubly-linked list based

details of list?

• a sequence container

• Doubly-linked list (class template)

• doubly-linked list based

std::array

• encapsulates FIXED-SIZE arrays

• supports const and mutable random access iterators

• amortized constant time insert/erase at its end

• linear time insert/erase in its middle

• contiguous storage for all types including bool

std::vector

• implemented as a dynamically allocated array (can grow and shrink)

• provides pre/re allocation, indexed storage, push_back, pop_back

• supports const and mutable random access iterators

• when capacity is reached, a new array is made with double the capacity and the data is copied into it

• common operations: push_back, emplace_back, at, size, clear

• advantages

  • contiguous memory = fast insert/remove from end

  • insert/remove more expensive if at beginning or middle

std::deque

• double-ended queue

• efficient O(1) insertion and removal at both ends via push_front() and pop_front()

• supports const and mutable random access iterators

• linear time insert/erase in its middle

std::forward_list

• has constant time insertion and deletion at any point in the sequence

• does not support random access iterator

• includes member functions for splicing

• implemented as a singly-linked list

std::list

• has constant time insertion and deletion at any point in the sequence

• does not support random access iterator

• supports const and mutable bidirectional iterators instead

• includes member functions for splicing, sorting, and merging

• implemented as a doubly-linked list

what is a set? std::set

• associative container

• an ordered collection containing no duplicate elements

• supports testing for membership, adding elements, and removing elements

• set operations: union, intersection, difference, subset

• value of elements cannot be modified

what is a map?

• associative container

• a set of ordered pairs containing a key and value (like python dictionary)

• keys map to values

• different keys can be mapped to the same value

ordered associative containers (2 qualities)

• values are “associated” with a key

• elements are automatically sorted

  • default is <

  • users can define own ordering

  • implemented using a binary search tree

  • no push_back or push_front

  • O(log(n)) searching most important feature

properties of std::set and std::multiset

• associative containers

• fast search: O(log(n))

• value of elements cannot be modified

what can associative containers std::multiset and std::multimap do?

support multiple equivalent (non-unique) keys

what is std::pair and what does it do

• STL helper class

• basis for associative containers

• can store heterogeneous pairs of data together

• binds first element (key) to second element (associated value)

what do associative containers std::map and std::multimap have in common?

don’t allow for duplicate KEYS

how do unordered containers store info (because they’re not stored in order)

• a hash function takes inputs and regurgitates it as an address in memory to place info

• if you don’t have a good hash function —> collision: when two or more items are assigned the same location in memory

properties of unordered containers

• fastest search/insert at any place: O(1)

• unordered set/multiset: element value cannot be changed

• unordered map/multimap: key cannot be changed

properties of std::unordered_set

• (unordered associative container)

• amortized constant time element lookup

• hash determines order of key

• includes const forward iterator

• elements are unique

• implemented as a hash table

properties of std::unordered_multiset

unordered set that allows duplicate elements

properties of std::unordered_map

• amortized constant time lookup of type T based on type Key

• implemented as a hash table; hash determines order of Key

• more efficient than map for element access, less for range iteration

• includes at least forward iterator

• keys are unique

properties of unordered_multimap

cannot use [] operator to access bc it can contain duplicate keys

how do stacks work?

• Last In First Out

  • can only access top of the stack

• elements are pushed/popped from the container

  • push adds an item to the top

  • pop removes an item from the top

• may be represented using a STL container adaptor or vector/deque directly

how do queues work?

• First In First Out

• elements are inserted at the back and deleted from the front

• may be represented using the STL container adapter, a deque, or a linked list

what are STL iterators?

• an implementation of the iterator pattern

  • provides access to elements of an aggregate object sequentially

  • does not expose underlying representation of the object

  • encapsulates internal structure of iteration

• most obvious form is a pointer (iterate through array elems via ++), but not all iterators have similar funcitonality as that of pointers

• used to iterate over a range of objects

• the interface between containers and algorithms

• central to generic programming

• algorithms take iterators as arguments

• containers provide access to elements using iterators

5 categories of iterators

weakest

• input and output

• forward

• bidirectional

• random access

strongest

input and output iterators

weakest and can only be used in single pass algorithms

input: no element accessed more than once, readonly

output: used for assigning elements, write only

forward iterators

are both input and output iterators. can only move in forward direction and only one step at a time. read and write with revisiting capabilities.

bidirectional iterators

are forward iterators, but can move in both directions

random access iterators

are bidirectional iterators. most powerful and not limited to move sequentially (most pointer-like behavior). can randomly access any element in the container by index

native types

(pointers)

can be used as iterators

iterator benefits

• convenience

• reusability

• dynamic processing of container

generic algorithms

• operate on iterators rather than containers

• containers declare iterator and const_iterators traits

• containers declare factory methods for their iterator types

• templates provide compile-time type safety

categories of generic algorithms

• non-mutating: do not change the data elements

• mutating: can change the data elements

• sorting and search: sort or search and act on ranges of elements

• numeric: mutating algorithm which produce numeric results

• specific algorithms that accept a predicate condition

benefits of STL generic algorithms

• decoupled from containers they operate on

• parameterized by iterators

• all containers with same iterator can use same algorithms

• software effort drastically reduced

• just a few versions of the search routine must be implemented

STL function objects, aka functors

• function objects are objects that can be called like functions

• they overload the function call operator ()()

• they work where functions are expected

• public access must be granted to the overloaded () operator, which must be declared and defined

• they hold state and customize behavior

lambda expressions

• compiler provided functor without the boiler plate syntax

• inline anonymous unnamed function

• simple throwaway function without the intention of reuse

• easy to read, clean

format of lambda expression

[ captures ] ( params ) specs requires (optional) { body }

• [ ] capture clause

• ( ) input parameters w/ datatypes

• { } function body