как найти пересечение двух std :: set в C ++?

93

Я пытался найти пересечение между двумя std :: set в C ++, но все время получаю сообщение об ошибке.

Я создал небольшой образец теста для этого

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int main() {
  set<int> s1;
  set<int> s2;

  s1.insert(1);
  s1.insert(2);
  s1.insert(3);
  s1.insert(4);

  s2.insert(1);
  s2.insert(6);
  s2.insert(3);
  s2.insert(0);

  set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end());
  return 0;
}

Последняя программа не генерирует никакого вывода, но я ожидаю получить новый набор (назовем его s3) со следующими значениями:

s3 = [ 1 , 3 ]

Вместо этого я получаю сообщение об ошибке:

test.cpp: In function ‘int main()’:
test.cpp:19: error: no matching function for call to ‘set_intersection(std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>, std::_Rb_tree_const_iterator<int>)

Что я понимаю из этой ошибки, так это то, что в ней нет определения, set_intersectionкоторое принимает в Rb_tree_const_iterator<int>качестве параметра.

Кроме того, я полагаю, что std::set.begin()метод возвращает объект такого типа,

есть ли лучший способ найти пересечение двух std::setв C ++? Желательно встроенную функцию?

Большое спасибо!

Я люблю тако
источник
«Я ожидаю, что у меня будет новый набор (назовем его s3)» Но у тебя его нет и не было. Я не понимаю, чего вы ожидали от результатов. Также вы не читали документацию, чтобы узнать, какие аргументы передавать.
Гонки

Ответы:

113

Вы не предоставили итератор вывода для set_intersection

template <class InputIterator1, class InputIterator2, class OutputIterator>
OutputIterator set_intersection ( InputIterator1 first1, InputIterator1 last1,
                                InputIterator2 first2, InputIterator2 last2,
                                OutputIterator result );

Исправьте это, выполнив что-то вроде

...;
set<int> intersect;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(),
                  std::inserter(intersect,intersect.begin()));

Вам нужен std::insertитератор, поскольку на данный момент набор пуст. Мы не можем использовать back_ или front_inserter, поскольку set не поддерживает эти операции.

Картик Т
источник
71
Я хотел бы понять, почему такая фундаментальная операция над множествами требует такого загадочного многословного заклинания. Почему не простой set<T>& set::isect(set<T>&)метод, который сделает все необходимое? (Я бы попросил set<T>& set::operator^(set<T>&), но это, вероятно, слишком далеко.)
Райан В. Бисселл
3
@ RyanV.Bissell, это дизайн, похожий на почти все алгоритмы, <algorithm>если не что иное, как согласованность. Я полагаю, что этот стиль также дает вам гибкость. И позволяет использовать алгоритмы с несколькими контейнерами, хотя здесь этого может и не произойти .. Также ваша подпись может не работать, вам, вероятно, потребуется вернуть значение. И я думаю, что в те дни, когда еще не было семантики копирования, она была бы двойной копией. Я уже некоторое время не занимаюсь C ++, так что возьмите это с щепоткой или
тройкой
4
Я до сих пор считаю себя новичком в STL, поэтому применение крупинок соли тоже применимо. Срок действия моего окна редактирования комментария истек, поэтому я не могу исправить ошибку при возврате по ссылке. Мой комментарий был не жалобой на последовательность, а честным вопросом о том, почему этот синтаксис обязательно должен быть таким горьким. Возможно, мне стоит задать такой вопрос.
Райан В. Бисселл
3
На самом деле, большая часть стандартной библиотеки C ++ разработана таким неясным образом. Хотя элегантность дизайна очевидна (относительно универсальности, но не только), сложность API имеет разрушительные последствия (в основном потому, что люди продолжают изобретать колеса, поскольку они не могут использовать те, которые поставляются с их компилятором). В другом мире дизайнеры получили бы пощечину за то, что предпочли свое удовольствие пользователю. В этом мире ... ну, по крайней мере, у нас есть StackOverflow.
3
Это «общий синтаксис» - вы также можете выполнить set_intersection для вектора и в списке и сохранить результаты в двухсторонней очереди, и вы должны иметь возможность делать даже это эффективно (конечно, ваша проблема - позаботиться о том, чтобы оба исходные контейнеры сортируются перед вызовом this). Я не считаю это плохим, единственное, с чем у меня проблема, это то, что может быть также метод setконтейнера, который пересекается с другим набором. Тема передачи контейнера вместо .begin()- .end()это другое дело - это будет исправлено, когда в C ++ появятся концепции.
Ethouris
25

