Изменение порядка векторов с использованием вектора индексов

Question

Я хотел бы изменить порядок элементов в векторе, используя другой вектор для указания порядка:

char   A[]     = { 'a', 'b', 'c' };
size_t ORDER[] = { 1, 0, 2 };

vector<char>   vA(A, A + sizeof(A) / sizeof(*A));
vector<size_t> vOrder(ORDER, ORDER + sizeof(ORDER) / sizeof(*ORDER));
<BR>reorder_naive(vA, vOrder);
<BR>// A is now { 'b', 'a', 'c' }

Следующее является неэффективной реализацией, которая требует копирования вектора:

void reorder_naive(vector<char>& vA, const vector<size_t>& vOrder)  
{   
    assert(vA.size() == vOrder.size());  
    vector vCopy = vA; // Can we avoid this?  
    for(int i = 0; i < vOrder.size(); ++i)  
        vA[i] = vCopy[ vOrder[i] ];  
}  

Есть ли более эффективный способ, например, использующий swap ()?

Answer 1

Для итерации по вектору есть O (n) операция. Это своего рода трудно победить.

Answer 2

Ваш код не работает. Вы не можете присвоить vA, и вам нужно использовать параметры шаблона.

vector<char> REORDER(const vector<char>& vA, const vector<size_t>& vOrder)  
{   
    assert(vA.size() == vOrder.size());  
    vector<char> vCopy(vA.size()); 
    for(int i = 0; i < vOrder.size(); ++i)  
        vCopy[i] = vA[ vOrder[i] ];  
    return vA;
} 

Выше немного эффективнее.

Answer 3

Вы могли бы сделать это рекурсивно, я думаю, что-то вроде этого (не проверено, но это дает идею):

// Recursive function
template<typename T>
void REORDER(int oldPosition, vector<T>& vA, 
             const vector<int>& vecNewOrder, vector<bool>& vecVisited)
{
    // Keep a record of the value currently in that position,
    // as well as the position we're moving it to.
    // But don't move it yet, or we'll overwrite whatever's at the next
    // position. Instead, we first move what's at the next position.
    // To guard against loops, we look at vecVisited, and set it to true
    // once we've visited a position.
    T oldVal = vA[oldPosition];
    int newPos = vecNewOrder[oldPosition];
    if (vecVisited[oldPosition])
    {
        // We've hit a loop. Set it and return.
        vA[newPosition] = oldVal;
        return;
    }
    // Guard against loops:
    vecVisited[oldPosition] = true;

    // Recursively re-order the next item in the sequence.
    REORDER(newPos, vA, vecNewOrder, vecVisited);

    // And, after we've set this new value, 
    vA[newPosition] = oldVal;
}

// The "main" function
template<typename T>
void REORDER(vector<T>& vA, const vector<int>& newOrder)
{
    // Initialise vecVisited with false values
    vector<bool> vecVisited(vA.size(), false);

    for (int x = 0; x < vA.size(); x++)
    {
        REORDER(x, vA, newOrder, vecVisited);
    }
}

Конечно, у вас есть накладные расходы на vecVisited. Мысли об этом подходе, кто-нибудь?