C++: эффективное извлечение подмножества элементов из типа данных, доступ к которому возможен только через итератор

Question

У меня есть определенная пользователем структура данных пользователя (для работы с сетками). Единственный открытый доступ к базовым элементам - через итератор (прямой доступ к элементу «x» невозможен).

У меня также есть список индексов элементов, хранящихся в виде std :: vector, которые я хочу извлечь, где я буду определять первый элемент, который посетил итератор, как index = 1, index = 2 и т. Д. Эффективно я я хочу извлечь подмножество элементов на основе индекса.

Я буду делать это много раз (сетка, из которой я беру выборку, будет постоянно меняться, и я хочу сохранить выборку по тем же самым показателям), поэтому мне нужно как можно эффективнее использовать метод.

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

Любые предложения были бы очень признательны.

Answer 1

Если вектор отсортирован заранее, вам нужно будет только итерации один раз. Однако вам нужно будет поддерживать счет в стороннем итераторе. Попробуйте вариант кода ниже. (Примечание. Этот код отсутствует ошибка и проверки границ)

iterator elementIt; 
int elementPos = 0; 

vector<int> extractElements; 
for (vector<int>::iterator extractIt = extractElements.begin(); extractIt != extractElements.end(); ++extractIt) 
{ 
    while (elementPos < *extractIt) 
    { 
    ++elementIt; 
    ++elementPos; 
    } 

    doSomething(elementIt); 
} 

Answer 2

Предполагая, что вы можете получить доступ к открытым iterator объекта (т.е. с помощью метода в begin() геттера) с помощью смещения от существующего iterator объекта, вы могли бы быть в состоянии сделать следующий

DataStructure_type::iterator iter = dataStructureVar.begin(); 
elementValue = *(iter + idx); 

Где DataStructure_type является типом итератора структуры данных, и idx является индексом элемента которой вы хотите. Тогда, извлекая подмножество элементов из структуры данных становится таким же простым, как:

DataStructure_type::iterator subsetStartIter = dataStructureVar.begin() + subsetStartIdx; 
DataStructure_type::iterator subsetEndIter = dataStructureVar.begin() + subsetEndIdx; 
std::vector<Element_type> subsetCollection(subsetStartIter, subsetEndIter); 

Но это могло бы быть более эффективным, если вы работать непосредственно на исходном множестве iterator объектов в коде, а не копировать их в промежуточном контейнер - это позволит исключить необходимость копирования подмножества в std::vector<> ...

Обратите внимание, что этот ответ делают некоторые предположения о реализации выставленного iterator объекта в DataStructure_type и не учитывает граничную проверку.