2

私のプロジェクトは、既存のアルゴリズムを並列化するための分割統治戦略を扱っています。アルゴリズムは を返します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 ;
}
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は 2 つの引数を取ります。挿入イテレータが必要なコンテナ (つまりfinal_m) と、挿入の開始点として使用される同じコンテナの通常のイテレータです。マージ操作の性質上、挿入の開始点は、作成中のマルチマップの最後にする必要があります。そのため、第 2 引数としてend(final_m)( と同じ) を使用しました。final_m.end()

于 2012-11-05T09:25:04.147 に答える