---

In this lab you will write some functions that work with the C++ std::vector data type.

---

1. Teams

   You may work with a partner for this lab. You and your partner should begin thinking about the problems and begin writing the code before lab time.

2. Create a new project

   Create a new project and add the header file vectorutils.h. vectorutils.h contains the prototypes of functions that you are to implement.

3. Implement the functions

   Create a new C++ source file named vectorutils.cpp that implements all the functions declared in the vectorutils.h header file. The specifications for the functions are listed here:

   • maximum

     int maximum(const std::vector<int>& vec) { ... }
     Returns the maximum value in vector vec. The behavior of this function is undefined if the vector is empty.

     The function should not disturb the contents of the vector, and it should not use any extra memory except for a few local scalar variables.

   • find

     int find(const std::vector<int>& vec, int seek) { ... }

     Returns the location (zero is the first position) of the first occurrence of seek within vec. Said another way, it returns the lowest index in vec that contains the value seek. If seek does not appear in vec, the function should return –1, since –1 is not a legal index within any C++ vector.

     The function should not disturb the contents of the vector, and it should not use any extra memory except for a few local scalar variables.

   • count

     int count(const std::vector<int>& vec, int seek) { ... }

     Returns the number of times element seek appears in vec. The function returns zero if seek is not present in vec.

     The function should not disturb the contents of the vector, and it should not use any extra memory except for a few local scalar variables.

   • equivalent

     bool equivalent(const std::vector<int>& vec1, const std::vector<int>& vec2) { ... }

     Returns true if vectors vec1 and vec2 contain exactly the same elements, regardless of their order within the vectors; otherwise, the function returns false.

     For example, suppose we have the following three vectors:

     • The vector list1 contains, in order, 1, 2, 3, 4, 3, 5, 6.
     • The vector list2 contains, in order, 3, 2, 1, 4, 6, 5, 3.
     • The vector list3 contains, in order, 3, 2, 1, 4, 6, 5.

     The call equivalent(list1, list2) would return true, since both lists contain exactly the same elements, although not necessarily in the same order. The call equivalent(list1, list3) would return false, because even though both vectors contain the same values, list1 has two 3s while list3 has only one 3.

     Two empty vectors are considered equivalent. The function should not disturb the contents of either vector during its processing. The function should use no extra space except for a few local scalar variables.

     Returns true if vectors vec1 and vec2 contain exactly the same elements; otherwise, the function returns false. The order of the elements does not matter. If one of the vectors contains duplicate elements, the other must contain exactly the same number of duplicate elements for the function to return true.

     The function should not affect the contents of either vector, and it should not use any extra memory except for a few local scalar variables.

   • sort

     void sort(std::vector<int>& vec) { ... }

     Physically rearranges the elements of vec so they are in ascending order.

     For example, if a vector named list contains the elements 2, 1, 3, 1, 5, and 2, the call sort(list) reorders list to contain 1, 1, 2, 2, 3, 5.

     The function necessarily will affect the contents of the vector, but it should not use any extra memory except for a few local scalar variables.

   • is_ascending

     bool is_ascending(const std::vector<int>& vec) { ... }

     Returns true if all the elements in the vector appear in non-descending order (or ascending order with possible duplicates); otherwise, the function returns false.

     For example, if a vector named list contains the elements 2, 1, 3, 1, 5, and 2, the call is_ascending(list) would return false. The call is_ascending({1, 1, 2, 2, 3, 5}) would return true.

     Since an empty vector has no elements to be out of order, is_ascending on an empty vector should return true.

     The function should not disturb the contents of the vector during its processing. The function should use no extra space except for a few local scalar variables.

   • remove_first

     bool remove_first(std::vector<int>& vec, int del) { ... }

     Removes the first occurrence of the value del from the vector vec. (The first occurence is the one with the lowest index.)

     The function returns true if del was located and removed; otherwise, it returns false. The function should not disturb the relative ordering of the elements that remain.

     The function can affect the contents of the vector, but it should use no extra space except for a few local scalar variables.

     For example, if the vector originally contains

                     23, 45, 14, 45, 19, 11
                  

     after removing 45 it would contain

                     23, 14, 45, 19, 11
                  

     Notice that only the first occurrence of 45 was removed, and the order of the remaining elements with respect to each other did not change.

     (Hint: Locate the element to remove, and then shift forward by one position all the elements that follow it. Be sure to decrease the vector's size by one.)

   • remove_all

     int remove_all(std::vector<int>& vec, int del) { ... }

     Removes all occurrences of the value del from the vector vec.

     The function returns the number of elements removed; if it removes nothing because the element to remove is not found in the vector, the function returns zero. The function should not disturb the relative ordering of the elements that remain.

     The function can affect the contents of the vector, but it should use no extra space except for a few local scalar variables.

     For example, if the vector originally contains

                     23, 45, 14, 45, 19, 11
                  

     after removing 45 it would contain

                     23, 14, 19, 11
                  

     Notice that all occurrences of 45 were removed, and the order of the remaining elements with respect to each other did not change.

   • rotate

     void rotate(std::vector<int>& vec, int dist) { ... }

     Physically rearranges the elements of vector vec so that all the elements are shifted towards the back by a distance of dist. As an element "falls off" the rear of the vector during the rotation, it is placed at the front of the vector in the space vacated when the first element was shifted backwards.

     For example, if vector s originally contains the elements 1, 2, 3, 4, 5, 6, in that order, the call rotate(s, 2) would rearrange s to contain 5, 6, 1, 2, 3, 4.

     Notice that if dist is equal to the size of the vector, after the rotation all the elements rotate to their original location.

     If dist is negative, the function shifts the elements toward the front of the vector dist spots instead of backwards. As an element "falls off" the front it is placed onto the rear of the vector in the space vacated when the last element was shifted forwards.

     For example, if vector s originally contains 1, 2, 3, 4, 5, 6, in that order, the call rotate(s, -2) rearranges s to contain 3, 4, 5, 6, 1, 2. The rotation is easier to understand if you visualize the list as a circular structure as shown in the following figure:

     

     The figure shows the original vector on the left and the vector rotated by –2 on the right.

     This function necessarily can affect the contents of the vector. The function should use no extra space except for a few local scalar variables. The function should not return anything to the caller.

   • subsequence

     bool subsequence(const std::vector<int>& vec1, const std::vector<int>& vec2) { ... }

     The function returns true if vec2 is a subsequence of vec1; otherwise, the functions returns false.

     A subsequence is a sequence of elements that are part of a potentially larger sequence. Given any sequence, you can produce a subsequence by removing none, some, or all of the elements in the original sequence. The remaining elements must appear in same relative order as in the original sequence.

     The concept is best explained by some examples: If seq1 is the sequence

                    23, 4, 19, -4, 0, 3
                    

     and seq2 is the sequence

     
                    19, -4, 0
                    

     seq2 is a subsequence of seq1.

     If seq1 is the sequence

                    23, 4, 19, -4, 0, 3
                    

     and seq2 is the sequence

                    19, 0
                    

     seq2 is a subsequence of seq1.

     If seq1 is the sequence

     
                    23, 4, 19, -4, 0, 3
                    

     and seq2 is the sequence

                    19, -4, 0, 3, 5
                    

     seq2 is not a subsequence of seq1, because seq2 contains an element that does not appear in seq1.

     If seq1 is the sequence

                    23, 4, 19, -4, 0, 3
                    

     and seq2 is the sequence

     
                    23, 0, -4
                    

     seq2 is not a subsequence of seq1 even though all of its elements appear in seq1. This is because seq2's elements are not in the same relative order as in seq1 (0 comes after –4 in seq1 but before –4 in seq2.)

     If seq1 is the sequence

                    23, 4, 19, -4, 0, 3
                    

     and seq2 is the sequence

                    23, 4, 19, -4, 0, 3
                    

     seq2 is a subsequence of seq1; thus, any sequence is a subsequence of itself.

     The empty sequence is a subsequence of every sequence.

     The function should disturb neither vector seq1 nor vector seq2 during its processing. The function should use no extra space except for a few local scalar variables.

   There are library routines that offer the functionality of some of the tasks in this assignment; however, you are expected to write the code yourself using primitive loops and conditionals. This will help you better understand how vectors work.

   The specification that a function "does not affect the vector" means that the contents of the vector are unchanged by the function; the function may not reassign, rearrange, or otherwise change the elements of the vector. A caller legitimately would not expect the function to disturb the contents the vector for the functionality the function provides. Don't disappoint the caller!

   The directive to "not use any extra memory except for a few local scalar variables" means you are not to make a copy of the vector or create a new vector inside the function. This is because the caller may pass a very large vector containing millions of elements. It would be wasteful for the function to use the extra space unnecessarily.

   None of the functions specified above should do any input or output. This means that neither std::cout nor std::cin should appear in any of the functions. You are welcome to add printing statements during development for debugging purposes, but you should remove or comment out these printing statements when you are ready to submit your program for testing.

   You may not modify the contents of the vectorutils.h header file.

4. Check out

   Your finished vectorutils.cpp file will be evaluated for correctness and compliance. Before showing me your code, be sure that it complies with the following requirements:

   1. Your name and your partner's name should appear in the in a comment at the top of the source code. Failure to provide such a comment results in an immediate failed test.
   2. Ensure that your vectorutils.cpp compiles correctly with the following very simple test file. If your vectorutils.cpp file does not compile with this very simple test program, it will not compile with my test program either. If your code will not compile, it counts as a failed test. This simple test file is very minimal and is designed merely to verify that your code satisfies the compiler; it does not begin to demonstrate the correctness of your code's logic. You should write your own test code to verify your functions' correctness.

   Unlike the earlier programming assignments, your score for this assignment depends on the number of functions that pass a rigorous test suite. You will be awarded 10 points if all 10 functions pass all the tests, 9 points if one of the functions failed one or more of its tests, 8 points if two of the functions failed one or more of their tests, etc. You may provide to me your vectorutils.cpp file for testing up to two times before its due date. The final test determines the score based on the number of functions that pass the tests. After the final check you should submit your C++ source file to eclass.