Overview

• Data structures are not just for CIS 22 students :)
• Highly useful structures for day-to-day programming contexts
• Rather than constantly reinventing the wheel, many of the classical structures were robustly implemented and placed in a library -- the Standard Template Library -- STL

A Quick Tour Through the STL

• Structures capable of storing elements
• Various storage/retrival properties
  • LIFO - stack
  • FIFO - queue
  • Priority-based -
• Basic Categories
  • Sequences
    • Container whose elements are arranged in some sort of order
    • Front insertion sequence
      • Insertion at front in O(1) time
    • Back insertion sequence
      • Insertion at back in O(1) time
    • Associative Containers
      • key/value association
      • Access value by specifying key
    • Adaptors
      • Containers that use an underlying container to obtain their functionality
      Iterators
      • Need some way of moving through various containers
      • Iterators act somewhat like pointers (which can be used to move through an array) Iterators
        • Allow iteration through a container
        • forward and backward iteration
          • Requires support from the container (i.e., only certain containers allow for bckward iteration).