A sorted list for any type – OOP in C++ Practice

Write one container and use it for numbers and for words.

What to build

A class template SortedList<T> that keeps distinct items in increasing order.

Requirements

Write add, which ignores an item already present, contains, and print.
Use only < and == on the items, so that any type with those operators works.
Use a SortedList<int> and a SortedList<string> in the same program.

Input

n, then n whole numbers. Then m, then m words. Then q, then q lines, each int X or word W.

Output

The sorted numbers on one line, the sorted words on the next, then yes or no for each question.

Constraints

1 ≤ n, m ≤ 200 and 1 ≤ q ≤ 100. Words are single words, and capital letters sort before small ones.

Example

Input:

5
3 1 3 2 9
3
pear apple pear
3
int 3
int 4
word pear

Output:

1 2 3 9
apple pear
yes
no
yes

Why it works

The list's code never mentions int or string. The compiler makes one version for each type, and both work because both types support < and ==.

Examples

Example 1 · Input

5
3 1 3 2 9
3
pear apple pear
3
int 3
int 4
word pear

Expected output

1 2 3 9
apple pear
yes
no
yes

Example 2 · Input

1
7
1
z
1
word a

Expected output

7
z
no

Hints

Hint 1

Write `template <typename T> class SortedList` that keeps its items in a `vector<T>`, always in increasing order.

Hint 2

To add, find the first item that is not smaller than the new one. If it is equal, ignore the new one. Otherwise insert it there.

Hint 3

`contains` can use binary search, because the items are sorted.

Solution

Show one correct solution (try it yourself first)

#include <iostream>
#include <string>
#include <vector>
using namespace std;

template <typename T>
class SortedList {
    vector<T> items;
    int firstNotSmaller(const T& x) const {
        int lo = 0, hi = items.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (items[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
public:
    void add(const T& x) {
        int i = firstNotSmaller(x);
        if (i < (int)items.size() && items[i] == x) return;
        items.push_back(x);
        for (int j = (int)items.size() - 1; j > i; j--) items[j] = items[j - 1];
        items[i] = x;
    }
    bool contains(const T& x) const {
        int i = firstNotSmaller(x);
        return i < (int)items.size() && items[i] == x;
    }
    void print() const {
        for (size_t i = 0; i < items.size(); i++) {
            if (i > 0) cout << " ";
            cout << items[i];
        }
        cout << endl;
    }
};

int main() {
    int n, m, q;
    SortedList<int> numbers;
    SortedList<string> words;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        numbers.add(x);
    }
    cin >> m;
    for (int i = 0; i < m; i++) {
        string w;
        cin >> w;
        words.add(w);
    }
    numbers.print();
    words.print();
    cin >> q;
    while (q-- > 0) {
        string kind;
        cin >> kind;
        bool found;
        if (kind == "int") {
            int x;
            cin >> x;
            found = numbers.contains(x);
        } else {
            string w;
            cin >> w;
            found = words.contains(w);
        }
        cout << (found ? "yes" : "no") << endl;
    }
    return 0;
}

Lesson: Templates →