сравнить два мультимапа С++

У меня есть две мультикарты. Я хотел бы создать новую мультикарту, которая имеет общие пары ключ-значение для этих двух мультикарт:

например:

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

int main ()
{


multimap<std::string, std::string> m;
multimap<std::string, std::string> n;


m.insert(multimap<string,string>::value_type("1-2","1-1"));
m.insert(multimap<string,string>::value_type("1-2","1-2"));
m.insert(multimap<string,string>::value_type("1-2","1-3"));
m.insert(multimap<string,string>::value_type("1-2","1-4"));
m.insert(multimap<string,string>::value_type("1-3","2-1"));
m.insert(multimap<string,string>::value_type("1-3","21-1"));
m.insert(multimap<string,string>::value_type("1-3","21-2"));

n.insert(multimap<string,string>::value_type("1-2","1-1"));
n.insert(multimap<string,string>::value_type("1-2","1-2"));
n.insert(multimap<string,string>::value_type("1-2","1-5"));
n.insert(multimap<string,string>::value_type("1-2","1-7"));
n.insert(multimap<string,string>::value_type("1-3","2-1"));
n.insert(multimap<string,string>::value_type("1-3","21-4"));
n.insert(multimap<string,string>::value_type("1-3","21-2"));

cout<<"multimap of m"<<endl;
cout<<"--------------"<<endl;
for(multimap<string,string>::iterator i=m.begin();i!=m.end();i++)
cout <<i->first<<" "<<i->second<<endl;
cout<<"multimap of n"<<endl;
cout<<"--------------"<<endl;
for(multimap<string,string>::iterator i=n.begin();i!=n.end();i++)
cout <<i->first<<" "<<i->second<<endl;

}

это приводит к:

multimap of m
--------------
1-2 1-1
1-2 1-2
1-2 1-3
1-2 1-4
1-3 2-1
1-3 21-1
1-3 21-2
multimap of n
--------------
1-2 1-1
1-2 1-2
1-2 1-5
1-2 1-7
1-3 2-1
1-3 21-4
1-3 21-2

я хочу создать новую мультикарту: которая имеет следующие элементы:

1-2 1-1
1-2 1-2
1-3 2-1
1-3 21-2

ИЗМЕНИТЬ:

также есть способ, которым я могу удалить общие элементы (пару) с обеих карт.


c++ multimap
person Vijay    schedule 19.12.2011    source источник
comment
Я выложил прямой алгоритм, который работает на мультикартах, а также делает удаление.   -  person Kerrek SB    schedule 19.12.2011

Ответы (3)


arrow_upward
2
arrow_downward

В качестве альтернативного решения для Армена (что превосходно), вот способ одновременного копирования и сортировки:

typedef std::multimap<std::string, std::string> map_type;
map_type m, n, result;

m.insert(std::make_pair("1-2", "1-1"));
// --------8<--------
n.insert(std::make_pair("1-3", "21-2"));

// --------8<--------    

std::set<map_type::value_type> s1(m.begin(), m.end());
std::set<map_type::value_type> s2(n.begin(), n.end());
std::set_intersection(s1.begin(), s1.end(), 
                      s2.begin(), s2.end(), 
                      std::inserter(result, result.end()));

Выход:

intersection
============
1-2 1-1
1-2 1-2
1-3 2-1
1-3 21-2

Чтобы получить элементы, которые есть только в m:

result.clear();
std::set_difference(s1.begin(), s1.end(), 
                    s2.begin(), s2.end(), 
                    std::inserter(result, result.end()));

И только в n:

result.clear();
std::set_difference(s2.begin(), s2.end(), 
                    s1.begin(), s1.end(), 
                    std::inserter(result, result.end()));

Посмотрите, как он работает.

Поскольку вы скопировали m и n (в s1 и s2) во время выполнения set_difference() , вы можете clear() их и вставить в них вместо result.

person Johnsyweb    schedule 19.12.2011
comment
+1: не думал о наборе. Хотя, если честно, я понятия не имею, будет ли так или иначе значительно быстрее. Пусть ОП попробует это - person Armen Tsirunyan; 19.12.2011

