multisets 2 X96044

 14: #include <iostream>
  15: #include <vector>
  16: #include <algorithm>
  17: using namespace std;
  18:
  19: typedef vector<string> Set;
  20: typedef struct{string id; int occur;} Element;
  21: typedef vector<Element> Multiset;
  22:
  23: Set read_set(){
  24:     int n;
  25:     cin >> n;
  26:     Set s(n);
  27:     for (int i = 0; i < n; ++i) cin >> s[i];
  28:     return s;
  29: }
  30:
  31: bool empty(const Set& s){
  32:     return s.size() == 0;
  33: }
  34:
  35: void write_multiset(const Multiset& m){
  36:     int n = m.size();
  37:     for (int i=0; i < n; ++i){
  38:         cout << "(" << m[i].id << " , " << m[i].occur << ")" << endl;
  39:     }
  40: }
  41:
  42: Multiset multi_union(Multiset& m, Set& s1){
  43:     int ss1 = s1.size();
  44:     for(int set_counter = 0; set_counter < ss1; set_counter++) { //We loop through the set for the elements
  45:         int is_element_found = false; //We search if element already exists
  46:         int sm = m.size();
  47:         for(int multiset_counter = 0; multiset_counter < sm && !is_element_found; multiset_counter++) {
  48:             if(m.at(multiset_counter).id == s1.at(set_counter)) { //if it exists we increment the counter
  49:                 is_element_found = true;
  50:                 m.at(multiset_counter).occur++;
  51:             }
  52:         }
  53:         //If we couldnt find the element we push a new one
  54:         if(!is_element_found) {
  55:             Element element;
  56:             element.id = s1.at(set_counter);
  57:             element.occur = 1;
  58:             m.push_back(element);
  59:         }
  60:     }
  61:     return m; //Redundant return.
  62: }
  63: bool comp(const Element &a, const Element &b) {
  64:     return a.id < b.id; //we compare the names in ascending order
  65: }
  66: int main(){
  67:     Multiset multi_set;
  68:     Set load_set;
  69:     while(!empty((load_set = read_set()))) //We read next set
  70:         multi_union(multi_set, load_set); //We apply the function while theres sets
  71:
  72:     multi_union(multi_set, load_set); //We apply the function for the last set
  73:     std::sort(multi_set.begin(), multi_set.end(), comp); //we sort elements names with a custom function
  74:     write_multiset(multi_set); //We write the result
  75:     return 0;
  76: }