2

我的项目处理将现有算法并行化的分而治之策略。该算法返回一个std::multimap<int, std::pair<int, int>>. 以上是初步（单线程）版本的草图。

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 ;
}

我知道我可以使用 insert 或 merge 来进行合并（如此处所述）。但是插入在 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 ;
}
4

2 回答 2

5

是的，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它有两个参数：您需要一个用于 (ie final_m) 的插入迭代器的容器，以及一个用于同一容器的普通迭代器，它用作插入的起点。由于合并操作的性质，为插入指定的起点应该是正在创建的多映射的结尾。因此，我使用end(final_m)（与 相同final_m.end()）作为第二个参数。

于 2012-11-05T09:25:04.147 回答
1

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 );
于 2018-04-11T11:58:54.667 回答