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

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

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

Answer 2

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

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

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

Answer 3

Возможно следующее может быть полезным для кого-то в будущем:

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; 
} 

Answer 4

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

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

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