Взгляните на образец по ссылке: http://en.cppreference.com/w/cpp/algorithm/set_intersection

Вам нужен другой контейнер для хранения данных о пересечении, предположим, что ниже работает код:

std::vector<int> common_data;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::back_inserter(common_data));
Billz
источник
6
back_inserterне работает, так setкак setне имеет push_backфункции.
Джек Эйдли,
6

См. Std :: set_intersection . Вы должны добавить итератор вывода, в котором вы будете хранить результат:

#include <iterator>
std::vector<int> s3;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::back_inserter(s3));

См. Полный список в Ideone .

Олаф Дитше
источник
3
Обратите внимание, что back_inserter не будет работать, если вы хотите, чтобы результат также был набором, тогда вам понадобится std :: insertter, как у Karthik.
Джозеф Гарвин,
4

Просто прокомментируйте здесь. Думаю, пора добавить операцию объединения, пересечения в заданный интерфейс. Предложим это в будущих стандартах. Я давно использую стандартную операцию, и каждый раз, когда я использовал операцию установки, мне хотелось, чтобы она была лучше. Для некоторых сложных операций над множеством, таких как пересечение, вы можете просто (проще?) Изменить следующий код:

template <class InputIterator1, class InputIterator2, class OutputIterator>
  OutputIterator set_intersection (InputIterator1 first1, InputIterator1 last1,
                                   InputIterator2 first2, InputIterator2 last2,
                                   OutputIterator result)
{
  while (first1!=last1 && first2!=last2)
  {
    if (*first1<*first2) ++first1;
    else if (*first2<*first1) ++first2;
    else {
      *result = *first1;
      ++result; ++first1; ++first2;
    }
  }
  return result;
}

скопировано с http://www.cplusplus.com/reference/algorithm/set_intersection/

Например, если вы выводите набор, вы можете output.insert (* first1). Кроме того, ваша функция может не быть шаблонной. Если ваш код может быть короче, чем использование функции std set_intersection, то продолжайте.

Если вы хотите объединить два набора, вы можете просто setA.insert (setB.begin (), setB.end ()); Это намного проще, чем метод set_union. Однако с вектором это не сработает.

Кемин Чжоу
источник
4

Первый (получивший хорошее голосование) комментарий принятого ответа жалуется на отсутствие оператора для существующих операций стандартного набора.

С одной стороны, я понимаю отсутствие таких операторов в стандартной библиотеке. С другой стороны, при желании их легко добавить (для личного удовольствия). Я перегружен

  • operator *() для пересечения множеств
  • operator +() для объединения множеств.

Образец test-set-ops.cc:

#include <algorithm>
#include <iterator>
#include <set>

template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC> operator * (
  const std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
  std::set<T, CMP, ALLOC> s;
  std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
    std::inserter(s, s.begin()));
  return s;
}

template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC> operator + (
  const std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
  std::set<T, CMP, ALLOC> s;
  std::set_union(s1.begin(), s1.end(), s2.begin(), s2.end(),
    std::inserter(s, s.begin()));
  return s;
}

// sample code to check them out:

#include <iostream>

using namespace std;

template <class T>
ostream& operator << (ostream &out, const set<T> &values)
{
  const char *sep = " ";
  for (const T &value : values) {
    out << sep << value; sep = ", ";
  }
  return out;
}

int main()
{
  set<int> s1 { 1, 2, 3, 4 };
  cout << "s1: {" << s1 << " }" << endl;
  set<int> s2 { 0, 1, 3, 6 };
  cout << "s2: {" << s2 << " }" << endl;
  cout << "I: {" << s1 * s2 << " }" << endl;
  cout << "U: {" << s1 + s2 << " }" << endl;
  return 0;
}

Скомпилировано и протестировано:

$ g++ -std=c++11 -o test-set-ops test-set-ops.cc 

$ ./test-set-ops     
s1: { 1, 2, 3, 4 }
s2: { 0, 1, 3, 6 }
I: { 1, 3 }
U: { 0, 1, 2, 3, 4, 6 }

$ 

