計算兩個字符串鏈表中的共同數據項，需要考慮重復選項的情況

Problem
/*
// Given two lists of strings build a new list that has all strings that appear in both the original lists. If the same string appears more than once output it as many times as it appears in both lists
//
// Example:
// "dog", "bird", "elephant", "dog", "dog", "cat"
// "cat", "dog", "dog", "cat", "cat", "fish"
// Result (order doesn't matter)
// "dog", "dog", "cat"

*/

Solution
[cpp]
#include <iostream>  
#include <list>  
#include <iterator>  
#include <algorithm>  
#include <string>  
 
using namespace std; 
 
void find_comm_strings(list<string>& output, list<string>& listA, list<string>& listB) 
{ 
    listA.sort(); 
    listB.sort(); 
 
    list<string>::const_iterator citA = listA.begin(); 
    list<string>::const_iterator citB = listB.begin(); 
 
    while(citA != listA.end() && citB != listB.end()){ 
        int eq = (*citA).compare(*citB); 
        if(eq == 0){ 
            output.push_back(*citA); 
            citA ++; 
            citB ++; 
        } 
        else if (eq > 0){ 
            citB ++; 
        } 
        else{ 
            citA ++; 
        } 
    } 
} 
 
int main(int argc, char* argv[]) 
{ 
    list<string> listA; 
    list<string> listB; 
    list<string> output; 
 
    cout << "list A:" << endl; 
    listA.push_back("dog"); 
    listA.push_back("bird"); 
    listA.push_back("elephant"); 
    listA.push_back("dog"); 
    listA.push_back("dog"); 
    listA.push_back("cat"); 
    copy(listA.begin(), listA.end(), ostream_iterator<string>(cout, ",")); 
    cout << endl; 
 
    cout << "list B:" << endl; 
    listB.push_back("cat"); 
    listB.push_back("dog"); 
    listB.push_back("dog"); 
    listB.push_back("cat"); 
    listB.push_back("cat"); 
    listB.push_back("fish"); 
    copy(listB.begin(), listB.end(), ostream_iterator<string>(cout, ",")); 
    cout << endl; 
 
    find_comm_strings(output, listA, listB); 
 
    cout << "common strings" << endl; 
    copy(output.begin(), output.end(), ostream_iterator<string>(cout, ",")); 
    cout << endl; 
 
 return 0; 
} 

#include <iostream>
#include <list>
#include <iterator>
#include <algorithm>
#include <string>

using namespace std;

void find_comm_strings(list<string>& output, list<string>& listA, list<string>& listB)
{
    listA.sort();
    listB.sort();

    list<string>::const_iterator citA = listA.begin();
    list<string>::const_iterator citB = listB.begin();

    while(citA != listA.end() && citB != listB.end()){
        int eq = (*citA).compare(*citB);
        if(eq == 0){
            output.push_back(*citA);
            citA ++;
            citB ++;
        }
        else if (eq > 0){
            citB ++;
        }
        else{
            citA ++;
        }
    }
}

int main(int argc, char* argv[])
{
    list<string> listA;
    list<string> listB;
    list<string> output;

    cout << "list A:" << endl;
    listA.push_back("dog");
    listA.push_back("bird");
    listA.push_back("elephant");
    listA.push_back("dog");
    listA.push_back("dog");
    listA.push_back("cat");
    copy(listA.begin(), listA.end(), ostream_iterator<string>(cout, ","));
    cout << endl;

    cout << "list B:" << endl;
    listB.push_back("cat");
    listB.push_back("dog");
    listB.push_back("dog");
    listB.push_back("cat");
    listB.push_back("cat");
    listB.push_back("fish");
    copy(listB.begin(), listB.end(), ostream_iterator<string>(cout, ","));
    cout << endl;

    find_comm_strings(output, listA, listB);

    cout << "common strings" << endl;
    copy(output.begin(), output.end(), ostream_iterator<string>(cout, ","));
    cout << endl;

 return 0;
}
Output
[cpp]
list A: 
dog,bird,elephant,dog,dog,cat, 
list B: 
cat,dog,dog,cat,cat,fish, 
common strings 
cat,dog,dog, 
Press any key to continue . . . 

list A:
dog,bird,elephant,dog,dog,cat,
list B:
cat,dog,dog,cat,cat,fish,
common strings
cat,dog,dog,
Press any key to continue . . .