Есть переменная int a=5
, которой инициализируем элемент массива int b[3]={a,2,3}
, потом получаем переменную int a1=5
. Имея а1 нужно узнать равна ли она элементу массива, и если равна то, самое важное — получить индекс.
Так вот, проблема в том, что это надо сделать не используя цикл. В .NET есть Array::IndexOf(Array^, Object^)
, есть ли аналог в C++? Может шаблонные классы?
-
2Если и есть такой метод - то он все равно использует цикл.– Алексей Саровский8 мар 2016 в 19:29
-
Дак ведь у вас неупорядоченный массив, каким еще образом можно найти в нем искомый элемент (или вы чего-то недоговариваете)?– StateItPrimitive8 мар 2016 в 19:31
-
Ну возможно, он написан на ассемблере, что даст прирост производительности. А вообще мне кажется, что есть способ нахождения через адреса– Алесандр Вогрик8 мар 2016 в 19:31
-
Глупости. Если подумать, можно доказать, что меньше O(N) не получить– Алексей Саровский8 мар 2016 в 19:33
-
@StateItPrimitive а он и не должен быть упорядоченным, он заполняется в течении выполнения программы . Это важно?– Алесандр Вогрик8 мар 2016 в 19:34
3 ответа
Не используя цикл, можно использовать алгоритм find
из STL (find_if
в данном случае - перебор).
Есть и второй способ без применения циклов - применить рекурсию.
Но вы уверены, что вам нужно именно это? :)
Если вопрос в производительности - то быстрее цикла все равно ничего не будет, O(N) для неупорядоченного массива никак не переплюнуть.
Другое дело, что хранить эти значения можно не в массиве, а в том же unordered_set
и получить свое за O(1)
.
Всем спасибо, решение найдено. Наиболее удачный вариант - std::map
. Возможно он не изменяет О(N), однако, конкретно в моём случае он повысил производительность. Ещё хороший вариант - for(int i = 0; i < count; ++i)// count - размер массива
vector[hwnd[i]] = i;
, но я не много не понял как задавать индекс через HWND. reinterpret_cast
помог, но с ним были другие заморочки. Ещё раз всем спасибо
Предисловие: в комментариях с автором выяснили, зачем ему это, прикладываю ответ
Так как обращение будет частое к массиву, то удобно применить вектор-индикатор. Ограничиваем максимальное значение в массиве MAX_VALUE
и создаем int
-массив размера MAX_VALUE
. На начальном этапе ОДИН РАЗ инициализируем его примерно так:
for(int i = 0; i < count; ++i)// count - размер массива
vector[hwnd[i]] = i;
Теперь чтобы узнать индекс элемента, достаточно обратиться к vector[i]
- это и будет его индекс в массиве hwnd
. Если нужно добавить/удалить значения в hwnd, то соответствующим образом поменять vector
-
-
-
То есть я в
vector
передаю hwnd, который у меня в WM_PAINT пришёл. Но HWND это ж неint
... То есть нормально если его в качестве индекса передать? 8 мар 2016 в 20:19 -
Ох, меня терзают смутные сомнения, что MAX_VALUE либо нельзя будет заранее указать, либо оно будет такой величиной, что... Какой там вообще размер массива? стоит ли того, чтоб заморачиваться? Если это, грубо говоря, сотня - то там поиск будет почти мгновенный, нет?– Harry8 мар 2016 в 20:39
-
@Harry 200 элементов но всё равно долго ишёт. Да МАКС_ВЭЛУЭ нельзя задать, как размер массива 8 мар 2016 в 20:43