Просмотрите все три значения, содержащиеся в std :: set? - PullRequest
Новая
       69

Просмотрите все три значения, содержащиеся в std :: set?

0 голосов
/ 27 августа 2018

Предположим, у меня есть отсортированный вектор без дублированных значений. Если я хочу пройти через все тройки разных значений, я делаю это: 

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 для совместимости.

Ответы [ 5 ]

0 голосов
/ 27 августа 2018

Вы можете думать о своей проблеме так, как будто вам пришлось использовать итераторы над индексами в вашем векторном примере. Давайте упростим это так: 

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

Это в основном упрощенная версия предлагаемой реализации 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);
0 голосов
/ 27 августа 2018

Вы можете сделать то же самое, что и с вектором, но вам нужно будет создать функцию-обертку, которая будет копировать и увеличивать итератор набора: 

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)
       // ...
0 голосов
/ 27 августа 2018

Вы можете создать из него вектор, а затем сделать это так, как обычно. 

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]);
0 голосов
/ 27 августа 2018

вы можете сделать что-то вроде: 

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.

0 голосов
/ 27 августа 2018

Это особый случай выбора всех k-комбинаций из набора из n элементов.

См. Здесь для объяснения: https://en.wikipedia.org/wiki/Combination

И здесь уже был дан ответ на stackoverflow: создание всех возможных k комбинаций из n элементов в C ++

...