Что мне не нравится, так это копия возвращаемых значений в операторах. Возможно, это можно было бы решить с помощью назначения ходов, но это все еще не в моих силах.

Из-за моих ограниченных знаний об этой "новой причудливой" семантике перемещения я был обеспокоен возвратом оператора, который мог вызвать копии возвращенных наборов. Олаф Дитше отметил, что в этих проблемах нет необходимости, поскольку std::setон уже оснащен конструктором / назначением перемещения.

Хотя я ему верил, я думал, как это проверить (что-то вроде «самоубийства»). На самом деле это довольно просто. Поскольку шаблоны должны быть предоставлены в исходном коде, вы можете просто выполнить их с помощью отладчика. Таким образом, я поставил точку останова прямо на return s;из operator *()и протекал с пошаговым , который этилированным меня сразу в std::set::set(_myt&& _Right): вуаля - ход конструктора. Спасибо, Олаф, за (мое) просветление.

Для полноты картины я также реализовал соответствующие операторы присваивания

  • operator *=() для «деструктивного» пересечения множеств
  • operator +=() для «деструктивного» объединения множеств.

Образец test-set-assign-ops.cc:

#include <iterator>
#include <set>

template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC>& operator *= (
  std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
  auto iter1 = s1.begin();
  for (auto iter2 = s2.begin(); iter1 != s1.end() && iter2 != s2.end();) {
    if (*iter1 < *iter2) iter1 = s1.erase(iter1);
    else {
      if (!(*iter2 < *iter1)) ++iter1;
      ++iter2;
    }
  }
  while (iter1 != s1.end()) iter1 = s1.erase(iter1);
  return s1;
}

template <class T, class CMP = std::less<T>, class ALLOC = std::allocator<T> >
std::set<T, CMP, ALLOC>& operator += (
  std::set<T, CMP, ALLOC> &s1, const std::set<T, CMP, ALLOC> &s2)
{
  s1.insert(s2.begin(), s2.end());
  return s1;
}

// sample code to check them out:

#include <iostream>

using namespace std;

template <class T>
ostream& operator << (ostream &out, const set<T> &values)
{
  const char *sep = " ";
  for (const T &value : values) {
    out << sep << value; sep = ", ";
  }
  return out;
}

int main()
{
  set<int> s1 { 1, 2, 3, 4 };
  cout << "s1: {" << s1 << " }" << endl;
  set<int> s2 { 0, 1, 3, 6 };
  cout << "s2: {" << s2 << " }" << endl;
  set<int> s1I = s1;
  s1I *= s2;
  cout << "s1I: {" << s1I << " }" << endl;
  set<int> s2I = s2;
  s2I *= s1;
  cout << "s2I: {" << s2I << " }" << endl;
  set<int> s1U = s1;
  s1U += s2;
  cout << "s1U: {" << s1U << " }" << endl;
  set<int> s2U = s2;
  s2U += s1;
  cout << "s2U: {" << s2U << " }" << endl;
  return 0;
}

Скомпилировано и протестировано:

$ g++ -std=c++11 -o test-set-assign-ops test-set-assign-ops.cc 

$ ./test-set-assign-ops
s1: { 1, 2, 3, 4 }
s2: { 0, 1, 3, 6 }
s1I: { 1, 3 }
s2I: { 1, 3 }
s1U: { 0, 1, 2, 3, 4, 6 }
s2U: { 0, 1, 2, 3, 4, 6 }

$
Scheff
источник
1
std::setуже реализует необходимый конструктор перемещения и оператор присваивания, поэтому не нужно об этом беспокоиться. Также компилятор, скорее всего, использует оптимизацию возвращаемого значения
Olaf
@OlafDietsche Спасибо за ваш комментарий. Я проверил это и соответственно улучшил ответ. Что касается RVO, у меня уже были определенные обсуждения с моими коллегами, пока я не показал им в отладчике VS2013, что этого не происходит (по крайней мере, на нашей платформе разработки). На самом деле это не так важно, за исключением случаев, когда код критичен к производительности. В последнем случае я пока не полагаюсь на RVO. (На самом деле это не так уж и сложно в C ++ ...)
Scheff
@Scheff ну Scheff (не Bose), хорошее объяснение.
JeJo
Даже сейчас VS поддержка гарантированного исключения C ++ 17 ужасна.
Гонки