C++ Data structure

Maps in C++

The standard template library (STL) has implementations of several data structures that we’ve studied in this course. A common operation in software is the fetching of a key, value pair, which “maps” a key to a value. For example, “find the definition for a given dictionary word” or “find the student record associated with this student ID.”.

For fast lookups by key, one of the most useful templates is std::map, which uses a search tree to store associations between a key and a value. An overview of std::map (and another similar container, set) can be found on pages 704-706 of the textbook. All lookups are done with a key.

CSV Files

CSV (comma-separated values) is one of the most common layouts for storing data on disk. Each line contains a series of values delimited by a comma (,), with an optional line of header labels as the first line. In this way the file consists of “rows” (each line) and “columns” (data items on each line). For example, if a file has three columns, there would be three comma-separated values on each line, with an optional header line appearing on line 1.

One of the advantages of this format is that it’s plain-text and can be processed using one of several methods. As a starting point, you can use the below function, parse_line(), to return a vector of the values in each row in the file. The vector then contains the columns so you can refer to each column by its index. For example, row[0] would contain the Customer ID and row[18] would contain the MonthlyCharges value for that customer.

#include
#include
using namespace std;

void parse_line(const string &str,
vector &row) {
istringstream istr(str);
string tmp;
while (getline(istr, tmp, ‘,’)) {
row.push_back(tmp);
}
}
A CSV file is posted in this module (customers.csv) containing an anonymized list of customers from a telecom provider.

Assignment

Using the STL map template, read this file and build a map of (customer ID, monthly charges) for each entry. Your program should then do the following:

Prompt the user to enter a range of two key values. These values would refer to the “first” column in the file, which are the customer IDs. Use the lower key as the lower bound of the range, and the higher key as the higher bound (you can compare string keys just as you would numeric keys, by using “a > b”, etc.).
Output the records that fall in the range (inclusive) and their monthly charges. Use the MonthlyCharges field from the file here.
If a user enters an upper or lowercase X, quit the loop and exit the program (be sure to explain this in the prompt).
Also be sure to output the charges formatted as currency (i.e. fixed point, two decimal digits precision, and prefixed with the ‘$’ sign).
To do this efficiently, you will need to make use of the std::map::lower_bound and std::map::upper_bound methods in the map container (these are also described in pp. 704-708 of the book as well as in the STL documentation, found easily in Google). This requires the use of iterators, which you may not have learned prior to this point. Here is some sample code that would iterate through an entire map() and print the contents — this code also shows how to insert items into the map. Items consist of pairs, which are a simple 2-element data structure representing a (key, value) pair.

#include
#include

using namespace std;

int main() {
map things;

things.insert(make_pair(“dog”, “leash”));
things.insert(make_pair(“car”, “key”));
things.insert(make_pair(“rain”, “umbrella”));

map::iterator item = things.begin();
map::iterator end = things.end();

for (; item != end; ++item)
cout << item->first << endl; } What to Submit Submit your .cpp file. Your code must implement the solution using the map template in the STL. Example Run Enter the lower and upper values of the range (X to quit): 1095-WGNGG 1098-KFQEC The customers in this range are: 1095-WGNGG: $101.05 1096-ADRUX: $74.25 1097-FSPVW: $54.55 1098-KFQEC: $19.40 Enter the lower and upper values of the range (X to quit): X Exiting..