遍历 std::set 中包含的所有三重不同值？

Question

假设我有一个没有重复值的排序向量。如果我想遍历所有不同值的三元组，我会这样做：

for(std::size_t i = 0; i < data.size(); ++i)
  for(std::size_t j = i+1; j < data.size(); ++j)
    for(std::size_t k = j+1; k < data.size(); ++k)
      do_somthing_with(data[i],data[j],data[k]);

如果我的容器是 std::set，我该如何使用迭代器做到这一点？

注意：出于兼容性原因，我不使用 C++11。

Answer 1

这是从一组n个元素中选择所有k个组合的特例。

请看这里的解释：https://en.wikipedia.org/wiki/Combination

之前在 Whosebug 上已经回答过这个问题： creating all possible k combinations of n items in C++

Answer 2

您可以从中创建一个矢量，然后按照您通常的方式进行操作。

std::set<int> s = {1, 2, 3, 4, 5, 6, 7};
std::vector<int> data(s.begin(), s.end());
for(std::size_t i = 0; i < data.size(); ++i)
  for(std::size_t j = i+1; j < data.size(); ++j)
    for(std::size_t k = j+1; k < data.size(); ++k)
      do_somthing_with(data[i],data[j],data[k]);

Answer 3

你可以这样做：

if (data.size() < 2) { return; }

for (auto it1 = data.begin(); it1 != std::prev(data.end(), 2); ++it1) {
    for (std::size_t it2 = std::next(it1); it2 != std::prev(data.end()); ++it2) {
      for (std::size_t it3 = std::next(it2); it3 != data.end(); ++it3) {
          do_something_with(*it1, *it2, *it3);
      }
   }
}

您可以缓存 std::prev 的值。

Answer 4

您可以执行与向量几乎相同的操作，但您需要创建一个包装函数，它将复制和递增集合迭代器：

std::set<int>::const_iterator next_iterator(std::set<int>::const_iterator it)
{
  return ++it; // it has been passed by value, so already copied
}

//...

for (std::set<int>::const_iterator it = data.begin(); it != data.end(); ++it)
  for(std::set<int>::const_iterator jt = next_iterator(it); jt != data.end(); ++jt)
    for(std::set<int>::const_iterator kt = next_iterator(jt); kt != data.end(); ++kt)
       // ...

Answer 5

您可以将您的问题想象成您必须在矢量示例中对索引使用迭代器。让我们这样简化它：

for(std::size_t i = 0; i < data.size(); ++i)
  do_somthing_with(data[i]);

你可以用迭代器这样写：

for(std::vector<MyClass>::iterator it = data.begin(); it != data.end(); ++it)
  do_somthing_with(*it);

现在可以直接对集合执行相同的操作：

for(std::set<MyClass>::iterator it = data.begin(); it != data.end(); ++it)
  do_somthing_with(*it);

如果你想使用三重循环，在我看来问题是从下一个迭代器开始的。在 C++11 中，您可以使用 std::next 但由于您不能，因此您需要存储迭代器然后推进它：

for(std::set<MyClass>::iterator it1 = data.begin(); it1 != data.end(); ++it1)
{
  std::set<MyClass>::iterator it2 = it1;
  ++it2;
  for(; it2 != data.end(); ++it2)
  {
    std::set<MyClass>::iterator it3 = it2;
    ++it3;
    for(; it3 != data.end(); ++it3)
      do_somthing_with(*it1,*it2,*it3);
  }
}

或者您可以定义自己的 next 函数，例如：

template<class ForwardIt>
ForwardIt next(ForwardIt it)
{
    return ++it;
}

这基本上是suggested implementation of std::next的简化版本。

那么重写代码就更容易了：

for(std::set<MyClass>::iterator it1 = data.begin(); it1 != data.end(); ++it1)
  for(std::set<MyClass>::iterator it2 = next(it1); it2 != data.end(); ++it2)
    for(std::set<MyClass>::iterator it3 = next(it2); it3 != data.end(); ++it3)
      do_somthing_with(*it1,*it2,*it3);

遍历 std::set 中包含的所有三重不同值？

Go through all triple of different values contained in a std::set?

c++

iterator

c++03

c++98

stdset