Как получить ранг элемента в векторе в C ++

Question

Мне нужно получить ранг (позиционный индекс + 1) элемента для контейнеров в C ++, таких как vector или list. Есть ли удобный способ сделать это? Я мог бы сделать тестирование на основе nth_element, чтобы найти ранг. Или я мог бы сортировать и делать бинарный поиск, чтобы найти ранг. Но все это не кажется очень эффективным в худшем случае. Я хотел бы получить сложность O (lgn) и по возможности сделать с алгоритмами STL.

Answer 1

Если ваш контейнер имеет итераторы произвольного доступа (например, вектор) и отсортирован, вы можете использовать алгоритм std::lower_bound() для получения индекса элементов со сложностью O (log n). Например:

std::vector<int> v({10,20,30,30,20,10,10,20});
std::sort(v.begin(), v.end());
auto iter = std::lower_bound(v.begin(), v.end(), 20);
std::cout << "index " << int(iter - v.begin()) << std::endl;

(я использую синтаксис C ++ 11 для краткости кода, но вы должны понять).

Обратите внимание, что вы можете вставлять элементы в вектор отсортированным образом, поэтому вам не нужно выполнять сортировку перед поиском индекса.

Answer 2

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

Answer 3

это может быть немного неопрятно.

Вы можете использовать тот факт, что элементы в векторах непрерывны в памяти.

так что вам нужно сделать

1) получить адрес итератора интересующего элемента

2) вычтите с помощью vector.begin (), чтобы получить общую память

3) разделить на размер одного элемента

это должно дать вам должность (или звание).

это предполагает, что элементы имеют фиксированный размер.