Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Тамика
Котовчанин
918 / 462 / 195
Регистрация: 16.02.2010
Сообщений: 3,264
Записей в блоге: 28
#1

Быстрый поиск элемента - C++

30.01.2014, 16:32. Просмотров 1284. Ответов 22
Метки нет (Все метки)

Добрый день всем! Такой вопрос - есть у меня строка из 64-х чаров. Мне приходит новый чар и нужно найти какой индекс у такого же чара в массиве. Но переберивать ифом все элементы очень затратно(в плане производительности). Есть ли какие-то способы? Можно ли сделать массив, у которых индексы будут чары?
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.01.2014, 16:32
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Быстрый поиск элемента (C++):

Быстрый поиск
Здравствуйте. Нужно выполнить поиск i-го вхождения заданного элемента в...

Быстрый поиск в мапе
Есть мапа вида : std::map<size_t, std::string> Нужно найти элемент меньший или...

Быстрый поиск супернатуральных чисел
Натуральное число будем называть супернатуральным, если в своем десятичном виде...

Быстрый поиск совершенных чисел
Чтобы легко можно было отсылать вопрошающих по этому вопросу, создаю новую...

Быстрый поиск в векторе из pair
Пытаюсь сделать вектор: vector< pair<string, string> > myVect; По идее,...

Быстрый поиск по полям в коллекции
Есть коллекция объектов класса с разными полями. Нужно организовать быстрый...

22
gng
692 / 538 / 160
Регистрация: 08.09.2013
Сообщений: 1,446
30.01.2014, 20:31 #21
Цитата Сообщение от zelim Посмотреть сообщение
Что-то мне подсказывает, что в таком случае мы будем впустую расходовать память
C++
1
2
3
4
5
6
7
8
9
#include <iostream>
#include <map>
using namespace std;
 
main() {
  int s[256];      // даже не char s[256]
  map <char, int> mp[64];
  cout << sizeof (s) << '\t' << sizeof (mp) << '\n';
}
Результат предсказуем
1024 3072
Часть памяти в случае массива чаров, действительно, расходуется впустую, а не на наполненные смыслом "прибомбасы" stl.
По скорости отрыв, думаю, только увеличится.

Добавлено через 18 минут
Цитата Сообщение от zelim Посмотреть сообщение
не должно быть проигрыша в скорости: при компилировании на более-менее вменяемом компиляторе, скорость доступа к элементам контейнера и статического массива - одинакова.
Совершенно не подтверждается практикой. Скорость доступа различается примепно в 4 раза и эта пропорция сохраняется даже при оптимизации -O3.
PS. Я имел в виду массив против вектора при доступе по индексу.
0
MrGluck
Модератор
Эксперт CЭксперт С++
8022 / 4865 / 1425
Регистрация: 29.11.2010
Сообщений: 13,251
30.01.2014, 20:38 #22
А теперь предположим, что нам нужно пробежаться по всем элементам, которые использовались.
Для массива это будет пробег по всем элементам с проверкой, в случае же с контейнером map (хз зачем тут вектор вообще и какой с него профит) это делается обычным пробегом. Вот тут и экономия на будущее.
P.S. gng, сравните доступ в заполненном unordered_map по индексу и в массиве.
0
gng
692 / 538 / 160
Регистрация: 08.09.2013
Сообщений: 1,446
30.01.2014, 21:18 #23
Цитата Сообщение от MrGluck Посмотреть сообщение
gng, сравните доступ в заполненном unordered_map по индексу и в массиве.
Чтение по int индексу
array[10000000] - 0.02s
map - 2.80s
Есть немало примеров, где применение хэшированного списка оправдано, но к задаче ТС это если и относится, то только как дань привычке.
1
30.01.2014, 21:18
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.01.2014, 21:18
Привет! Вот еще темы с решениями:

Быстрый поиск минимального числа
подскажите быстрый алгоритм поиска второго минимального числа в массиве?

Вставка элемента в заданную позицию, удаление элемента по заданной позиции, поиск заданного элемента
Добавить в класс &quot;Односвязный список&quot; следующие функции: вставка элемента в...

Быстрый поиск ip адреса в текстовом файле
Нужно найти конкретный ip-адрес в текстовом файле (он может попасться несколько...

Подскажите быстрый поиск количества интервалов в отрезке
Есть массив H Есть отрезок x+dx. Задача найти количество интервалов на...


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

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

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