c++ - 将 std::sets 合并到 std::vector

Question

考虑以下。

我有两个std::sets 并希望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());

这是我的代码，有没有更有效的方法？提前致谢。

Answer 1

std::merge 应该可以解决问题，因为 S1 和 S2 已排序：

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

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

// 而不是 V.begin() -- 感谢您的更正。

Answer 2

我相信您可以使用以下方法简化代码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());

Answer 3

这些集合已经排序，所以最后再次重新排序似乎很浪费。

像这样的东西怎么样（留下几个 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;
    }

  }

Answer 4

您可以使用 std::merge()：http ://en.cppreference.com/w/cpp/algorithm/merge

它的实现与您的类似。