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 через смещение от существующего объекта iterator (т. Е. С помощью метода begin() getter), вы можете сделать следующее

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 и не учитывает проверку границ.