Пересечение множеств

[Mirazhana]

Помогите с программой на С++, у самой никак не получается. Даны значения двух целочисленных массивов x и y размером n. Рассматривая массивы как конечные множество целых чисел, построить массив z размером не более 2n, где z = x пересекает y.
Нашла подобную программу но там z = x Δ y (симментрическая разность)

[EUGY]

Вроде одной функцией из <algorithm> решается.
Только перед этим массивы x & y отсортировать.

http://www.cplusplus.com/reference/a..._intersection/

[Murashov]

Сообщение от EUGY

Только перед этим массивы x & y отсортировать.

ничего сортировать не надо при операции пересеч., объед., вычит. и т.п. (не знаю сколько их). Алгоритм должен итак работать.

[EUGY]

Алгоритм должен итак работать.

Ой ли?

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

int main () {
  int first[] = {5,10,15,20,25};
  int second[] = {50,40,30,20,10};
  vector<int> v(10);                        
  //sort (first,first+5);     //  5 10 15 20 25
 // sort (second,second+5);   // 10 20 30 40 50

  set_intersection (first, first+5, second, second+5, v.begin());
  for (int i = v.size(); i--;)
	  std::cout <<  v[i] << std::endl;

  return 0;
}

function template std::set_intersection
Intersection of two sorted ranges
Constructs a sorted range beginning in the location pointed by result with the set intersection of the two sorted ranges [first1,last1) and [first2,last2) as content.

[Murashov]

ой ли? :D

откуда вообще эта функция? вернее описание просто

[Son Of Pain]

Сообщение от Murashov

откуда вообще эта функция? вернее описание просто

Тебе стандарт языка процитировать?
На сортированных множествах алгоритм отрабатывает за o(n), на несортированных было бы o(n^2). Потому в stl включили более оптимальную версию.

[Murashov]

язык чего? при чём тут конкретный язык программирования? множества - математика же.. в теории нужна ли сортировка вообще? блин я уже не уверен) нифига не помню

[EUGY]

язык чего? при чём тут конкретный язык программирования? множества - математика же.. в теории нужна ли сортировка вообще? блин я уже не уверен) нифига не помню

В теории сортировка не нужна.
И конечно, можно написать алгоритм пересечения не сортированных массивов.
Но предполагается, что мы здесь в ветке языка с++, у которого есть библиотека STL. Она стала стандартом (де-факто). В нее, в частности, включена функция set_intersection, имеющая документированное описание, из которого следует, что работает она с отсортированными массивами.

[Murashov]

Сообщение от EUGY

В теории сортировка не нужна.
И конечно, можно написать алгоритм пересечения не сортированных массивов.
Но предполагается, что мы здесь в ветке языка с++, у которого есть библиотека STL. Она стала стандартом (де-факто). В нее, в частности, включена функция set_intersection, имеющая документированное описание, из которого следует, что работает она с отсортированными массивами.

во, теперь понятно, спасибо.

ответ-то всё равно один будет.. как ни крути. а отсортировать всегда можно успеть