Форум программистов, компьютерный форум, киберфорум
Visual C++
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.72/25: Рейтинг темы: голосов - 25, средняя оценка - 4.72
 Аватар для Kabak
159 / 145 / 14
Регистрация: 03.02.2012
Сообщений: 788
Записей в блоге: 1

Ускоренный поиск текста в массиве

11.02.2022, 10:57. Показов 4920. Ответов 20
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Здравствуйте

Есть такие вот конструкции.

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
  
struct _Definitions
{
    std::string Name;
    std::string Value;
};
 
 
vector < _Definitions* > Definitions;
.
.
.
 
// Поиск наличия по имени в массиве 
int File_process::Find_Definition ( std::string Search )
{
    int Size = (int)Definitions.size();
 
 
        for ( int i = 0; i < Size; ++i )
        {
            if ( Definitions [i]->Name == Search )
            {
                return ( i );
            }
        }
        return ( -1 );
}
1) Как организовать ускоренный поиск нужной строки в таком массиве ?

2) Можно ли разбить этот массив на мысленные куски, например, побив пополам и запустить потоки для поиска в каждом куске ?
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
11.02.2022, 10:57
Ответы с готовыми решениями:

Ускоренный поиск, основанный на использовании единого справочника
Необходим пример кода ускоренного поиска с использованием единого справочника. Погуглил, нашёл только задания и теорию, а программной...

Ускоренный поиск, основанный на использовании общего справочника
подскажите как создавать этот справочник, если можно то покажите на примере

Поиск текста в массиве строк String
Доброго времени суток помогите пожалуйста, нужно найти в тексте строку в которой содержится слово ''Тема: '' и записать эту строку в...

20
фрилансер
 Аватар для Алексей1153
6465 / 5679 / 1131
Регистрация: 11.10.2019
Сообщений: 15,122
11.02.2022, 12:13
Kabak, а поиск по имени или по значению?

Добавлено через 56 секунд
если только по имени, можно хранить в std::unordered_set , либо в векторе поддерживать порядок по возрастанию и использовать двоичный поиск

Добавлено через 31 секунду
и хранить лучше не указатели, а экземпляры
0
 Аватар для Kabak
159 / 145 / 14
Регистрация: 03.02.2012
Сообщений: 788
Записей в блоге: 1
11.02.2022, 12:24  [ТС]
Поиск по имени

для _Definitions* я создаю указатели с помощью new

std::vector хранит всё в стеке или в куче ?

Добавлено через 8 минут
Я пытался создать потоки для поиска в таком массиве. Создал, потоки отрабатывают, но только в DEBUG сборке. В Release почему-то находит то, чего на самом деле не существует.

Потоки только читают. ( массив на момент поиска в нём полностью сформирован и никто не пишет в него ) Потоки обращаются к разным блокам элементов и никогда не обращаются к одиному и тому же елементу одновременно.
0
фрилансер
 Аватар для Алексей1153
6465 / 5679 / 1131
Регистрация: 11.10.2019
Сообщений: 15,122
11.02.2022, 12:45
Лучший ответ Сообщение было отмечено Kabak как решение

Решение

Цитата Сообщение от Kabak Посмотреть сообщение
Поиск по имени
тогда std::unordered_set отлично подойдёт. Искать будет мгновенно. Заполняться будет чуть подольше, чем вектор (если это некритично, то не обращать внимания)

Не по теме:

Цитата Сообщение от Kabak Посмотреть сообщение
std::vector хранит всё в стеке или в куче ?
в куче

Цитата Сообщение от Kabak Посмотреть сообщение
Я пытался создать потоки для поиска в таком массиве
у STL-функций поиска есть версии, которые уже со встроенным многопоточным выполнением, например https://en.cppreference.com/w/... lue%20)%3B
но, конечно же, всё равно придётся учитывать, если контейнер используется ещё и в другом потоке.



Добавлено через 13 минут
Kabak,

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
#include <unordered_set>
#include <iostream>
#include <string>
 
struct s_Definitions
{
    std::string Name;
    std::string Value;
    
    struct std__hash
    {
        size_t operator()(const s_Definitions& item)const noexcept
        {
            return std::hash<std::string>{}(item.Name);
        }
    };
    
