bagaimana menemukan persimpangan dua std :: set di C ++?

Saya telah mencoba menemukan persimpangan antara dua std :: set di C ++, tetapi saya terus mendapatkan kesalahan.

Saya membuat tes sampel kecil untuk ini

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

Program terakhir tidak menghasilkan output apa pun, tetapi saya berharap memiliki set baru (sebut saja s3) dengan nilai-nilai berikut:

s3 = [ 1 , 3 ]

Sebaliknya saya mendapatkan kesalahan:

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>)’

Apa yang saya pahami dari kesalahan ini, adalah bahwa tidak ada definisi set_intersectionyang menerima Rb_tree_const_iterator<int>sebagai parameter.

Selanjutnya, saya kira std::set.begin()metode mengembalikan objek dengan tipe seperti itu,

apakah ada cara yang lebih baik untuk menemukan perpotongan dua std::setdi C ++? Lebih disukai fungsi built-in?

Terima kasih banyak!

Anda belum menyediakan iterator keluaran untuk set_intersection

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

Perbaiki ini dengan melakukan sesuatu seperti

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

Anda memerlukan std::insertiterator karena set tersebut sudah kosong. Kita tidak dapat menggunakan back_ atau front_inserter karena set tidak mendukung operasi tersebut.

Lihat contoh di tautan: http://en.cppreference.com/w/cpp/algorithm/set_intersection

Anda membutuhkan wadah lain untuk menyimpan data persimpangan, kode di bawah ini seharusnya berfungsi:

std::vector<int> common_data;
set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::back_inserter(common_data));

Lihat std :: set_intersection . Anda harus menambahkan iterator keluaran, tempat Anda akan menyimpan hasilnya:

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

Lihat Ideone untuk daftar lengkap.

Beri komentar saja di sini. Saya pikir sudah waktunya untuk menambahkan operasi persatuan, memotong ke antarmuka yang ditetapkan. Mari usulkan ini di standar masa depan. Saya telah menggunakan std untuk waktu yang lama, setiap kali saya menggunakan operasi set, saya berharap std lebih baik. Untuk beberapa operasi himpunan yang rumit, seperti intersect, Anda dapat (lebih mudah?) Memodifikasi kode berikut:

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

disalin dari http://www.cplusplus.com/reference/algorithm/set_intersection/

Misalnya, jika output Anda satu set, Anda dapat output.insert (* first1). Selain itu, fungsi Anda mungkin tidak memiliki template. Jika kode Anda bisa lebih pendek daripada menggunakan fungsi set_intersection std maka lanjutkan dengan itu.

Jika Anda ingin melakukan penyatuan dua set, Anda cukup setA.insert (setB.begin (), setB.end ()); Ini jauh lebih sederhana daripada metode set_union. Namun, ini tidak akan berfungsi dengan vektor.

Komentar pertama (dipilih dengan baik) dari jawaban yang diterima mengeluh tentang operator yang hilang untuk operasi set std yang ada.

Di satu sisi, saya memahami kurangnya operator semacam itu di perpustakaan standar. Di sisi lain, mudah untuk menambahkannya (untuk kesenangan pribadi) jika diinginkan. Saya kelebihan beban

• operator *() untuk persimpangan set
• operator +() untuk penyatuan set.

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

Disusun dan diuji:

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

$ 

Yang tidak saya sukai adalah salinan nilai kembalian di operator. Mungkin, ini bisa diselesaikan menggunakan tugas bergerak tetapi ini masih di luar kemampuan saya.

Karena pengetahuan saya yang terbatas tentang semantik gerakan "mewah baru" ini, saya khawatir tentang pengembalian operator yang mungkin menyebabkan salinan dari set yang dikembalikan. Olaf Dietsche menunjukkan bahwa kekhawatiran ini tidak perlu karena std::setsudah dilengkapi dengan konstruktor / penugasan bergerak.

Meskipun saya percaya padanya, saya sedang berpikir bagaimana cara memeriksa ini (untuk sesuatu seperti "meyakinkan diri"). Sebenarnya caranya cukup mudah. Karena templat harus disediakan dalam kode sumber, Anda cukup melangkah dengan debugger. Jadi, saya menempatkan titik istirahat yang tepat di return s;satu operator *()dan melanjutkan dengan single-langkah yang dipimpin saya segera ke std::set::set(_myt&& _Right): et voila - langkah konstruktor. Terima kasih, Olaf, atas pencerahan (saya).

Demi kelengkapan, saya juga menerapkan operator penugasan yang sesuai

• operator *=() untuk persimpangan "destruktif" dari set
• operator +=() untuk penyatuan set yang "merusak".

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

Disusun dan diuji:

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

$