Description

Advanced Programming in C++ – W6 Assignment

Sorting and Searching with Vectors

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 it’s 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 <iostream>

#include <string>

#include <vector>

usingnamespacestd;

template <class T>

class myVector: publicvector<T> {

public:

int seqSearch(T searchItem);

int binarySearch(T searchItem);

void bubbleSort();

void insertionSort();

};

template <class T>

intmyVector<T>::seqSearch(T searchItem)

{

//implement sequential search

}

template <class T>

voidmyVector<T>::bubbleSort()

{

//implement bubble sort

}

template <class T>

voidmyVector<T>::insertionSort()

{

//implement insertion sort

}

template <class T>

intmyVector<T>::binarySearch(T searchItem)

{

//implement binary search

}

int main()

{

//define test vector(s)

myVector<string> 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

return0;

}

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

Please pay careful attention to all assignment requirements. You are graded on your ability to implement each requirement.   

In Week 6 we begin developing with STL container classes – specifically the vector class this week. You will create your own vector class which extends (derives from) the STL vector class. Your vector adds 4 new methods as listed in the requirements document.