Unit 13 Containers

STL

• Standard Template Library

  • there is a large collection of them
  • we are encouraged to use them

• The data structures are usually called container classes

• KEY FEATURES

  • Containers

    • a bunch of shit inside

  • Algorithms

    • doing shit in the contaniers
    • does things that do data shit
    • has minimum requirements

  • iterators

    • gives you output but no know what he shit is in

Containers

• 4 types

  • Sequence (sequence of objects)

    • arange the data they contain in a linear manner

      • order has nothing to do with their value
      • similar to builtin arrays

    • Types

      • vector
        • resizable
        • linear
        • contiguous
      • array
        • fixed-size
        • contiguous elements
        • direct access
      • list
        • doubly linked list
        • fast insertions and removals anywhere
      • forward list
        • single linked list
        • fast insertion and romovals anywhere
      • deque
        • linear
        • not contiguous
        • fast insertion and romoval at both ends

    • (contiguous, is that the memory is beside eachother)

  • ordered associative (it will have an assisiative value)

    • The orderded associative containters are like a binary tree

    • types

      • set
      • multiset
      • map
      • multimap

  • unordered associativeines where the elements values are the keys

    • Unordered tree will also use a hash table

    • Types

      • unordered_set
        • defines the elements vaules are the keys
        • duplicates arnt allowed
      • unorderde_multiset
        • defines the elements values are the keys
        • duplicates are allowed

  • container adapter

    • Types

      • stack
        • fist in last out
      • queue
        • first in, first out
      • priority_queue
        • sam

Hash table

• What is a hash table

  • • its fast because it assigns the dataa to the keys and and find its entires

Iterators

• its like a pointer but instead it itterates and shit

  • like we can assign shit like a pointer but when we interate it becomes diffrient

• Forrward iterators

• bidirectional iterators

Big O

• Generic algorithms

  • template functions that use interators as template parameters

• worst case runningop that runs time

  • running time → always mean “worst case”
    • how do we proceeed, do we count “steps ” or “operations”

  • lets say we have a loop that truns n times, there is 6 operation per iteration

    • after n iterations, the final case iterations add a total of 3 more opterations so we have a total of 6N+3 operations.
      • this algebraic expression is called the big oh

• Big oh notation

  • we are looking for the worst case senario

    • in the example above it is O(6N+3) → it would be O(N)
      • we are only caring for the power and not the coeffient of N

  • O(1)

    • constant time
      • independent of number efo elements

  • O(n)

    • linear time

  • O(n^2)

    • quadratic time