COMP5421 Assignment 5-Algorithms, Iterators, Containers Solved

1 Purpose

• •

Familiar with standard sequence containers,12 we are now ready to also become familiar with std::multimap<>, one of the standard associative3 containers (sets and maps).4

The primary purpose is to practice using a few of the Standard Template Library (STL) algorithms, iterators, and containers, enough to get a feel for how to connect algorithms to containers with the help of iterators.

Setting the Stage For Tasks 1-5

Algorithms

Iterators

Containers

2

To quickly get you to practice few standard algorithms on associative containers, this section provides some “boilerplate” code that you are already familiar with.

2.1 Input: Dog Records in a CSV File

Tasks 1-4 in this section each use a comma-separated values (CSV) input file named dogDB.csv whose contents are shown below. Each line in the file records four comma-separated strings of characters representing the name, breed, age, and gender of a dog, in that order.

1such as std::array<>, std::vector<>, std::list<> and std::forward list<> 2A sequence container provides access based on the position of an element in the sequence.
3An associative container provides access to the elements based on a key.
4The Standard Library offers two categories of associative containers:

– Ordered associative containers are usually implemented as Self-balancing binary search trees. std::set<>, std::multiset<>, std::map<>, and std::multimap<>

– Unordered associative containers are implemented as hash tables.
std::unordered set<>, std::unordered multiset<>, std::unordered map<>, and std::unordered multimap<>

1

2.2 Representation: Class Dog

The following class Dog provides a minimal representation of a dog record:

1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

2

1 2 3 4 5 6 7 8

9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

30 31 32 33 34 35 36

2.3.1

On your to-do list

2.3

Implementation: Class Dog

Without using explicit loops (for, while, do-while), implement the following trim function to remove whitespace from both ends of a given string str. Hint: use find members of std::string.

3

2.4 Storage for Dog Records
2.4.1 Requirements
In this assignment, we are interested in a container that

􏰀 keeps the elements sorted according to a given comparison object, and

􏰀 provides faster than O(n) time for element lookup.
Since the elements in sequence containers are indexed by position, the best they can offer is

O(n) and O(n log n) time for searching and sorting a sequence, respectively.

To do better, we need a container that allows indexing the dog records by a dog’s key attribute such as breed; that is, a container that models a dictionary structure, where key is breed and the associated values are dog records.

Specifically, we need a dictionary container that allows multiple dog records to share the same breed, such as Bull Terrier which appears in two of the records listed in the sample input file shown in 2.1.

Mapping keys to their corresponding values, a dictionary can provide O(log n) operations (lookup/in- sertion/removal), while keeping the elements ordered based on some policy.

2.4.2 Representation: DogMap

A clear choice of a container from the C++ STL that satisfies the requirements above is a std:: multimap<Key,T> whose elements are of the type std::pair<Key, T>, where Key represents the key type and T represents the mapped type.

We choose std::multimap<Key,T> rather than std::map<Key,T> because dogDB.csv may contain multiple dog records with the same key (breed).

Here is how to insert a Dog object into a DogMap object:

4

2.5

1
2
3
4
5
6
7 8} 9

Loading a DogMap Object From a CSV File

throw std::runtime_error("Could not open file " + cvsfilename);

10 11 12 13 14 15 16 17 18

   std::string line;
   while (std::getline(my_file_stream, line)) {        // read a line

      std::stringstream my_line_stream(line); // turn the line into a string stream
      Dog dog{};                // create a Dog object, and
      my_line_stream >> dog;    // initialize it using Dog’s extraction operator>>
      dog_map.emplace(dog.getBreed(), dog); // insert dog into dog_map

}

   my_file_stream.close(); // close the file stream
}

2.6 Your Tasks

The tasks in this section are independent. Each task starts by asking you to create a new Project initialized with your Task 1 project code; this approach is intended to minimize the potential for introducing conflicting features within the same project.

To facilitate grading, however, please combine some or all of the tasks into a single project as much as possible. Include and submit any remaining code, if any, in a plain dogMapExtra.cpp file, itemizing its contents in your README file.

5

2.6.1 Task 1

Create a project named Task 1.
1. Include the code segment from sections 2.2, 2.3, and 2.5. 2. Implement the trim method as specified on page 3, and 3. Test drive your code as follows:

1. 1  using DogMap = std::multimap<std::string, Dog>;
2. 2  int main()

