VPF::Поиск одинаковых значений в двух векторах

Rutti

Дата 26.4.2007, 15:16 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 225
Регистрация: 25.7.2004

Репутация: нет
Всего: нет

Есть ли стандартная возможность поиска в двух векторах разных размеров одного типа одинаковых значений?

Daevaorn

Дата 26.4.2007, 15:27 (ссылка)

(голосов:2)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2155
Регистрация: 29.11.2004
Где: Москва

Репутация: 51
Всего: 70

http://www.sgi.com/tech/stl/set_intersection.html

boriska

Дата 26.4.2007, 17:13 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 36
Регистрация: 7.12.2006
Где: kharkov

Репутация: нет
Всего: нет

есть еще такой алгоритм как find_first_of()

Код


#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
    int array1[5] = {0, 2, 4, 6, 8};
    int array2[8] = {0, 1, 8, 5, 7, 11, 2, 4};

    vector<int> vec1(array1, array1+5);
    vector<int> vec2(array2, array2+8);

    vector<int>::iterator pos = vec1.begin();
    
    while (( pos = find_first_of(pos, vec1.end(), vec2.begin(), vec2.end())) != vec1.end())
    {
        cout << "Equal value : " << *pos << endl;
        ++pos;
    }

    return 0;
}

Это сообщение отредактировал(а) boriska - 26.4.2007, 17:17

Daevaorn

Дата 26.4.2007, 17:19 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2155
Регистрация: 29.11.2004
Где: Москва

Репутация: 51
Всего: 70

Цитата(boriska @ 26.4.2007, 18:13

)

есть еще такой алгоритм как find_first_of()

а ещё есть оператор условного перехода if smile

JackYF

Дата 26.4.2007, 17:22 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

Хм...
boriska, у тебя будет квадратичная сложность, хотя решение и красивое. Я бы все-таки взял вариант Daevaornа, предварительно скопировав данные в два set'a.

--------------------

Пожаловаться на меня как модератора можно здесь.

Daevaorn

Дата 26.4.2007, 17:26 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 2155
Регистрация: 29.11.2004
Где: Москва

Репутация: 51
Всего: 70

Цитата(JackYF @ 26.4.2007, 18:22

)

предварительно скопировав данные в два set'a.

вовсе не обязательно что-то копировать. нужно только отсортировать

JackYF

Дата 26.4.2007, 17:29 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

Цитата(Daevaorn @ 26.4.2007, 17:26

)

вовсе не обязательно что-то копировать. нужно только отсортировать

В принципе, да. Но сеты это сделают автоматом + не изменят исходных двух векторов. Может, оно и не надо, но мало ли...

--------------------

Пожаловаться на меня как модератора можно здесь.

Earnest

Дата 27.4.2007, 18:05 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183

Цитата(JackYF @ 26.4.2007, 18:29

)

В принципе, да. Но сеты это сделают автоматом + не изменят исходных двух векторов. Может, оно и не надо, но мало ли

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

--------------------

...

JackYF

Дата 27.4.2007, 20:44 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

Цитата(Earnest @ 27.4.2007, 18:05

)

По памяти

тут однозначно да

Цитата(Earnest @ 27.4.2007, 18:05

)

по быстродействию

гм... честно говоря, не очевидно, хотя и возможно.
Тут желательно провести эксперимент.

--------------------

Пожаловаться на меня как модератора можно здесь.

Earnest

Дата 28.4.2007, 20:13 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183

Цитата(JackYF @ 27.4.2007, 21:44

)

честно говоря, не очевидно, хотя и возможно

Во первых, Мейерс так пишет в "Эффективном использовании STL", а во вторых, можно прикинуть так:
формально, это операции одного порядка:
Элементы в вектор добавляются пулей, особенно если просто копия делается, а потом сортировка N*logN.
Вствка в set логарифмическая, и так N раз. Но при этом не надо забывать о том, что set производит перебалансировку дерева при своем росте, а это операция не очень тривиальная.
Кроме того, итерация по сету или по вектору - тоже две большие разницы (это когда мы set_difference строить будем)...

--------------------

...

JackYF

Дата 29.4.2007, 23:31 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

Цитата(Earnest @ 28.4.2007, 20:13

)

Вствка в set логарифмическая, и так N раз. Но при этом не надо забывать о том, что set производит перебалансировку дерева при своем росте, а это операция не очень тривиальная.
Кроме того, итерация по сету или по вектору - тоже две большие разницы (это когда мы set_difference строить будем)...

Убедила. Согласен.

--------------------

Пожаловаться на меня как модератора можно здесь.

Voldemar2004

Дата 30.4.2007, 18:13 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1650
Регистрация: 25.12.2004

Репутация: нет
Всего: 23

Я бы так сделал:

Код

#include <iostream>

int main()
{
    int array1[5] = {0, 2, 4, 6, 8};
    int array2[8] = {0, 1, 8, 5, 7, 11, 2, 4};

    for(int i=0; i<5; ++i)
     for(int j=0; j<8; ++j)
      if(array1[i] == array2[j]) std::cout << array1[i] << '\t';

std::cin.get();

return 0;
}

Это сообщение отредактировал(а) Voldemar2004 - 30.4.2007, 18:15

--------------------

i_i
(';')
(V)

user posted image

JackYF

Дата 1.5.2007, 23:40 (ссылка)

(нет голосов)

Загрузка ...

полуавантюрист

Профиль
Группа: Участник
Сообщений: 5814
Регистрация: 28.8.2004
Где: страна тысячи озё р

Репутация: 18
Всего: 162

Цитата(Voldemar2004 @ 30.4.2007, 18:13

)

for(int i=0; i<5; ++i)
for(int j=0; j<8; ++j)
if(array1[i] == array2[j]) std::cout << array1[i] << '\t';

Та же квадратичная сложность. В плане быстродействия может выступить боком, см. посты выше.

--------------------

Пожаловаться на меня как модератора можно здесь.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »