CSCI 104 - Fall 2019 Data Structures and Design

STL

STL stands for Standard Template Library. The C++ STL is a set of classes that include common data structures like maps, sets, lists, queues, stacks and more. In this class, we've written some data structures by hand, and it's very useful to know how to do so, but in practice, you would just use STL implementations.

What are some reasons you wouldn't want to write your own data structures every time?

In addition to data structures, STL also has some pre-implemented algorithms, that do things like fill an array with zeros, or sort a vector.

Today, we're going to go into a lot of detail about maps and sets (and iterators), but there are several other STL container classes (like stacks and queues) that you'll use in this class and beyond. They are instantiated in the same way (e.g. std::stack<int> mystack;), and you can find the names of their member functions, as well as comprehensive examples of how to use them at C++ Reference.

STL Maps

As you know, maps are data structures that contain key-value pairs of items, where each key is unique. In the STL map, the following operations are all logarithmic: search, removal and insertion. This may be surprising — shouldn't we have to look at all the elements to see if a key is present (which would make the runtime linear)? You'll learn later in the semester how the STL map achieves this logarithimic runtime, but for now, just remember that these operations are O(log(n)).

Iterators

What if we do need to look through every item in our map? We could do n searches, but then we would need to know all the keys ahead of time. And even if we did have all the keys, our runtime would be nlog(n). Can we iterate through every element in linear time if we don't have all the keys?

Yes! We use an iterator. If we want to loop through every element, our code will look something like this: 

std::map<std::string, std::string>::iterator it;
for(it = myMap.begin(); it != myMap.end(); ++it)   
{
  std::cout << it->first << std::endl;
  std::cout << it->second << std::endl;
}

This for loop will take linear time.

Note that this isn't too different from the for loop you'd write to iterate through an array. Instead of starting at index 0, though, we start at the first element in the map data structure by using the begin() function.

STL Iterators also overload the operator '++', which moves an iterator to the next element.

Note that our terminate condition of the for loop is it != myMap.end(). myMap.end() points past the last element in your map so that your loop stops at the last element. Conceptually, this is just like in our typical for loops that we use to iterate over lists — we stop when i == size, which is the last index of our list + 1;

Incrementing or deferencing end() will cause undefined behavior, because it's not pointing at an actual element in your map.

At this point, you don't need to know how to find the runtime of maps — just understand that maps are the best way to find key/value pairs. For now, assume that the find function is O(log(n)) — later in the semester, you'll learn how to we can reduce that O(1)!

Inserting into a Map

There are two basic ways we can insert into a map. There is insert() , which only adds the specified element if the key is not already in the map. If the key does exist, insert() does nothing.

We can also insert using the overloaded operator[] to index into the map. Unlike insert(), using operator[] will overwrite the value if the key exists.

Here's an example of both ways to insert.

myMap.insert(std::make_pair("Key", "Value")); // Inserts the pair
myMap["Key"] = "Overwrites Previous Value"; // Overwrites "Value"
myMap.insert(std::make_pair("Key", "This should do nothing")); // Does nothing, because "Key" was already in the map

Finding Elements in a Map

To find an element, we can use the find() function. This returns an iterator pointing to the key-value pair, if found. If it wasn't found, it returns a pointer to end(). For example:

std::map<std::string, std::string>::iterator it = myMap.find("Key");
if (it != myMap.end()) // we found the element
{
  std::cout << it->first << " has value " << it->second << std::endl; 
}

We can also use the operator[] to retrieve the element if the key exists. 

std::string var = myMap["Key"];

If the key does not exist, and we try to access it using [], this will insert a new element into the map with the given key.

What do you think the value would be?

We've learned that we can find elements in a map using 'myMap.find("Key")'.

Take a look at the following code snippet (which is relatively commmon, when students first start using maps). Let's say we want to return true if a certain key is in the map.

std::map<std::string, std::string>::iterator it;
for(it = myMap.begin(); it != myMap.end(); ++it)   
{
  if (it->first == "myKey") {
    return true;
  }
}

return false;

Does this code work? What is the runtime? What is the major problem with this approach? What is a better way to solve this problem?

Removing Elements in a Map

To remove a single element, we use the erase() function. This accepts an iterator or a key as a parameter.

We can remove like this:

myMap.erase (myMap.find("Key"));

find() returns an iterator pointing to the object containing "Key". There is undefined behavior if iterator is invalid (i.e. end()), so don't call erase unless you know that the key is in the set.

or, we can just do:

// This first searches for an object containing "Key", then removes it
myMap.erase ("Key");

To remove all elements, use the clear() function.

NOTE: Successfully erasing or inserting an item from a map will change the map's internal structure and therefore invalidate the iterator pointing to the removed element. In other words, we can't use an iterator that we passed into erase in order to look at the next element.

myMap.insert(std::make_pair("K1", "V1"));
myMap.insert(std::make_pair("K2", "V2"));
std::map<std::string, std::string>::iterator it = myMap.find("K1"); // it points to a valid position in myMap
myMap.erase(it);
++it; // !!! UNDEFINED BEHAVIOR !!! it is no longer valid after its element has been removed from myMap

STL Sets

The STL set class is similar to a map, but we only have keys (no values). Keys are unique, and again, we can use insert(), erase(), and find(). We can also use iterators to walk through all the elements in a set. Again, find() is logarithmic, and iterating through the set is linear. Here's a code snippet.

// insert into the set
set<string> radioStations;
radioStations.insert("KCRW");
radioStations.insert("KXSC");
string stationName = "KPWR";
radioStations.insert(stationName);

// iterating through the set
for(set<string>::iterator it=radioStations.begin(); it != radioStations.end(); ++it)
{
  // note that we don't have the concept of it->first or it->last, because there are no values, only keys
  cout << "Station: " << *it << endl;
}

stationName = "KPWR";

// find an element
if(radioStations.find(stationName) != radioStations.end()){
  cout<< stationName + " is a radio station!" << endl;
}
else {
  cout<< "Couldn't find this station!" << endl;
}

radioStations.erase("KCRW"); // remove KCRW from the set of names
// if we try to find "KCRW" now, find() will return radioStations.end()

Assignment

Thank you for all your feedback in last week's lab!

A lot of you indicated that you wanted more interview-style coding problems, and some people mentioned that they preferred to write their own code from scratch rather than using skeleton code that they needed to modify.

The check off portion of this lab will be that style of independent coding problems with just a function signature. However, in general, we will still have skeleton code in lab 1) to save time, and 2) because it's a useful skill to be able to understand someone's else code, and you'll likely be working in an existing code base in your internships and jobs (and even in classes at USC, like Operating Systems).

That being said, here are three fun problems to work on! Use STL, and think carefully about which data structure makes the most sense for the problem. Complete all three for checkoff.

As usual, you can find more details about the problems in the header files.

You may have to use an STL class that was not explicity discussed in lab (e.g. not map or set)!

For this lab, and in general, remember that C++ Reference is a great website for examples of how to use STL. You can search for something like "C++ stl stack push", to find a page like this.

Good luck!