Unit 11 Standard Library Containers and Iterators

STL

Containers

• purpose

  • containers are ways to manage a collection of objects

• Benefits

  • they provide ready made solutions for storing, accessing and managing data

• types of containers

  • Sequential Containers

    • Array

      • static, fixed size collection (fast access but no dynamic sizing)

    • Vector

      • Dynamic array that is also fast and allows easy expansion to the end of the vector

    • Deque (double-ended queue)

      • Efficient operations on both ends making it suitable for queue implementations (lines)

    • List and forward list

      • linked lists offering efficient insertions and deletions List supports bidirectional traversal, while Forward_list is singly linked

  • Ordered associative Containers:

    • Set

      • stores Unique elements in a specific order

    • Multiset

      • allows duplicate elements

    • Map

      • stores key value pairs with unique keys (useful for dictionaries and associative arrays)

    • Multimap

      • Similar to map but allows duplicate keys

  • Unordered Associative Containers:

    • unordered_set and unordered_map

      • utilize hash tables for fast retrieval

  • Container Adaptors:

    • Stack

      • Last in first out data structure, using underlying container types like (deque or vector)

    • Queue

      • First in First out structure, also uses underlying container types

    • Priority Queue:

      • similar to queue but allows retrieval based on priority

• Iterators

  • Role

    • Generalize the way collections are navigated and changed

      • similar to pointers but with more abstraction

  • Types

    • Input iterator:

      • reading elements

    • Output iterator

      • writing elements

    • forward iterator

      • single pass algorithms

    • Bidirectional iterator

      • allows both forward and backward traversal

    • Random access iterator

      • supports random access to elements from like a vector or deque

• Vector Sequence Container:

  • Operations

    • fast random acceses
    • insertions/deletions at the end are efficient but costly at other postitions

  • Functions: push_back, pop_back, insert, erase, resize.

  • Performance

    • amortized constant time complexity for appending elements

• List Sequence Container:

  • Characteristics:

    • doubly linked structure enabling fast operations at any point

  • Functions:

    • Includes push_front, push_back, insert, sort, unique.

  • Use cases

    • ideal for for frequent insertions or deletions that occur throughout the collection rather than at the end

• Deque Sequence Container:

  • Characteristics

    • Combination of features from vectors and lists

  • Efficiency

    • fast insertations and removals from both ends unlike vector

• Associative containers:

  • Use cases

    • situations where you frequently check for existence, insertions or deletions are common and order is important

  • Key functions

    • insert, find, erase, lower_bound, upper_bound.

Big O notation