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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
admsasha
14 / 14 / 4
Регистрация: 11.06.2011
Сообщений: 212
#1

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

29.07.2012, 17:27. Просмотров 866. Ответов 12
Метки нет (Все метки)

Как можно без перебора выяснить существует ли элемент уже в списке vector<int> ? Может есть такая функция в list или в deque ?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.07.2012, 17:27     Существует ли элемент в <vector>
Посмотрите здесь:

Удалить элемент из std::vector - C++
vector&lt;int&gt; k; надо удалить k элемент.

Как удалить последний элемент контейнера vector - C++
Доброго вечера всем!!!Подскажите пожалуйста как удалить последний элемент контейнера vector,уменьшив его длину тем самым на 1...

Как добавить элемент структуры с использованием #include <vector> ? - C++
#include &lt;vector&gt; #include &lt;iostream&gt; using namespace std; struct Item { int n; };

Удалить первый совпадающий по значению элемент из std::vector - C++
Пояснение: дано допустим так: int i = 5; Нужно удалить из вектора vector&lt;int&gt; первый попавшийся элемент со значением 5. Сам уж себя в...

Std::vector добавить новый элемент собственного класса без использования конструктора копирования - C++
Всем привет! Есть один класс, который я хочу хранить в std::vector. Создать массив, с типом своего класса, грубо говоря. Естественно,...

Теряю ссылку на элемент в std::vector после того, как делаю push_back следующего элемента - C++
Добрый день! Подскажите пожалуйста в чем причина моей ошибки. Сам работал на чистом C++, то есть использовал все по минимуму из C++. В...

Заменить в каждом массиве максимальный элемент средним арифметическим положительных элементов (если оно существует) соответствующего массива - C++
Здравствуйте, помогите пожалуйста: Ввести одномерные массивы X1(N1) , X2(N2) и X3(N3) . Заменить в каждом из них максимальный...

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

В задаче мне нужно найти элемент который отсутствует в контейнере. Чисел примерно ~10000. Соответственно проверка будет идти очень долго....
edward_jonson
158 / 158 / 25
Регистрация: 23.02.2011
Сообщений: 391
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
Жарю без масла
859 / 741 / 164
Регистрация: 13.01.2012
Сообщений: 1,694
29.07.2012, 17:54     Существует ли элемент в <vector> #5
Цитата Сообщение от admsasha Посмотреть сообщение
на сколько я понял, он возращает последний элемент, если даже ничего не найдено.
прочитайте внимателнее

Цитата Сообщение от admsasha Посмотреть сообщение
Судя по описанию, это та же самая переборка и есть.
если массив не отсортирован - придется перебирать
soon
2540 / 1305 / 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
~ Эврика! ~
1243 / 992 / 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
2540 / 1305 / 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
~ Эврика! ~
1243 / 992 / 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
2540 / 1305 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
29.07.2012, 21:16     Существует ли элемент в <vector> #10
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Ну если параллелит, тогда да.
*soon заменил for на while. Определенно параллелит
admsasha
14 / 14 / 4
Регистрация: 11.06.2011
Сообщений: 212
30.07.2012, 08:58  [ТС]     Существует ли элемент в <vector> #11
Не знаю почему, но действительно find быстро работает. Всем спасибо. Использую её.
diagon
Higher
1928 / 1194 / 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++
Как спросить у программы: &quot;Если существует соседний элемент массива по вертикали или горизонтали, то ...&quot; Собственно пробывал так: ...

Существует ли элемент в "сложном" векторе - C++
Здравствуйте, недавно столкнулся с такой проблемой Есть такая структура и последующий вектор: struct cell { char symbol; int...

Bind vector<vector<A*>> - C++
Привет всем ! вот код struct A { void qwer(int a) { qDebug()&lt;&lt;a; } }; int main(int argc, char...

Поиск в vector < vector <T> > - C++
есть двумерный массив vector &lt; vector &lt;double&gt; &gt; a(size, vector&lt;double&gt;(size, 0)); заполняем рандомом, надо найти индекс последнего...

vector<vector <bool> > - C++
vector&lt;vector &lt;bool&gt; &gt; v1; bool v2 = { {1,1}, {1,1}, }; как v1 присвоить v2? Добавлено через 1 минуту в c++11...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru