Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/6: Рейтинг темы: голосов - 6, средняя оценка - 4.50
28 / 27 / 7
Регистрация: 11.06.2011
Сообщений: 350
1

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

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

Как можно без перебора выяснить существует ли элемент уже в списке vector<int> ? Может есть такая функция в list или в deque ?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.07.2012, 17:27
Ответы с готовыми решениями:

Не могу вставить элемент в second(vector) мультимапа. multimap<string, vector<string>>
#include &lt;iostream&gt; #include &lt;map&gt; #include &lt;vector&gt; #include &lt;algorithm&gt; #include &lt;string&gt;...

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

error LNK2019: ссылка на неразрешенный внешний символ "public: __thiscall Vector<int>::Vector<int>(void)" (?0?$Vector@H@@QAE@XZ) в функции _main
//Vector.h #include &lt;iostream&gt; #include &lt;Windows.h&gt; #include &lt;climits&gt; #include &lt;vector&gt;...

Как можно увеличить размер вектора, который является элементом вектора vector<vector<int>>arr(n, vector <int>)
Написал программу, которая создает вектор 'а' векторов 'b', вектора 'b' содержат 2 числа. Стало...

12
1450 / 787 / 257
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
29.07.2012, 17:40 2
А чем вам алгоритм find не подходит? http://www.cplusplus.com/reference/algorithm/find/
0
28 / 27 / 7
Регистрация: 11.06.2011
Сообщений: 350
29.07.2012, 17:46  [ТС] 3
Цитата Сообщение от yuron_477 Посмотреть сообщение
А чем вам алгоритм find не подходит? http://www.cplusplus.com/reference/algorithm/find/
1. на сколько я понял, он возращает последний элемент, если даже ничего не найдено.
2. Судя по описанию, это та же самая переборка и есть.

В задаче мне нужно найти элемент который отсутствует в контейнере. Чисел примерно ~10000. Соответственно проверка будет идти очень долго....
0
161 / 161 / 68
Регистрация: 23.02.2011
Сообщений: 392
29.07.2012, 17:52 4
C++
1
std::cout << (std::find (myvector.begin(), myvector.end(), myval) != myvector.end() ? "found" : "not found") << std::endl;
0
Жарю без масла
867 / 749 / 225
Регистрация: 13.01.2012
Сообщений: 1,702
29.07.2012, 17:54 5
Цитата Сообщение от admsasha Посмотреть сообщение
на сколько я понял, он возращает последний элемент, если даже ничего не найдено.
прочитайте внимателнее

Цитата Сообщение от admsasha Посмотреть сообщение
Судя по описанию, это та же самая переборка и есть.
если массив не отсортирован - придется перебирать
0
2551 / 1316 / 177
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
29.07.2012, 19:29 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 быстрее обычного перебора.
0
~ Эврика! ~
1253 / 1002 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
29.07.2012, 21:07 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 ниумею компилить.)
0
2551 / 1316 / 177
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
29.07.2012, 21:12 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
0
~ Эврика! ~
1253 / 1002 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
29.07.2012, 21:14 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;
}
Ну если параллелит, тогда да.
0
2551 / 1316 / 177
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
29.07.2012, 21:16 10
Цитата Сообщение от ~OhMyGodSoLong~ Посмотреть сообщение
Ну если параллелит, тогда да.
*soon заменил for на while. Определенно параллелит
0
28 / 27 / 7
Регистрация: 11.06.2011
Сообщений: 350
30.07.2012, 08:58  [ТС] 11
Не знаю почему, но действительно find быстро работает. Всем спасибо. Использую её.
0
Higher
1944 / 1210 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
30.07.2012, 12:25 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;
    }
}
0
554 / 508 / 25
Регистрация: 23.07.2009
Сообщений: 2,359
Записей в блоге: 1
30.07.2012, 12:42 13
или использовать set вместо vector
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.07.2012, 12:42

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

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

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

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

Используя контейнер vector найти минимальный элемент каждой строки
сформировать 2-мерный массив используя контейр вектор найти мин елемент каждой строки удалить макс...


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Опции темы

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