    struct std__equalto
    {
        bool operator()(const s_Definitions& l, const s_Definitions& r)const noexcept
        {
            return l.Name==r.Name;
        }
    };
};
 
int main()
{
    std::unordered_set<s_Definitions, s_Definitions::std__hash,s_Definitions::std__equalto> list
    {
        {"Name1","Value1"},
        {"Name2","Value2"},
        {"Name3","Value3"},
        {"Name4","Value4"},
    };
    
    if(auto it=list.find(s_Definitions{"Name3"}); it!=list.end())
    {
        std::cout<<it->Value;
    }
}
1
 Аватар для Kabak
159 / 145 / 14
Регистрация: 03.02.2012
Сообщений: 788
Записей в блоге: 1
11.02.2022, 13:06  [ТС]
А как в std::unordered_set искать по конкретному полю Name ? у меня то не одно поле std::string Name; нужно хранить.

C++
1
2
3
4
5
struct _Definitions
{
    std::string Name;
    std::string Value;
};
0
фрилансер
 Аватар для Алексей1153
6465 / 5679 / 1131
Регистрация: 11.10.2019
Сообщений: 15,122
11.02.2022, 13:08
Kabak, в коде выше есть пример поиска по имени

Цитата Сообщение от Алексей1153 Посмотреть сообщение
if(auto it=list.find(s_Definitions{"Name3"}); it!=list.end())
    {
        std::cout<<it->Value;
    }
0
 Аватар для Kabak
159 / 145 / 14
Регистрация: 03.02.2012
Сообщений: 788
Записей в блоге: 1
11.02.2022, 13:36  [ТС]
А как получить индекс найденного элемента в массиве ?
0
фрилансер
 Аватар для Алексей1153
6465 / 5679 / 1131
Регистрация: 11.10.2019
Сообщений: 15,122
11.02.2022, 13:51
Цитата Сообщение от Kabak Посмотреть сообщение
как получить индекс
имя - это и есть индекс

Добавлено через 48 секунд
и это не массив, а хеш-контейнер

Добавлено через 19 секунд
если таки нужен именно массив, придётся держать упорядоченный вектор
0
 Аватар для Kabak
159 / 145 / 14
Регистрация: 03.02.2012
Сообщений: 788
Записей в блоге: 1
11.02.2022, 14:02  [ТС]
у меня тут всё немного сложнее. я для просты привёл пример обрезанной структуры которая используется разными классами и похоже этим всё усложнил.


Я пишу что-то похожее на компилятор С в общем, мне нужно аннализировать текстовые файлы где размещены множественные #define

Соответственно, мне нужно все эти #define собрать в кучу и потом по мере появления нового #define, сравнивать и искать по имени в массиве уже сохранённых на предмет совпадений. Чтобы в массиве не было одинаковых имён.

Мне нужно каким-то образом получать индекс элемента в массиве, если он был найден. И потом где-нибудь в другом месте по этому индексу извлекать нужный элемент и что-то дальше делать со структурой привязанной к этому индексу. т.е. имя переменной из массива не подходит в качестве индекса.

Как всё это лучше организовать? vector < struct > меня вполне устраивает, но мне нужен быстрый поиск в этом векторе по конкретному СИМВОЛЬНОМУ полю в struct.

Благодарю , что удиляете мне время.
0
фрилансер
 Аватар для Алексей1153
6465 / 5679 / 1131
Регистрация: 11.10.2019
Сообщений: 15,122
11.02.2022, 14:11
Цитата Сообщение от Kabak Посмотреть сообщение
Соответственно, мне нужно все эти #define собрать в кучу и потом по мере появления нового #define, сравнивать и искать по имени в массиве уже сохранённых на предмет совпадений. Чтобы в массиве не было одинаковых имён.
код из примера всё это умеет - хранить уникальные имена без повторений, быстро искать (find) по имени.
Когда нужно вставить новый элемент, ищем (find) по имени - если уже такое есть, говорим юзеру ошибку. Если нету, добавляем элемент (insert или operator [] ) в контейнер

с вектором всё то же самое можно провернуть, только добавится ручной работы (хотя, можно сделать свой класс-контейнер на основе вектора, и все действия описать в виде методов). Хранить элемент нужно будет упорядоченно, при добавлении - искать место для вставки и вставлять так, чтобы порядок не нарушался и не было повторов (std::lower_bound и пара проверок), поиск - двоичный (std::lower_bound или std::binary_search)

