Question

In C++ write an implementation of the ADT sorted list that uses a resizable array (vector class of C++ STL) to represent the list items.

Answer 1

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

Note: for the ease of submission, everything is written inside a single file, which can be separated into multiple files easily.

#include <iostream>

#include <vector>

using namespace std;

//template class representing a sorted list

template <class T>

class SortedList {

                //using a vector of type T as underlying data structure

    vector<T> vec;

public:

    SortedList() {}

    //method to add a value in proper position so that elements will be in sorted order

    void add(T value);

    //method to get an element at given position

    T get(int index) const;

    //method to remove an item from given position

    T remove(int index);

    //returns the current size of the list

    int size() const;

    //overloaded friend << operator function to display elements of the list

    template <class T1>

    friend ostream& operator<<(ostream& out, const SortedList<T1>& sortedVec);

};

//implementation of all methods declared inside the class

template <class T>

void SortedList<T>::add(T value)

{

    //if vector is empty, simply adding

    if (vec.empty()) {

        vec.push_back(value);

        //exiting function

        return;

    }

    //if value is less than first element, adding as first element

    if (value < vec[0]) {

        vec.insert(vec.begin(), value);

        return;

    }

    //otherwise, looping through each pair and checking if value can be added

    //to the middle of any pair

    for (int i = 0; i < vec.size() - 1; i++) {

        if (value >= vec[i] && value <= vec[i + 1]) {

            //adding number between current vec[i] and vec[i+1]

            vec.insert(vec.begin() + i + 1, value);

            return;

        }

    }

    //otherwise, adding as last value

    vec.push_back(value);

}

template <class T>

T SortedList<T>::get(int index) const

{

                //assuming index is valid, returning element at given index

    return vec[index];

}

template <class T>

T SortedList<T>::remove(int index)

{              //assuming index is valid, fetching element at given index

    T element = vec[index];

    //removing element at index position

    vec.erase(vec.begin() + index);

    //returning removed value

    return element;

}

template <class T>

int SortedList<T>::size() const

{

                //returning size of vector

    return vec.size();

}

template <typename E>

ostream& operator<<(ostream& out, const SortedList<E>& list)

{

    //looping and printing all values in list space separated

    for (int i = 0; i < list.size(); i++) {

        out << list.vec[i] << " ";

    }

    return out;

}

int main()

{

                //creating a SortedList of integers, adding some values, displaying list

    SortedList<int> list1;

    list1.add(15);

    list1.add(7);

    list1.add(-2);

    list1.add(99);

    list1.add(76);

    cout << "Sorted integer list: " << list1 << endl;

                //creating a SortedList of characters, adding some values, displaying list

    SortedList<char> list2;

    list2.add('e');

    list2.add('a');

    list2.add('d');

    list2.add('b');

    list2.add('c');

    cout << "Sorted char list: " << list2 << endl;

   

  return 0;

}

/*OUTPUT*/

Sorted integer list: -2 7 15 76 99

Sorted char list: a b c d e