Write a C++ function to efficiently yield a new ordered list that is the union o

Question

Write a C++ function to efficiently yield a new ordered list that is the union of two ordered lists: template list ordered_union(const list & a, const list & b); You may assume the values in each list are unique. Write a C++ function to efficiently yield the ordered-intersection of the two lists: template list ordered_intersect(const list & a, const list & b); Write the same functions for unordered lists and compare the efficiency of your two approaches. Write your own main() function to test the correctness of the above four functions. Hand in a printout of your program and typescript of a sample run.

Explanation / Answer

#include <list>
#include <iostream>

using namespace std;

template<class T>
void printList(const list<T> &a)
{
    typename list<T>::const_iterator citer;
    citer = a.begin();
    while(citer != a.end()){
        cout << *citer << " ";
        citer++;
    }
    cout << endl << endl;
}// printList

template <class T>
list<T> ordered_union(const list<T> &a, const list<T> &b)
{
    typename list<T>::const_iterator Iter1,Iter2;
    list<T> temp;

    if (a.empty())
        return b;
    if (b.empty())
        return a;

    Iter1 = a.begin();
    Iter2 = b.begin();

    while (Iter1 != a.end() && Iter2 != b.end()) {
        if ((*Iter1) < (*Iter2)) {
           temp.push_back(*Iter1);
           Iter1++;
        }  
        else if ((*Iter1) > (*Iter2)) {
           temp.push_back(*Iter2);
           Iter2++;
        }
        else {
            temp.push_back(*Iter1);
            Iter1++;
            Iter2++;
        }
        if(Iter2 == b.end()){
            temp.push_back(*Iter1);
            Iter1++;
        }
        else if (Iter1 == a.end()) {
            temp.push_back(*Iter2);
            Iter2++;
        }
    }
    return temp;
}//ordered_union

template<class T>
list<T> ordered_intersect(const list<T> &a, const list<T> &b)
{
    typename list<T>::const_iterator Iter1,Iter2;
    list<T> temp;

    Iter1 = a.begin();
    Iter2 = b.begin();

    while (Iter1 != a.end() && Iter2 != b.end()) {
        if ((*Iter1) == (*Iter2)) {
            temp.push_back(*Iter2);
            Iter1++;
            Iter2++;
        }
        else if ((*Iter1) > (*Iter2))
            Iter2++;
        else if ((*Iter2) > (*Iter1))
            Iter1++;
      
    }
    return temp;
}//ordered_intersect

template<class T>
list<T> unordered_union(const list<T> &a, const list<T> &b)
{
    list<T> temp1 = a;
    list<T> temp2 = b;
    list<T> temp;

    if (a.empty())
        return b;
    if (b.empty())
        return a;

    temp1.sort();
    temp2.sort();

    temp = ordered_union(temp1,temp2);

    return temp;
}//unordered_union

template<class T>
list<T> unordered_intersection(const list<T> &a, const list<T> &b)
{
    list<T> temp1 = a;
    list<T> temp2 = b;
    list<T> temp;

    temp1.sort();
    temp2.sort();
    temp = ordered_intersect(temp1,temp2);

    return temp;

}//unordered_intersection

int main()
{
    list<int> l,m,t,z;

    l.push_back(1);
    l.push_back(92);
    l.push_back(28);
    l.push_back(16);
    l.push_back(54);
    l.push_back(91);
    l.sort();

    m.push_back(12);
    m.push_back(1);
    m.push_back(2);
    m.push_back(13);
    m.push_back(9);
    m.push_back(91);
    m.sort();
    cout<< "first list:" << endl;
    printList(l);

    cout<< "Second list:" << endl;
    printList(m);

    t = ordered_union(l,m);
    z = ordered_intersect(l,m);

    cout << "Ordered Union: " << endl;
    printList(t);

    cout << "Ordered intersect: " << endl;
    printList(z);

    list<int> a,b,c,d;
    a.push_back(82);
    a.push_back(8);
    a.push_back(2);
    a.push_back(90);
    a.push_back(45);
    a.push_back(1);
    a.push_back(6);
    cout << "Third list: " << endl;
    printList(a);

    b.push_back(88);
    b.push_back(1);
    b.push_back(6);
    b.push_back(77);
    b.push_back(2);
    b.push_back(45);
    b.push_back(12);
    b.push_back(120);
    cout << "Fourth list: " << endl;
    printList(b);
    c = unordered_union(a,b);
    d = unordered_intersection(a,b);

    cout << "Unordered union:" << endl;
    printList(c);

    cout << "Unordered intersect:" << endl;
    printList(d);
    return 0;
}//main

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.