3{ 4

5 6 7 8 9

10 11

1 2 3 4 5 6 7 8 9

DogMap dogMap{};
string filename{ R"(C:\Users\msi\CPP\Dogs\dogDB.csv)" }; // adjust file path according

// to your file directory

2.6.2

Output of project Task 1

6

2.6.3

1. 2.

Task 2

Create a Task 2 project, initializing it with your Task 1 header/implementation files.

Make a copy of the load DogMap function and rename it load DogMap Using For Each.

Then replace the explicit while loop in that function using the for each algorithm.

There is only one version of std::for each, which to be set up according to the comments in the code below:

template <class InputIterator, class Function>
   Function for_each (

      InputIterator first, // input iterator to the initial Dog object
      InputIterator last,  // input iterator to the final Dog object
      Function fn); // Implement fn as a lambda that takes a Dog as parameter,

                    // captures the destination multimap by reference, and

Specifically, complete the code below by filling out the blank after line 14 and before return.

// then creates and inserts an element of type
// std::pair<std::string, Dog> into the multimap

1
2 3{ 4
5
6
7
8
9

10 11 12 13 14 15 16 17 18 19

3.

std::ifstream input_file_stream(cvsfilename); // Create an input file stream

if (!input_file_stream.is_open()) {        // Check that the file is open
   cout << "Could not open file " + cvsfilename << endl;
   throw std::runtime_error("Could not open file " + cvsfilename);

using DogMap = std::multimap<std::string, Dog>;
void load_DogMap_Using_For_Each(DogMap& dog_map, std::string cvsfilename)

Replace the main() function as follows an then run Task 2:

7

5 6 7 8 9

10 11

10 11 12 13 14 15 16 17 18

DogMap dogMap{};
string filename{ R"(C:\Users\msi\CPP\Dogs\dogDB.csv)" }; // adjust file path according

1 using DogMap = std::multimap<std::string, Dog>; 2 int main()
3{
4

// to your file directory

2.6.4

Output of project Task 2

8

2.6.5 Task 3

1. Create a Task 3 project, initializing it with your Task 1 header/implementation files.
2. Make a copy of the load DogMap function, renaming it load DogMap Using Transform.

   Then replace the explicit while loop in that function using the transform algorithm.
   Use the version of std::transform that takes a unary operation, which to be set up

   according to the comments in the code below:

        template <class InputIterator, class OutputIterator, class UnaryOperation>
        OutputIterator transform (
   

           InputIterator first1,  // input iterator to the initial Dog object
           InputIterator last1,   // input iterator to the final Dog object
           OutputIterator result, // output iterator into a DogMap, wrapped in an inserter
   

                                  // for example: std::inserter(dog_map, dog_map.begin())
   

   Specifically, following the comments above, complete the code below by filling out the blank after line 14 and before return.

1. 1  using DogMap = std::multimap<std::string, Dog>;
2. 2  void load_DogMap_Using_Transform(DogMap& dog_map, std::string cvsfilename)

3{ 4
5
6
7
8
9

10 11 12 13 14 15 16 17 18 19

3.

std::ifstream input_file_stream(cvsfilename); // Create an input file stream

Replace the main() function as follows an then run Task 3:

9

12 13 14 15 16 17 18 19 20 21

19 20 21 22 23 24 25 26 27

int main() {

   std::multimap<std::string, Dog> dogMap{};
   string filename{ R"(C:\Users\msi\CPP\Dogs\dogDB.csv)" }; // adjust file path according

   load_DogMap_Using_Transform(dogMap, filename);
   cout << dogMap << "==========" << endl;

2.6.6 Output of project Task 3

// to your file directory

10

2.6.7 Task 4

The std::multimap class template is prototyped as follows:

template < class Key,
           class T,

           class Compare = less<Key>,
           class Alloc = allocator<pair<const Key,T> >
           > class multimap;

// multimap::key_type

// multimap::mapped_type
// multimap::key_compare
// multimap::allocator_type

As you can see, in addition to the key type Key and the mapped type T, there is also a third optional type parameter Compare for key compare and a forth optional type parameter Alloc for allocator type. Unless an application must take charge of its own storage management, the supplied default allocator type is most often the best choice.

However, sometimes you want to supply another Compare type instead of accepting the default std::less<Key>.

1. Create a Task 4 project, initializing it with your Task 1 header/implementation files.
2. By default, the standard library uses the operator< for the key type (std::string) to compare the keys (breeds). In this project, let us use std::string’s operator> to compare the keys (breeds) in our dog map.

   In this entire Task 4 project, replace

   with

3. Run Task 4.

2.6.8 Output of project Task 4

using DogMap =
     std::multimap<std::string, Dog>;

using DogMapReversed =
      std::multimap<std::string, Dog, std::greater<std::string>>;

11

2.6.9 Task 5

1. Create a Task 5 project, initializing it with your Task 1 header/implementation files.
2. Introduce the following function into your project and then complete it:

The function takes a DogMap and a std::string as parameters and returns a DogMap that contains all Dog objects in source having the same key breed. Hint: use equal range

3. Replace your main() with this:

      std::multimap<std::string, Dog> dogMap{};
      string filename{ R"(C:\Users\msi\CPP\Dogs\dogDB2.csv)" }; // adjust file path according

int main() {

load_DogMap(dogMap, filename);
//cout << dogMap << "==========" << endl;

// to your file directory

12

4. Replace the input file with dogDB2.csv:

5. Run your Task 5 project. 2.6.10 Output of project Task 5

13

3 Task 6: Palindromes and No Explicit Loops

Recall that a palindrome is a word or phrase that reads the same when read forward or backward, such as “Was it a car or a cat I saw?”. The reading process ignores spaces, punctuation, and capitalization.

Write a function named isPalindrome that receives a string as the only parameter and deter- mines whether that string is a palindrome.

Your implementation may not use

• any form of loops explicitly; that is, no for, while or do/while loops
• more than one local string variable
• raw arrays, STL container classes

3.1 A Suggestion

1. use std::remove copy if to move only alphabet characters from phrase to temp;
   • 􏰀  Take into account that temp is initially empty, forcing the need for an inserter

     iterator!

   • 􏰀  As the last argument to std::remove copy if, pass a unary predicate, a regular free function, called, say, is alphabetic, that takes a char ch as its only parameter and determines whether ch is an alphabetic character.
2. To allow case insensitive comparison of characters in temp, convert all the characters in it to the same letter-case, either uppercase or lowercase.

   􏰀 To do this use the std::transform algorithm, passing temp as both the source and the destination streams, effectively overwriting temp during the transformation process.

   – Use a lambda as the last argument to transform, defining a function that takes a char ch as its only parameter and returns ch in the selected letter-case.

3. use std::equal to compare the first half of temp with its second half, moving forward in the first half starting at temp.begin() and moving backward in the second half starting at temp.rbegin().

   􏰀 Set result to the value returned from the call to std::equal; 􏰀 return result

3.2 Driver Function

Use the following function to test your isPalindrome function:

14

1 2 3 4 5 6 7 8 9

10

15

4 Task 7: Searching for Second Max

Write a function template named second max to find the second largest element in a container within a given range [start, finish), where start and finish are iterators that provide properties of forward iterators.

Your function template should be prototyped as follows, and may not use STL algorithms or containers.

Clearly, in the case where the iterator range [start, finish) contains at least two distinct objects, second max should return an iterator to the second largest object. However, what should second max return if the iterator range [start, finish) is empty or contains objects which are all equal to one another? How should it convey all that information back to the caller?

Mimicking std::set’s insert member function, your second max function should return a std::pair<Iterator,bool> defined as follows:

condition

R is empty
R contains all equal elements
R contains at least two distinct elements

the value to return

std::make pair (finish,false) std::make pair (start,false) std::make pair (iter,true)

R is the range [start, finish),
iter is an Iterator referring to the 2nd largest element in the range.

4.1 Driver Function

Use the following function to test your second max function:

16

17

5 Task 8: Counting Strings of Equal lengths

Write three wrapper functions with the same return type and parameter lists.

1 int count_using_xxx (const std::vector<std::string>& vec, int n);

where xxx is either lamda, free func, or functor (function object).
Each function must return the number of elements in the vec that are of length n. For example, suppose

Then, for example, the call to any of your wrapper functions with the arguments (vec, 1), (vec, 2), (vec, 3), and (vec, 4), should return 6, 4, 3, and 0, respectively.

Your wrapper functions must each use the count if algorithm from <algorithm>.
// Returns the number of elements in the range [first,last) for which pred is true.

You should implement three versions of the unary predicate, with each version taking a std::string as their only parameter and returning whether or not that std::string is of length n:

version 1: Uses a lambda expression named Lambda that napture n by value in the lambda introducer

2 int count_using_lambda (const std::vector<std::string>& vec, int n); version 2: Uses a free function bool FreeFun(std::string, int) and then turn it into a

“unary” function by fixing its 2nd argument to n using std::bind.
3 int count_using_Free_Func(const std::vector<std::string>& vec, int n);

version 3: Uses a functor (function object) named that stores n at construction.
4 int count_using_Functor(const std::vector<std::string>& vec, int n);

5.1 Driver Function

std::vector<std::string> vec { "C", "BB", "A", "CC", "A", "B",
                               "BB", "A", "D", "CC", "DDD", "AAA", "CCC" };

18

19

6 Task 9: Sorting Strings on length and Value

Consider the following function that defines a multiset object using std::multiset’s default compare type parameter, which is std::less<T>:

1 2 3 4 5 6 7 8 9

10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

When called, the function produces the following output:

A A A AAA B BB BB C CC CC D DDD

Renaming the function multisetUsingMyComparator(), modify the declaration on line 3 so that it produces an output like this:

A A A B C D BB BB CC CC AAA DDD

The effect is that the string elements in strSet are now ordered into groups of strings of increasing lengths 1, 2, 3, …, with the strings in each group sorted lexicographically.

20

7 Test Driver Function For Tasks 6-9

file

21

8 Deliverables
Implementation files: test driver 6789.cpp and the .cpp and .h file from Section 2

(that is, those in 2.6.1, 2.6.3, 2.6.5, 2.6.7, and 2.6.9) README.txt A text file, as described in the course outline.