Предикат возвращающий есть ли пересечение
От: wonderer  
Дата: 18.08.09 23:57
Оценка:
Доброе время суток

Давеча попался мне вопрос один, на который я не могу найти ответ и поэтому он меня мучает...


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:

template <class T>
bool hasIntersection(std::vector<T>& set1, std::vector<T>& set2);


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

Вобщем, я запутался. Подскажите....
Re: Предикат возвращающий есть ли пересечение
От: Bell Россия  
Дата: 19.08.09 01:23
Оценка:
Здравствуйте, 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>
W>template <class T>
W>bool hasIntersection(std::vector<T>& set1, std::vector<T>& set2);
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>Вобщем, я запутался. Подскажите....

Мне кажется, нужно еще раз почитать про итераторы и алгоритмы
А еще лучше — попробуй сам реализовать один из вариантов (а может быть и все), и выложи его сюда, ну а за комментариями дело не станет
Любите книгу — источник знаний (с) М.Горький
Re[2]: Предикат возвращающий есть ли пересечение
От: Bell Россия  
Дата: 19.08.09 07:38
Оценка:
Здравствуйте, Bell, Вы писали:

W>>2)std::find_first_of

B>Можно использовать, задав длину искомой последовательности, равную 1.

Глупость написал — find_first_of ищет первое вхождение любого элемента из последовательности-запроса, так что требуемый предикат можно реализовать так:

template <class T>
bool hasIntersection(std::vector<T>& v1, std::vector<T>& v2)
{
   return (v1.end() != std::find_first_of(v1.begin(), v1.end(), v2.begin(), v2.end()));
}
Любите книгу — источник знаний (с) М.Горький
Re: Предикат возвращающий есть ли пересечение
От: Кодт Россия  
Дата: 19.08.09 14:25
Оценка:
Здравствуйте, wonderer, Вы писали:

Для упорядоченных контейнеров можно сделать по мотивам 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 <= *i
        else if(p(*j,*i)) // *j < *i
            j = std::lower_bound(j,je, *i, p); // *i <= *j
        else
            break;
    }
    return make_pair(i,j);
}
... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.