Вопрос по c++, indexing, stl, arrays – C ++ получить индекс элемента массива по значению

6

До сих пор я сохранял массив в векторе, а затем перебирал вектор, чтобы найти соответствующий элемент, а затем возвращал индекс.

Есть ли более быстрый способ сделать это в C ++? Структура STL, которую я использую для хранения массива, для меня действительно не имеет значения (она не обязательно должна быть вектором). Мой массив также уникален (без повторяющихся элементов) и упорядочен (например, список дат на будущее).

Ваш Ответ

2   ответа
7

вы можете использовать двоичный поиск, чтобы найти соответствующий элемент. Стандартная библиотека C ++ имеетstd::lower_bound Алгоритм, который может быть использован для этой цели. Я бы порекомендовал обернуть его в свой собственный алгоритм двоичного поиска, для ясности и простоты:

/// Performs a binary search for an element
///
/// The range `[first, last)` must be ordered via `comparer`.  If `value` is
/// found in the range, an iterator to the first element comparing equal to
/// `value` will be returned; if `value` is not found in the range, `last` is
/// returned.
template <typename RandomAccessIterator, typename Value, typename Comparer>
auto binary_search(RandomAccessIterator const  first,
                   RandomAccessIterator const  last,
                   Value                const& value,
                   Comparer                    comparer) -> RandomAccessIterator
{
    RandomAccessIterator it(std::lower_bound(first, last, value, comparer));
    if (it == last || comparer(*it, value) || comparer(value, *it))
        return last;

    return it;
}

(Стандартная библиотека C ++ имеетstd::binary_search, но возвращаетbool: true если диапазон содержит элемент,false иначе. Это бесполезно, если вам нужен итератор для элемента.)

Если у вас есть итератор для элемента, вы можете использоватьstd::distance алгоритм расчета индекса элемента в диапазоне.

Оба этих алгоритма одинаково хорошо работают с любой последовательностью произвольного доступа, включая обаstd::vector и обычные массивы.

@Ulterior: Да, это копия-паста из моей библиотеки CxxReflect. Увидетьalgorithm.hpp.
Почему бы это не скомпилировать? Я не вижу доказательств ошибки.
это даже компилируется?
@ Внешне вам понадобится компилятор с некоторой поддержкой C ++ 11, хотя алгоритм может быть легко написан на C ++ 03.
Спасибо, я все еще в банкомате C99
7

вы можете использоватьstd::map или жеstd::unordered_map, Вы также можете комбинировать их с другими структурами данных (например,std::list или жеstd::vector) в зависимости от других операций, которые вы хотите выполнить с данными.

Например, при создании вектора мы также создаем таблицу соответствия:

vector<int> test(test_size);
unordered_map<int, size_t> lookup;
int value = 0;
for(size_t index = 0; index < test_size; ++index)
{
    test[index] = value;
    lookup[value] = index;
    value += rand()%100+1;
}

Теперь для поиска индекса вы просто:

size_t index = lookup[find_value];

Использование структуры данных на основе хеш-таблицы (например, unordered_map) является довольно классическим компромиссом между пространством и временем и может превзойти выполнение двоичного поиска для такого рода «обратного». операция поиска, когда вам нужно сделать много поисков. Другое преимущество заключается в том, что он также работает, когда вектор не отсортирован.

Для удовольствия :-) Я провел быстрый тест в VS2012RC, сравнивая James & apos; двоичный код поиска с линейным поиском и с использованием unordered_map для поиска, все по вектору: Performance of various find index methods

До ~ 50000 элементов unordered_set значительно (x3-4) превосходит двоичный поиск, который демонстрирует ожидаемое поведение O (log N), несколько неожиданный результат состоит в том, что unordered_map теряет свое поведение O (1) после 10000 элементов, предположительно из-за хеш-коллизии, возможно, проблема с реализацией.

РЕДАКТИРОВАТЬ: max_load_factor () для неупорядоченной карты равен 1, поэтому не должно быть никаких коллизий. Разница в производительности между двоичным поиском и хэш-таблицей для очень больших векторов, по-видимому, связана с кэшированием и варьируется в зависимости от шаблона поиска в тесте.

Выбор между std :: map и std :: unordered_map говорит о разнице между упорядоченными и неупорядоченными картами.

Похожие вопросы