Форум программистов, компьютерный форум CyberForum.ru

Существует ли элемент в <vector> - C++

Восстановить пароль Регистрация
 
admsasha
12 / 12 / 4
Регистрация: 11.06.2011
Сообщений: 201
29.07.2012, 17:27     Существует ли элемент в <vector> #1
Как можно без перебора выяснить существует ли элемент уже в списке vector<int> ? Может есть такая функция в list или в deque ?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
DiffEreD
 Аватар для DiffEreD
1420 / 757 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
29.07.2012, 17:40     Существует ли элемент в <vector> #2
А чем вам алгоритм find не подходит? http://www.cplusplus.com/reference/algorithm/find/
admsasha
12 / 12 / 4
Регистрация: 11.06.2011
Сообщений: 201
29.07.2012, 17:46  [ТС]     Существует ли элемент в <vector> #3
Цитата Сообщение от yuron_477 Посмотреть сообщение
А чем вам алгоритм find не подходит? http://www.cplusplus.com/reference/algorithm/find/
1. на сколько я понял, он возращает последний элемент, если даже ничего не найдено.
2. Судя по описанию, это та же самая переборка и есть.

В задаче мне нужно найти элемент который отсутствует в контейнере. Чисел примерно ~10000. Соответственно проверка будет идти очень долго....
edward_jonson
 Аватар для edward_jonson
157 / 157 / 25
Регистрация: 23.02.2011
Сообщений: 388
29.07.2012, 17:52     Существует ли элемент в <vector> #4
C++
1
std::cout << (std::find (myvector.begin(), myvector.end(), myval) != myvector.end() ? "found" : "not found") << std::endl;
retmas
Жарю без масла
803 / 685 / 143
Регистрация: 13.01.2012
Сообщений: 1,580
29.07.2012, 17:54     Существует ли элемент в <vector> #5
Цитата Сообщение от admsasha Посмотреть сообщение
на сколько я понял, он возращает последний элемент, если даже ничего не найдено.
прочитайте внимателнее

Цитата Сообщение от admsasha Посмотреть сообщение
Судя по описанию, это та же самая переборка и есть.
если массив не отсортирован - придется перебирать
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
29.07.2012, 19:29     Существует ли элемент в <vector> #6
Цитата Сообщение от admsasha Посмотреть сообщение
В задаче мне нужно найти элемент который отсутствует в контейнере. Чисел примерно ~10000. Соответственно проверка будет идти очень долго....
Враки
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <chrono>
 
template <class I, class T>
I find(I first, const I& last, const T& var)
{
    for( ; first != last; ++first)
        if(*first == var)
            return first;
    return first;
}
 
template <class F, class... Args>
std::chrono::system_clock::rep foo(F&& function, Args&&... args)
{
    auto s = std::chrono::system_clock::now();
    function(args...);
    auto e = std::chrono::system_clock::now();
    return (e - s).count();
}
 
int main()
{
    using vector = std::vector<std::size_t>;
    const auto SIZE = 10000;
 
    vector v(SIZE);
    v.push_back(42);
 
    std::cout <<    foo
                    (
                        std::find<vector::iterator, vector::value_type>,
                        v.begin(),
                        v.end(),
                        42
                    ) << std::endl;
 
    std::cout <<    foo
                    (
                        find<vector::iterator, vector::value_type>,
                        v.begin(),
                        v.end(),
                        42
                    ) << std::endl;
 
    return 0;
}
Раза в 2 быстрее обычного перебора.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
29.07.2012, 21:07     Существует ли элемент в <vector> #7
Цитата Сообщение от soon Посмотреть сообщение
Раза в 2 быстрее обычного перебора.
C++
1
2
3
4
5
6
7
8
9
template <class I, class T>
inline
I find(I first, const I& last, const T& var)
{
    for( ; first != last; ++first)
        if(*first == var)
            return first;
    return first;
}
А так? (С++11 ниумею компилить.)
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
29.07.2012, 21:12     Существует ли элемент в <vector> #8
~OhMyGodSoLong~, -O3 по умолчанию инлайнит все функции.
Bash
1
2
3
4
5
6
7
8
# with inline
soon@desktop:~/Src/C++/main$ ./main 
11
17
# without
soon@desktop:~/Src/C++/main$ ./main 
11
17
Добавлено через 1 минуту
-O0
Bash
1
2
3
soon@desktop:~/Src/C++/main$ ./main 
173
337
Добавлено через 1 минуту
Так что дело тут совсем не в инлайне. diagon говорил, что g++ распараллеливает некторые функции из stl
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
29.07.2012, 21:14     Существует ли элемент в <vector> #9
/me усиленно пялится в исходники find. Там, правда, while, но не думаю, что это так влияет:
C++
1
2
3
4
5
6
7
8
template <class I, class T>
inline
I find(I first, const I& last, const T& var)
{
    while(first != last && !(*first == var))
        ++first;
    return first;
}
Ну если параллелит, тогда да.
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
29.07.2012, 21:16     Существует ли элемент в <vector> #10
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Ну если параллелит, тогда да.
*soon заменил for на while. Определенно параллелит
admsasha
12 / 12 / 4
Регистрация: 11.06.2011
Сообщений: 201
30.07.2012, 08:58  [ТС]     Существует ли элемент в <vector> #11
Не знаю почему, но действительно find быстро работает. Всем спасибо. Использую её.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2012, 12:25     Существует ли элемент в <vector> #12
Цитата Сообщение от soon Посмотреть сообщение
diagon говорил, что g++ распараллеливает некторые функции из stl
Там вроде надо специальные ключики указывать.
Тут есть подробнее.
Ну еще gcc умеет параллелить разные циклы, в том числе алгоритмы из stl, но там тоже свои ключики нужны. Например, этот - -ftree-parallelize-loops=n.

Цитата Сообщение от admsasha Посмотреть сообщение
В задаче мне нужно найти элемент который отсутствует в контейнере. Чисел примерно ~10000. Соответственно проверка будет идти очень долго....
Это можно эффективно сделать с помощью бинарного поиска.
Как-то так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector>
#include <algorithm>
 
int main()
{
    std::vector< int > vec = { 11, 1, 2, 3, 4, 5, 7, 9, 8 };
    sort( vec.begin(), vec.end() ); //сортировка обязательна
 
    for (int i = 0; i < 15; ++i)
    {
        //проверяет, есть ли элемент в векторе
        std::cout << i
                  << " : "
                  << std::boolalpha
                  << binary_search( vec.begin(), vec.end(), i )
                  << std::endl;
    }
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.07.2012, 12:42     Существует ли элемент в <vector>
Еще ссылки по теме:

C++ Std::vector добавить новый элемент собственного класса без использования конструктора копирования
C++ Теряю ссылку на элемент в std::vector после того, как делаю push_back следующего элемента
Как корректно скопировать vector в vector внутри класса C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
novi4ok
549 / 502 / 8
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
30.07.2012, 12:42     Существует ли элемент в <vector> #13
или использовать set вместо vector
Yandex
Объявления
30.07.2012, 12:42     Существует ли элемент в <vector>
Ответ Создать тему
Опции темы

Текущее время: 19:24. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru