Create your own vector class which will test algorithms from Chapter 16 and those from the STL (Appendix H).

Derive class myVector from vector. myVector must implement the following methods:

int seqSearch(T searchItem);

int binarySearch(T searchItem);

void bubbleSort();

void insertionSort();

Create a test program to create some vectors and test your methods above. Recall from your reading that binary search only works on a sorted list. Add a static member to the class to remember if the list is sorted ( i.e. binarySearch() should first sort the vector if its not sorted already).

Use the template below as a starter for your assignment. All comments in green represent code which you need to implement.

#include

#include

#include

using namespace std;

template

class myVector: public vector {

public:

int seqSearch(T searchItem);

int binarySearch(T searchItem);

void bubbleSort();

void insertionSort();

};

template

int myVector::seqSearch(T searchItem)

{

//implement sequential search

}

template

void myVector::bubbleSort()

{

//implement bubble sort

}

template

void myVector::insertionSort()

{

//implement insertion sort

}

template

int myVector::binarySearch(T searchItem)

{

//implement binary search

}

int main()

{

//define test vector(s)

myVector nameList;

//add values to the vector(s)

//test sort methods

//test search methods

//print sorted vector using range based for loop

//define new test vector(s)

//define an iterator to each of the above vector containers

//add values to the vector(s)

//test the STL sort method

//test the STL binary_search algorithm

//print the resulting vector(s) using an iterator

return 0;

}

Useful notes:

this->size(); //length of vector from within myVector class

this->at(index); //value at specified index of vector from within myVector class

The STL concepts are taken from Appendix H

Directions

You are to write a C++ program that meets the instruction requirements above. Use the assignment template to insert the assignment deliverables outlined above.

Deliverables

A description of your program.

Your C++ source code (do not submit screen shots).

A screenshot of your program running.

A short reflection outlining your experience developing the program.

Assignment Rubric

Grading Criteria Assignments	Maximum Points
A description of the program was not submitted, A screenshot of the program execution was not submitted, A copy of the program code was not submitted, or A reflection of your programming experience was not submitted.	1
Program accomplishes requested operations per instructions	40
The code works and meets all assignment specifications	30
The code is organized and easy to follow and output is clear and clean	20
Uses software tools correctly and efficiently	10
Total	100

vector Type (class) Note This section may be skipped without any discontinuation.

Chapter 8 and the previous sections of this chapter described how arrays can be used to implement and process lists. One of the limitations of arrays discussed so far is that once you create an array, its size remains fixed. This means that only a fixed number of elements can be stored in an array. Also, inserting an element in the array at a specific position could require the elements of the array to be shifted. Similarly, removing an element from the array could also require shifting the elements of the array, as we typically do not leave empty positions between array positions holding some data. Typically, empty array positions are at the end.

In addition to arrays, C++ provides the vector type (most commonly called the class vector) to implement a list. A variable declared using the vector type is called a vector container (or a vector, a vector object, or simply an object). Unlike an array, the size of a vector object can grow and shrink during program execution. Therefore, you do not need to be concerned with the number of data elements.

When you declare a vector object, you must specify the type of the element the vector object stores. Table 16-1 describes various ways a vector object can be declared.

Table 16-1. Various Ways to Declare and Initialize a vector Object Statement Effect vector vecList; Creates the empty vector object, vecList, without any elements. vector vecList(otherVecList); Creates the vector object, vecList, and initializes vecList to the elements of the vector otherVecList. vecList and otherVecList are of the same type. vector vecList (size); Creates the vector object, vecList, of size size. vecList is initialized using the default values. vector vecList(n, elem); Creates the vector object, vecList, of size n. vecList is initialized using n copies of the element elem. In Table 16-1, elemType specifies the data type of the element to be stored in vecList.

Example 16-2. The following statement declares intList to be an empty vector object, and the element type is int .

Details The following statement declares intList to be a vector object of size 10, and the element type is int . The elements of intList are initialized to 0.

Details Now that we know how to declare a vector object, let us discuss how to manipulate the data stored in a vector object. To do so, we must know the following basic operations:

Item insertion

Item deletion

Stepping through the elements of a vector container

The type vector provides various operations to manipulate data stored in a vector object. Each of these operations is defined in the form of a function. Table 16-2 describes some of these functions and how to use them with a vector object. (Assume that vecList is a vector object.)

Table 16-2. Operations on a vector Object Expression Effect vecList.at(index) Returns the element at the position specified by index. vecList[index] Returns the element at the position specified by index. vecList.front() Returns the first element. (Does not check whether the object is empty.) vecList.back() Returns the last element. (Does not check whether the object is empty.) vecList.capacity() Returns the total number of elements that can be currently added to vecList. vecList.clear() Deletes all elements from the object. vecList.push_back(elem) A copy of elem is inserted into vecList at the end. vecList.pop_back() Deletes the last element of vecList. vecList.empty() Returns true if the object vecList is empty, and false otherwise. vecList.size() Returns the number of elements currently in the object vecList. The value returned is an unsigned int value. vecList.max_size() Returns the maximum number of elements that can be inserted into the object vecList. Table 16-2 shows that the elements in a vector can be processed just as they are in an array. (Recall that in C++, arrays start at location 0. Similarly, the first element in a vector object is at location 0. Note that both the function at and the subscripting operator [] return the elements at the specified position. However, if the position, that is, the index, of the specified position is out of range, the function at throws an exception. Exceptions are discussed in Chapter 14.

Example 16-3. Consider the following statement, which declares intList to be a vector of size 5 and the element to be of type int :

Details You can use a loop, such as the following, to store elements into intList:

Details Similarly, you can use a for loop to output the elements of intList.

Example 16-3 uses a for loop and the array subscripting operator, [], to access the elements of intList. We declare intList to be a vector object of size 5. Does this mean that we can store only five elements in intList? The answer is no. You can, in fact, add more elements to intList. However, because when we declared intList, we specified the size to be 5, in order to add any elements past position 4, we use the function push_back.

Furthermore, if you initially declare a vector object and do not specify its size, then to add elements to the vector object, we use the function push_back. Example 16-4 explains how to use this function.

Example 16-4. The following statement declares intList to be a vector container of size 0:

Details To add elements into intList, we can use the function push_back as follows:

Details After these statements execute, the size of intList is 2 and

Details In Example 16-4, because intList is declared to be of size 0, we use the function push_back to add elements to intList. However, we can also use the resize function to increase the size of intList and then use the array subscripting operator. For example, suppose that intList is declared as in Example 16-4. Then, the following statement sets the size of intList to 10:

Details Similarly, the following statement increases the size of intList by 10:

Details However, at times, the push_back function is more convenient because it does not need to know the size of the vector; it simply adds the elements at the end.

Note The name of the header file that contains the class vector is vector. Therefore, to use the class vector, you must include the header file vector, that is, include the following statement in your program:

The program in Example 16-5 illustrates how to use a vector object in a program and how to process the elements of a vector.

Example 16-5.

Details Sample Run:

The statement in Line 6 declares the vector object (or vector for short) intList. The statement in Line 7 declares i to be an unsigned int variable. (Notice that we declare i to be an unsigned int because, in the for loop, we are using the expression intList.size(), which returns an unsigned int value, to determine the size of intList.)

The statements in Lines 8 through 11 use the operation push_back to insert four numbers24, 39, 90, and 66into intList. The statements in Lines 13 and 14 use a for loop and the array subscripting operator, [], to output the elements of intList. In the output, see the line marked Line 12, which contains the output of Lines 12 through 15 of the program. The statements in Lines 16 and 17 use a for loop to double the value of each element of intList; the statements in Lines 19 and 20 output the elements of intList. In the output, see the line marked Line 18, which contains the output of Lines 18 through 21 of the program.