Reffering to the scenario above, which one of the following STL functions can be used to to implement hasIntersection
1)std::search_n
2)std::find_first_of
3)std::equal
4)std::nth_element
5)std::adjacent_find
Насколько мне известно, все вышеперечисленные функции принимают предикат, в который передается один элемент, а не целая пачка, что я первым делом проверил, поискав сигнатуры оных. Да и как там может быть, что алгоритмы работают поитераторно, а передается целый контейнер?
Есть мысль — что этот самый контейнер и есть элемент какого-то другого контейнера, по которому и бежит итератор. тогда думаю в сторону find_first_of
А если нет — тогда adjacent_find
Здравствуйте, wonderer, Вы писали:
W>Давеча попался мне вопрос один, на который я не могу найти ответ и поэтому он меня мучает... W>You need to define the following function so that is will return true if the sets passed to it have any intersection and false otherwise:
W>
Итак, нам нужно определить — встречается ли хотя бы 1 элемент из одного контейнера в другом.
W>Reffering to the scenario above, which one of the following STL functions can be used to to implement hasIntersection W>1)std::search_n
Можно использовать, задав длину сегмента, равную 1.
W>2)std::find_first_of
Можно использовать, задав длину искомой последовательности, равную 1.
W>3)std::equal
Также можно использовать, сравнивая диапазоны еденичной длины (красивость этого решения обсуждать не будем )
W>4)std::nth_element
Не подходит, т.к. может быть использован только с отсортированными последовательностями (в условии про это ничего не сказано).
W>5)std::adjacent_find
Не подходит, т.к. работает с одной последовательностью.
W>Насколько мне известно, все вышеперечисленные функции принимают предикат, в который передается один элемент, а не целая пачка, что я первым делом проверил, поискав сигнатуры оных.
Судя по всему, проверил плохо:
std::adjacent_find — либо без предиката (обычное сравнение на равенство двух элементов), либо с бинарным предикатом.
std::nth_element — либо без предиката (обычное сравнение двух элементов на больше/меньше), либо с бинарным предикатом.
std::equal — либо без предиката (обычное сравнение на равенство двух элементов), либо с бинарным предикатом.
std::find_first_of — либо без предиката (обычное сравнение на равенство двух элементов), либо с бинарным предикатом.
std::search_n — либо без предиката (обычное сравнение на равенство двух элементов), либо с бинарным предикатом.
W>Да и как там может быть, что алгоритмы работают поитераторно, а передается целый контейнер?
Ээээ... имея контейнер, можно получить итераторы на его элементы — begin(), end().
W>Есть мысль — что этот самый контейнер и есть элемент какого-то другого контейнера, по которому и бежит итератор. тогда думаю в сторону find_first_of
Совершенно ничего не понял.
W>А если нет — тогда adjacent_find
Совершенно неверно.
W>Вобщем, я запутался. Подскажите....
Мне кажется, нужно еще раз почитать про итераторы и алгоритмы
А еще лучше — попробуй сам реализовать один из вариантов (а может быть и все), и выложи его сюда, ну а за комментариями дело не станет
Здравствуйте, Bell, Вы писали:
W>>2)std::find_first_of B>Можно использовать, задав длину искомой последовательности, равную 1.
Глупость написал — find_first_of ищет первое вхождение любого элемента из последовательности-запроса, так что требуемый предикат можно реализовать так:
Для упорядоченных контейнеров можно сделать по мотивам set_intersection
template<class I, class J, class P>
std::pair<I,J> first_intersection(I i, I ie, J j, J je, P p)
{
while(i!=ie && j!=je)
{
if(p(*i,*j)) // *i < *j
++i;
else if(p(*j,*i)) // *j < *i
++j;
else
break;
}
return make_pair(i,j);
}
template<class I, class J, class P>
bool has_intersection(I i, I ie, J j, J je, P p)
{
std::pair<I,J> ij = first_intersection(i,ie, j,je, p);
return ij.first != ie && ij.second != je;
}
// в качестве P взять вот этоstruct versatile_less
{
template<class X, class Y> bool operator()(X const& x, Y const& y) const { return x<y; }
};
Это за линейное время.
Делаем за логарифмическое
template<class I, class J, class P>
std::pair<I,J> first_intersection(I i, I ie, J j, J je, P p)
{
while(i!=ie && j!=je)
{
if(p(*i,*j)) // *i < *j
i = std::lower_bound(i,ie, *j, p); // *j <= *ielse if(p(*j,*i)) // *j < *i
j = std::lower_bound(j,je, *i, p); // *i <= *jelse
break;
}
return make_pair(i,j);
}