Как я могу использовать слияние, чтобы объединить две карты / мультикарты (C ++ 11 STL)

Question

Как я могу использовать слияние, чтобы объединить две карты / мультикарты (C ++ 11 STL)

Мой проект имеет дело со стратегией «разделяй и властвуй», чтобы упорядочить существующий алгоритм.
Алгоритм возвращает std::multimap<int, std::pair<int, int>>, Выше приведен эскиз предварительной (single_thread) версии.

typedef std::multimap<int, std::pair<int, int>> Map ;
struct Box
{
std::pair<int, int> top_left, bottom_right ;
}
Map my_algo(Box, a_box)
{
Map final_m ;
if (not is_small(a_box))
{
box b1, b2 ;
split_box(a_box, &b1, &b2) ; // this function divides the box in two halves
Map m1 = my_algo(b1) ;
Map m2 = my_algo(b2) ;

// this line will not compile. final_m.begin() is not accepted.
std::merge (m1.begin(), m1.end(), m2.begin(), m2.end(), final_m.begin()) ;
}
return final_m ;
}

Я знаю, что я мог бы использовать вместо этого вставку или слияние, чтобы сделать слияние (как объяснено Вот). Но вставка в O (N.Log (n)), а слияние в O ((N)). Из-за количества операций слияния, задействованных в алгоритме, сложность времени имеет значение.

Спасибо за помощь,
Оливье

РЕДАКТИРОВАТЬ:

Благодаря jogojapan (см. Ответ ниже), это рабочая демонстрация исправленного кода:

#include <iostream>
#include <map>
#include <iterator>
#include <algorithm>

typedef std::pair<int, int> Cell ;
typedef std::multimap<int, Cell> Border_map ;

void test_merge_maps_1()
{
Border_map a, b, c ;
std::cout << std::endl << "a" << std::endl ;
for (int i=1; i<10; i+=2)
{
a.insert(std::pair<int, Cell>(i, Cell(i,i))) ;
std::cout << i << " " ;
}

std::cout << std::endl << "b" << std::endl ;
for (int i=2; i<11; i+=2)
{
b.insert(std::pair<int, Cell>(i, Cell(i,i))) ;
std::cout << i << " " ;
}

std::cout << std::endl << "merge" << std::endl ;
std::merge(a.begin(), a.end(), b.begin(), b.end(), inserter(c,end(c))) ;

std::cout << "result" << std::endl ;
for(auto x: c)
std::cout << x.first << " " ;
std::cout << std::endl ;
}

int main(void)
{
test_merge_maps_1() ;
return 0 ;
}

2

c++merge multimap stl

Решение

Другие решения

C ++ вставить

#include <map>
#include <string>

using std::map;
using std::string;

map< string, string > lhs;
map< string, string > rhs;

lhs.insert( rhs.begin( ), rhs.end( ) );

C ++ 17 сливаться

#include <map>
#include <string>

using std::map;
using std::string;

map< string, string > lhs;
map< string, string > rhs;

lhs.merge( rhs );

0

Источник

Accepted Answer

Да, multimap<T>::begin() возвращает обычный (двунаправленный) итератор, но вам нужен итератор, способный делать вставки. Вы можете получить один, используя std::inserter шаблон из iterator заголовок:

#include <iterator>

/* ... */

std::merge(begin(m1),end(m1),begin(m2),end(m2),inserter(final_m,end(final_m)));

Как вы видете, std::inserter принимает два аргумента: Контейнер, для которого требуется итератор вставки (т.е. final_m) и обычный итератор для того же контейнера, который используется в качестве отправной точки для вставок. В связи с характером операции слияния отправной точкой для вставок должна быть конец мульти-карты создаются. Поэтому я использовал end(final_m) (что так же, как final_m.end()) в качестве второго аргумента.

5