с хешем плюс в том, что уже всё готово к использованию + быстрый поиск
с вектором плюс в более скромном потреблении памяти
0
 Аватар для Kabak
159 / 145 / 14
Регистрация: 03.02.2012
Сообщений: 788
Записей в блоге: 1
16.02.2022, 21:13  [ТС]
C++
1
2
3
4
    if(auto it=list.find(s_Definitions{"Name3"}); it!=list.end())
    {
        std::cout<<it->Value;
    }
Почему-то компилятор не принимает такую форму записи.

ругается, что it должно быть bool или конвертироваться в bool

Добавлено через 2 минуты
https://i.gyazo.com/4142d60108... 2db8cf.png
0
фрилансер
 Аватар для Алексей1153
6465 / 5679 / 1131
Регистрация: 11.10.2019
Сообщений: 15,122
16.02.2022, 21:18
Kabak, нужно включить стандарт C++17, либо разнести по строкам:

C++
1
2
3
4
5
    auto it=list.find(s_Definitions{"Name3"});
    if(it!=list.end())
    {
        std::cout<<it->Value;
    }
0
 Аватар для Kabak
159 / 145 / 14
Регистрация: 03.02.2012
Сообщений: 788
Записей в блоге: 1
17.02.2022, 09:55  [ТС]
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
51
52
53
54
55
56
#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>
 
using namespace std;
 
 
struct _Reserved_Words
{
    string Name;
    int Value;
 
    struct std__hash
    {
        size_t operator()(const _Reserved_Words& item)const noexcept
        {
            return std::hash<std::string>{}(item.Name);
        }
    };
 
    struct std__equalto
    {
        bool operator()(const _Reserved_Words& l, const _Reserved_Words& r)const noexcept
        {
            return l.Name==r.Name;
        }
    };
};
 
 
int main()
{
 
    unordered_set < _Reserved_Words > Reserved_Words;
 
    Reserved_Words.insert ( { "one", 1 } );
    Reserved_Words.insert ( { "two", 2 } );
    Reserved_Words.insert ( { "three", 3 } );
    Reserved_Words.insert ( { "four", 4 } );
    Reserved_Words.insert ( { "five", 5 } );
    Reserved_Words.insert ( { "six", 6 } );
 
    std::cout << "Hello World!\n";
 
    string Test = "four";
 
    auto it = Reserved_Words.find ( _Reserved_Words{ Test } );
 
    if ( it != Reserved_Words.end () )
    {
        cout << it->Value;
    }
 
 
}

Получаю ошибку : error C2280: 'std::_Uhash_compare<_Kty,_Hasher,_Keyeq >::_Uhash_compare(const std::_Uhash_compare<_Kty,_Hasher,_Keyeq> &)': attempting to reference a deleted function

Добавлено через 1 минуту
как организовать быстрый поиск по конкретному полю типа string из структуры или класса ?

Добавлено через 3 минуты
Когда используется простой тип, а не структура , то проблем с поиском нет. Я понимаю, что я что-то не понимаю, если у вас есть время, разъясните мне , пожалуйста.

нашёл ещё материал, но там тоже не всё гладко с синтаксисом
0
фрилансер
 Аватар для Алексей1153
6465 / 5679 / 1131
Регистрация: 11.10.2019
Сообщений: 15,122
17.02.2022, 10:00
Kabak, обрати внимание, как у меня объявляется тип контейнера
Цитата Сообщение от Алексей1153 Посмотреть сообщение
std::unordered_set<s_Definitions, s_Definitions::std__hash,s_Definitions:: std__equalto> list

Не по теме:

Цитата Сообщение от Kabak Посмотреть сообщение
using namespace std;
а это лучше забыть и не использовать

1
 Аватар для Kabak
159 / 145 / 14
Регистрация: 03.02.2012
Сообщений: 788
Записей в блоге: 1
17.02.2022, 10:13  [ТС]
Благодарю вас за помощь, Алексей1153. Работает.

А есть ли где-то что-то почитать по этой теме, но не в банальной реализации ? ( искал в интернете - глухо )
0
 Аватар для Kabak