arrow_upward
5
arrow_downward

Используйте шаблон функции std::set_intersection из <algorithm>

std::multimap<T1, T2> newMap;
std::set_intersection(map1.begin(), map1.end(), 
                      map2.begin(), map2.end(), 
                      std::inserter(newMap, newMap.begin());

Редактировать Да, очевидно, это не работает для мультикарты, как для карты. Я предлагаю следующее:

std::multimap<T1, T2> newMap;
std::vector<std::multimap<T1, T2>::value_type> v1(map1.begin(), map1.end());
std::sort(v1.begin(), v1.end());
std::vector<std::multimap<T1, T2>::value_type> v2(map2.begin(), map2.end());
std::sort(v2.begin(), v2.end());
std::set_intersection(v1.begin(), v1.end(), 
                      v2.begin(), v2.end(), 
                      std::inserter(newMap, newMap.begin());
person Armen Tsirunyan    schedule 19.12.2011
comment
Я запустил это (созданный с использованием VS2010), и он не включает 1-3 21-2. Если я поменяю местами вставку 1-3 21-4 и 1-3 21-2 в n, то это даст правильный результат. - person hmjd; 19.12.2011
comment
Я думаю, что set_intersection нуждается в сортировке stl, прежде чем они перейдут на него. - person Vijay; 19.12.2011
comment
@RahulDravid, а для multimap указано следующее: порядок пар ключ-значение, чьи ключи сравниваются эквивалентными, является порядком вставки и не изменяется. - person hmjd; 19.12.2011
comment
Да, это означает, что set_intersection в этом случае не работает!! так как я могу иметь несортированные данные в значении - person Vijay; 19.12.2011
comment
Да ... вы правы ... но меня немного беспокоит время, которое займет сортировка. В любом случае, я попробую. Также есть ли способ удалить общие элементы с обеих карт? - person Vijay; 19.12.2011
comment
@RahulDravid: Да, рассчитайте пересечение, а затем используйте set_difference, чтобы получить элементы, которые не являются общими. - person Armen Tsirunyan; 19.12.2011

arrow_upward
0
arrow_downward

Ради интереса вот прямой алгоритм, который перемещает общие элементы в новую мультикарту, изменяя исходные карты. Вы узнаете стандартный алгоритм «установить пересечение» для отсортированных диапазонов во внешнем цикле (относительно first); и поскольку мы не можем ничего предположить о сопоставленных значениях, внутренний цикл (относительно second) представляет собой линейный поиск по сопоставленным значениям для поиска равных.

template <typename T>
T move_common(T & a, T & b)
{
  typename T::const_iterator it1 = a.cbegin(), iend = a.cend(), jt1 = b.cbegin(), jend = b.cend();

  T result;

  while (it1 != iend && jt1 != jend)
  {
    if (it1->first < jt1->first)
    {
      ++it1;
    }
    else if (jt1->first < it1->first)
    {
      ++jt1;
    }
    else
    {
      typename T::const_iterator it2 = it1;

      while (it2 != iend && it2->first == it1->first)
      {
        typename T::const_iterator jt2 = jt1;
        while (jt2 != jend && jt2->first == jt1->first)
        {
          if (jt2->second == it2->second)
          {
            result.insert(*it2);
            if (it2 == it1) { a.erase(it1++); it2 = it1; } else { a.erase(it2++); }
            if (jt2 == jt1) { b.erase(jt1++); } else { b.erase(jt2); }
            break;
          }
          else
          {
            ++jt2;
            if (jt2 == jend || jt2->first != jt1->first) { ++it2; break; }
          }
        }
      }
      it1 = it2;
    }
  }
  return result;
}

Результат:

common  = [(1-2, 1-1), (1-2, 1-2), (1-3, 2-1), (1-3, 21-2)]
n after = [(1-2, 1-3), (1-2, 1-4), (1-3, 21-1)]
m after = [(1-2, 1-5), (1-2, 1-7), (1-3, 21-4)]
person Kerrek SB    schedule 19.12.2011