C++ получить индекс элемента массива по значению

Question

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

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

Answer 1

Поскольку элементы отсортированы, вы можете использовать бинарный поиск, чтобы найти соответствующий элемент. Стандартная библиотека 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, так и обычные массивы.

Answer 2

Если вы хотите связать значение с индексом и быстро найти индекс, вы можете использовать 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 сравнения Джеймса двоичного кода поиска с помощью линейного поиска и с помощью unordered_map для поиска, все на векторе:

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

EDIT: max_load_factor() для неупорядоченной карты 1, поэтому не должно быть никаких столкновений. Разница в производительности между бинарным поиском и хэш-таблицей для очень больших векторов, по-видимому, связана с кешированием и варьируется в зависимости от шаблона поиска в эталонном тесте.

Choosing between std::map and std::unordered_map рассказывает о различии между упорядоченными и неупорядоченными картами.