Standard Library Containers

Okay. We learned about vectors a lot. They work well for many data-storage problems. But vector is not always the best choice. In lecture we learned about a lot of standard containers in c++. Today we'll go through some basic theory and examples with just a few of them.

Vector

  1. Elements are stored continuously in memory
  2. Fast:
    • Accessing elements (using indexing)
    • Adding elements to the end of the vector
    • Removing elements from the end of the vector
  3. Slow:
    • Inserting elements into the middle of the vector (preserving order)
    • Removing elements from the middle of the vector (preserving order)
    • Searching for an element in the vector (need to look at each element)

List

  1. Elements are stored all over the place in memory
  2. Fast:
    • Inserting elements anywhere in the list (preserving order)
    • Removing elements anywhere in the list (preserving order)
  3. Slow:
    • Accessing elements is slow. No indexing is available. To access the element at position 100, we need use the .begin() function to get an iterator, then use ++ 100 times.
    • Searching for an element in the list (need to look at each element)

Set

  1. Elements are stored in a tree-like structure
  2. The set is always kept sorted (using <).
  3. Elements are unique: no repeats allowed.
  4. Pretty fast (but not as fast as other examples above):
    • Inserting elements anywhere in the set (need to maintain sorting)
    • Searching for an element in the set (the sorting makes this go fast)
    • Removing elements anywhere in the set
    • Accessing elements (uses sorting to go faster)

There are more that we won't go over here

queue, map, multiset, hash table, etc. Each is useful for its own class of problems.

Example problem: Set Union

Let's say that set1 and set2 are both containers of type std::set. We want to find the "union". That is, we want to find all the elements that are in at least one of the sets (so one or the other or both).

The method is straightforward, so consider this some practice with the syntax.

setUnion.cpp

Example problem: Set Intersection

Let's say that set1 and set2 are both containers of type std::set. We want to find the "intersection". That is, we want to find all the elements that are in both sets.

The first solution we'll write up involves using a lot of the member functions from set (practicing syntax), and not thinking very hard about the algorithm. If we have time, we'll create a second solution uses the fact that sets are always sorted to run a little bit faster.

setIntersection.cpp

Example problem: Same elements in a vector

Write a function called same_elements, which inputs two vector<int>s, and outputs a bool. The function should return true if the vectors contain exactly the same elements (not necessarily in the same order), and return false otherwise. Repeated elements do not count. That is, if an element is repeated 10 times in one vector, and 3 times in another, then we still consider these vectors to have the same elements.

Examples:
same_elements([1, 2], [2, 1]) returns true
same_elements([1, 2, 3], [2, 1]) returns false
same_elements([1, 2, 1], [2, 1]) returns true
same_elements([1, 2, 1], [2, 2, 1]) returns true
same_elements([2, 9, 2, 1], [1, -4, 2, 1]) returns false
vectorSameElements.cpp

Now think about how to write a similar sameElements function using a set instead of a vector. Hint: it is very very easy. I can do it in one line.