159 / 145 / 14
Регистрация: 03.02.2012
Сообщений: 788
Записей в блоге: 1
17.02.2022, 10:24  [ТС]
Получается, что работает только с auto и при явном задеании типа для переменной it не работает. При этом IDE намекает на ошибку подчёркивая строку
Миниатюры
Ускоренный поиск текста в массиве  
0
фрилансер
 Аватар для Алексей1153
6465 / 5679 / 1131
Регистрация: 11.10.2019
Сообщений: 15,122
17.02.2022, 10:33
Цитата Сообщение от Kabak Посмотреть сообщение
А есть ли где-то что-то почитать по этой теме
думаю, что есть, но я не подскажу, так как не знаю нужную литературу.

Цитата Сообщение от Kabak Посмотреть сообщение
при явном задеании типа для переменной it не работает
будет тоже работать, только нужно правильно вывести. Для этого и изобрели auto, чтобы этой фигнёй не страдать

Цитата Сообщение от Kabak Посмотреть сообщение
IDE намекает на ошибку
это не ошибка, а предупреждение насчёт _Reserved_Words{ Test }. Можно игнорировать в данном случае
0
 Аватар для Kabak
159 / 145 / 14
Регистрация: 03.02.2012
Сообщений: 788
Записей в блоге: 1
23.03.2022, 13:00  [ТС]
Подскажите ,

Как отказаться от auto и заменить на явный тип ? Почему-то не прокатывает явное указание типа _Reserved_Words

C++
1
auto it = Reserved_Words.find ( _Reserved_Words{ Test } );
нужно поместить внутрь switch и VS2019 не пропускает auto в том месте где мне нужно.
0
фрилансер
 Аватар для Алексей1153
6465 / 5679 / 1131
Регистрация: 11.10.2019
Сообщений: 15,122
23.03.2022, 13:08
Kabak, так это ж итератор

C++
1
2
3
4
5
6
7
8
    auto it = Reserved_Words.find ( _Reserved_Words{ Test } );
    if ( it != Reserved_Words.end () )
    {
        switch(it->Value)
        {
            ...
        }
    }
0
 Аватар для Kabak
159 / 145 / 14
Регистрация: 03.02.2012
Сообщений: 788
Записей в блоге: 1
23.03.2022, 14:00  [ТС]
Так не получается , потому, что значение Test вычисляется индеивидуально внутри каждого case

Добавлено через 16 минут
я пытаюсь заменить конструкцию с vector на unordered_set в существующем и рабочем коде для ускорения поиска элемента.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
23.03.2022, 14:00
Помогаю со студенческими работами здесь

Поиск текста в массиве DOC-файлов
Уважаемые программисты! Очень нужна программа, которая решает такую задачу: Исходные данные: массив док-файлов с названием из...

Поиск ячейки в массиве данных по части текста
Вот такая вот незадача, или задачка =) Есть массив смешанных (цифры, текст) данных. 5 столбцов 5 строк. Нужно найти ячейку которая...

Поиск текста в массиве DOC (с логическими операторами), переименование, копирование
Уважаемые программисты! Очень нужен макроc (скрипт) или программа, который решает такую задачу: Исходные данные: массив...

Ускоренный градиентный спуск
народ спасайте не могу понять почему не пашет и еще бы график сюда прикрутить чтоб видны были итеррации, ну как спуск происходит там...

Ускоренный алгоритм Брезенхема
Подскажите пожалуйста, модифицированный алгоритм Брезенхема по этой ссылки: http://students.uni-vologda.ac.ru/pages/pm99/vvv/ellipse.htm и...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Автозаполнение реквизита при выборе элемента справочника
Maks 27.03.2026
Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .
Сумматор с применением элементов трёх состояний.
Hrethgir 26.03.2026
Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа
Maks 26.03.2026
Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .
Команды формы и диалоговое окно
Maks 26.03.2026
1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .
Кому нужен AOT?
DevAlt 26.03.2026
Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .
Отправка уведомления на почту при изменении наименования справочника
Maks 24.03.2026
Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .
модель ЗдравоСохранения 5. Меньше увольнений- больше дохода!
anaschu 24.03.2026
Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .
Midnight Chicago Blues
kumehtar 24.03.2026
Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru