c ++: выберите подмножество std :: vector на основе предварительно определенных индексов элементов

Question

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

e.g std::vector<String> Test = { "A", "B", "C", "D", "E"}

std::vector<int> SelectionV = {1,2,5}

Result = {"A", "B", "E"}

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

Альтернатива, которую я тоже рассматриваю, но опять же неуверенная в эффективном методе - это ...

Поскольку объект Test заполнен(в моем случае это объект, определенный третьей стороной), это результат одного прохода с использованием итератора (прямой доступ к элементу невозможен).Мне было интересно, если вместо этого можно добавить только элементы вектора теста, которые появляются в счетчике, определенном в SelectionV

например

int count = 0

for (Iterator.begin, Iterator.end(), Iterator++) {
    if (count is a number contained in selectionV)
        add to Test
}

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

Любая помощь очень ценится.

Answer 1

Вы также можете использовать стандартную библиотеку:

std::vector<std::string> Result(SelectionV.size(), 0);

std::transform(SelectionV.begin(), SelectionV.end(), Result.begin(), [Test](size_t pos) {return Test[pos];});

Answer 2

• Это зависит от размера Test и размера SelectionV (в процентах от Test), а также от того, повторяются или нет элементы в SelectionV. Вы могли бы потенциально оптимизировать, вычислив Not SelectionV вместо.
• Обратите внимание, что в вашем примере, поскольку SelectionV является индексом, а не значением, поиск уже O (1) быстрый (это уже огромный плюс).
• Если Test и SelectionV не изменяются, и если они большие, вы также можете разделить SelectionV на n потоков , и каждый поток независимо ищет значения в Test и затем объедините отдельные результаты позже (не в отличие от карты-уменьшить). Недостатком может быть потеря попаданий в кэш процессора.
• При повторных вызовах вы можете принять разницу между вашим старым SelectionV и новым SelectionV и использовать это значение. Этот тип оптимизации кэша будет хорошо работать при небольшом количестве изменений между итерациями.

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

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

Answer 3

Вы можете отсортировать вектор SelectionV по возрастанию порядка, а затем переписать цикл for примерно так:

int index = 0, nextInSelectionV = 0;
for (Iterator.begin; nextInSelectionV < SelectionV.lengh() && Iterator.end(); Iterator++) {
    if (index == SelectionV[nextInSelectionV]) {
        add to Test
        nextInSelectionV++;
    }
    index++;
}

Answer 4

Возможно, в будущем кому-то может пригодиться:

template<typename T>
T vector_select(const std::vector<T>& vector, const std::size_t index)
{
  assert(index < vector.size());  
  return vector[index];
}

template<typename T>
class VectorSelector
{
public:
  VectorSelector(const std::vector<T>& v) : _v(&v) { }
  T operator()(const std::size_t index){ return vector_select(*_v, index); }
private:
  const std::vector<T>* _v;

};

template<typename T>
std::vector<T> vector_select(const std::vector<T>& vector,
                             const std::vector<std::size_t>& index)
{
  assert(*std::max_element(index.begin(), index.end()) < vector.size());
  std::vector<T> out(index.size());
  std::transform(index.begin(), index.end(), out.begin(),
                 VectorSelector<T>(vector));
  return out;
}