container

An object that allows us to collect other objects together and interact with them in some way. (vectors, stacks, queues!)
why containers?

  • organization
  • standardization
  • abstraction
    we have used the idea for structs:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    struct Student {
    string name; // these are called fields
    string state; // separate these by semicolons
    int age;
    };

    Student s;
    s.name = "Fabio";
    s.state = "FL";
    s.age = 21; // use . to access fields
    what if there are a whole class of students?
    Typically, containers export some standard, basic functionality.
  • Allow you to store multiple objects (though all of the same type)
  • Allow access to the collection through some (perhaps limited) way
    • Maybe allow iteration through all of the objects
  • May allow editing/deletion

STL containers

  • vector
  • stack
  • queue
  • set
  • map
  • array (fixed size of a vector)
  • deque (double ended queue)
  • list (DLList)
  • unordered set
  • unordered map

vector

![[Pasted image 20240612185423.png]]
additionally: why C++ is fast?

  • Only provide the checks/safety nets that are necessary
  • the programmers knows best!

implementation

keep track of a few member values:

  • size = number of elements in the vector
  • capacity = space allocated for elements

unordered maps/sets

need a hash function to be defined
faster thant ordered maps/sets(needs a comparison operator)

hashing

as mentioned in 61B

2 types of containers

sequence

anything with a inherent order
containers can be accessed sequentially

associative

  • don’t necessarily have a sequence
  • more easily searched
  • maps and sets!

how to choose containers

![[Pasted image 20240612190037.png]]
Sequence containers are for when you need to enforce some order on your information!

  • vector for most anything
  • fast inserts in the front: std::deque
  • joining/working with multiple lists: std::list (rare)

container adaptors

Container adaptors are “wrappers” to existing containers!
modify the interface to sequence containers and change what the client is allowed to do/how they can interact with the container
e.g.: wrap the queue from a deque
Why? abstraction!

iterator

similar to what have been taught in 61B
in the STL:

  • initializing –> iter = s.begin();
  • invermenting –> ++iter; (iter++ will return the previous value!)
  • dereferencing –>*iter;
  • comparing –> iter != s.end();
  • copying –>new_iter = iter;
    ![[Pasted image 20240613113558.png]]
    1
    2
    3
    4
    std::map<int, int> map{{1, 6}, {2, 8}, {0, 3}, {3,9}};
    for(auto iter = map.begin(); iter != map.end(); iter++) {
    const auto& [key, value] = *iter; // structured binding!
    }
    ![[Pasted image 20240613170004.png]]
    forward iterator:
  • Input iterators can appear on the RHS (right hand side) of an = operator like auto elem = *it;
  • output iterators can appear on the LHS like *elem = value;
    bidirectional iterator: can go backward, like --iter;
    random access iterator: directly access values without visiting all of the elements, like iter += 5;
    All iteration time in the iterator is constant!

pointer

actually, iterator is a particular type of container!
‘point’ at the particular elements in the container
Pointers are marked by the asterisk * next to the type ofthe object they’re pointing at when they’re declared.
The address of a variable can be accessed by using & before its name, same as when passing by reference!