CIS 29 - Notes for Tuesday, 2/23

Announcements and Reminders
Recording

Standard Template Library

The STL consists of
  • containers (in the form of class templates),
  • iterators - to be used "like" pointers in a container
  • function objects (or functors) - A class object that can act like a function.
  • algorithms - functions applied to containers.

Containers

Types of containers

Sequential A sequential container is one in which elements are accessed sequentially.  That access is usually performed using an iterator.
Sorted Associative An associative container is one in which elements are accessed using a key.
Adaptors Adaptors are adaptations of specific sequential containers for specific purposes.
Unsorted Associative Unsorted associative containers are implemented using hashing algorithms.

Container Type Purpose
array sequential A C-style fixed size replacement
vector sequential All-purpose, variable size
list sequential Linked-list, double ended
forward_list sequential Linked-list, single ended
deque sequential Like a vector with access at ends
queue Adapter Implements FIFO
priority_queue Adapter Implements FIFO with priority
stack Adapter Implements LIFO
set Sorted associative Similar to mathematical set
multi_set Sorted associative A set with duplicate values
map Sorted associative Key-value pairs
multimap Sorted associative Key-value pairs with duplicate keys
unordered_set Unsorted associative set implemented as hash table
unordered_multiset Unsorted associative Multiset implemented as hash table
unordered_map Unsorted associative map implemented as hash table
unordered_multimap Unsorted associative multimap implemented as hash table
bitset N/A Bit manipulators replacement

References for the STL

www.cplusplus.com

en.cppreference.com

Joe's Notes

The array container

  • Replacement for fixed-size C style array
  • Introduced in C++11
  • Requires <array> header file
  • Uses only the default constructor (template style)
Example 15-1 - the array container

The vector container

  • Replacement for an array
  • Variable size
  • Most commonly used container
  • Insert/delete anywhere in the vector, but most efficiently at the end
  • Iterators used to traverse a vector
  • Has an index operator
  • Requires the <vector> header file
Example 15-2 - the vector container

The list container

  • Double-ended linked list
  • Relatively efficient insert and delete operations
  • No index operator
  • Requires the <list> header file
Example 15-3 - the list container