Foundational concepts to STL

• Standard Template Library (deprecated)
• Standard Library (after C++11)

3 Concepts

• Containers, Algorithms, Iterators

Containers

• A class with some storage facility
• Store different kinds of objects
• Limitation: Only able to store copies of objects and not references directly
  • This is because references have to have a value on initialization, and arrays are new'd/malloc'd
• Typically accessible via iterators
• Iterators are classes/types that allows us to traverse the container.

Iterators

• Not always pointers, though pointers can be iterators
• Iterators are essentially objects that talk, walk and behave like pointers BUT may not be pointers.
• Different kinds of iterators (GUIDELINES)
  • All iterators are assumed to support copy-constructor, copy-assign, equal comparisons (==, !=, !).
  • InputIterator (Promise), EXAMPLE: cin
    • Only increment it
    • Only dereference it for reading
    • Must be used this way: *i++ (Consume, then advance)
  • OutputIterator (Promise), EXAMPLE: cout
    • Only increment it
    • Dereference it for writing
    • Must be used this way: *i++ (Consume, then advance)
  • Forward Iterators, EXAMPLE: singly linked list
    • Union of InputIterator/OutputIterator
    • Dereference for both reading and writing
  • Reverse Iterators, EXAMPLE: A* pathfinding nodes
    • Only decrement it
    • Dereferenced for both reading and writing
  • BiDirectional Iterators, EXAMPLE: doubly linked list
    • Supports both increment/decrement
    • Dereference for both reading and writing
  • Random Access Iterators, EXAMPLE: array, deque, vector
    • Can do whatever pointers can do.

Categories of Iterators (pg 401)

• Insert (istream)
  • A type of iterator that creates an iterator
• Stream
  • Used for file i/o
• Reverse
• Move

Vectors can be initialized with iterators!

Predicate - something that is not affected by variables other than input

Containers in STL 1. std::vector

• storing the objects in contiguous space.
• iterator returned by vector is a random access iterator
• .begin()
• .cbegin() //const iterator (aka an iterator to a const object)

2. std::list

• linked list (doubly linked list)
• BiDirectional Iterator

STUFF TO NOTE ABOUT CONTAINERS

1. Half-ranges: Iterator pointing to the first element and one past the last element.
while(begin!=end)
Containers use value not reference semantics; this means deep copy not shallow copy.

2. Elements have a specific order

3. No safety guaranteed.