3

以下を検討してください。

2 つの があり、それらをソート順std::setにマージしたいと考えています。std::vector

それを行う最も効果的な方法はどれですか？

私はこのようなことをしましたが、もっと良い方法があるに違いないと思います。

std::set<int> S1;
std::set<int> S2;
// ....
// Initialization of sets
// ....

std::vector V;

std::set<int>::iterator iter;

for(iter = S1.begin(); iter!=S1.end(); ++iter)
{
    V.push_back(*iter);
}

for(iter = S2.begin(); iter!=S2.end(); ++iter)
{
    V.push_back(*iter);
}

std::sort(V.begin(), V.end());

これが私のコードです。より効果的な方法はありますか? 前もって感謝します。

4

4 に答える 4

7

S1 と S2 がソートされているため、std::merge でうまくいくはずです。

// Initialization of sets
// ....
std::vector V;

std::merge(S1.begin(), S1.end(), S2.begin(), S2.end(), std::back_inserter(V));

// V.begin() の代わりに -- 訂正していただきありがとうございます。

于 2014-05-08T16:42:39.787 に答える
1

を使用してコードを簡素化できると思いますstd::copy()：

std::copy(S1.begin(), S1.end(), std::back_inserter(V));
std::copy(S2.begin(), S2.end(), std::back_inserter(V));
std::sort(V.begin(), V.end());
于 2014-05-08T16:39:26.980 に答える
1

セットはすでにソートされているので、最後にすべて再ソートするのはもったいないようです。

次のようなものはどうでしょうか (読者の演習として TODO をいくつか残しておいてください!):

  std::set<int>iterator S1iter = S1.begin();
  std::set<int>iterator S1iter = S2.begin();

  while( S1iter != S1.end() && S2iter != S2.end() ) {

    if( S1iter == S1.end() ) {
       //TODO:  S1 is finished, so push back range S2iter->S2.end()
       //       onto the vector
       break;
    }
    else if( S2iter == S2.end() ) {
       //TODO:  S2 is finished, so push back range S1iter->S1.end()
       //       onto the vector
       break;
    }
    else if( *S1iter < *S2iter ) {
      V.push_back( *S1iter );
      ++S1iter;
    }
    else {
      V.push_back( *S2iter );
      ++S2iter;
    }

  }
于 2014-05-08T16:49:15.443 に答える