给定两个已排序的表L1和L2,求交集和并集

 交集

template<typename Object>
list<Object> intersection(const list<Object> &A,const list<Object> &B){
    list<Object> intersect;
    typename list<Object>::const_iterator iterA = A.begin();
    typename list<Object>::const_iterator iterB = B.begin();
    while(iterA!=A.end() && iterB!=B.end()){
        if(*iterA == *iterB){
            intersect.push_back(*iterA);
            iterA++;
            iterB++;
        }else if(*iterA < *iterB){
            iterA++;
        }else
            iterB++;
    }
    return intersect;
}

并集

template <typename Object>
list<Object> listUnion(const list<Object> &A,const list<Object> &B){
    list<Object> unionResult;
    typename list<Object>::const_iterator iterA = A.begin();
    typename list<Object>::const_iterator iterB = B.begin();
    while(iterA != A.end() || iterB != B.end()){
        if(iterA==A.end() && iterB != B.end()){
            unionResult.push_back(*iterB);
            iterB++;
        }else if(iterA != A.end() && iterB==B.end()){
            unionResult.push_back(*iterA);
            iterA++;
        }else if (*iterA == *iterB){
            unionResult.push_back(*iterA);
            iterA++;
            iterB++;
        }else if (*iterA < *iterB){
            unionResult.push_back(*iterA);
            iterA++;
        }else if (*iterA > *iterB){
            unionResult.push_back(*iterB);
            iterB++;
        }
    }
    return unionResult;
}

使用标准库的函数实现

template <typename Object>
list<Object> intersection1(const list<Object> &A,const list<Object> &B){
    list<Object> result;
    typename list<Object>::const_iterator iterA = A.begin();
    for(iterA = A.begin();iterA!=A.end();iterA++){
        for(auto & b:B)
            if(b == *iterA)
                result.push_back(b);
    }

    result.sort();
    result.unique();

    return result;
}

template <typename Object>
list<Object> listUnion1(const list<Object> &A,const list<Object> &B){
//    list<Object> result;
//    for(auto &a:A)
//        result.push_back(a);
//    for(auto &b:B)
//        result.push_back(b);

    list<Object> result = A,tmp = B;
    result.sort();
    tmp.sort();
    result.merge(tmp);
    result.unique();

    return result;
}

运行

    list<int> A = {2,3,5,6};
    list<int> B = {3,4,6,8,10,23,40,67};

    list<string> A1 ={"a","ab","abc","efgh","hello"};
    list<string> B1 ={"ab","helloworld"};

    list<int> C = intersection(A,B); //3 6
    list<int> D = listUnion(A,B); // 2 3 4 5 6 8 10 23 40 67
    list<string> C1 = intersection(A1,B1); // ab
    list<string> D1 = listUnion(A1,B1); //a ab abc efgh hello helloworld
    list<int> C3 = intersection1(A,B);
    list<int> D3 = listUnion1(A,B);
    list<string> C4 = intersection1(A1,B1);
    list<string> D4 = listUnion1(A1,B1);