// order[i] is new index for element at position, i.e. // current index -> new index mapping // If order has duplicated elements, result is undefined template<class Container> void reorder(Container& container, const std::vector<size_t>& order) { PRECONDITION(container.size() == order.size()); // Is element with original index i already placed to // proper place as described in order std::vector<bool> already_moved(order.size()); for (size_t i = 0; i < order.size(); ++i) { // Current is original index of element currently in container[i] // if order[current] differs from i we send current to // proper position and get new element in container[i] // if order[current] is equal to i, then element is already // in proper position, and no futher moves can be made for(int current = i; !already_moved[current]; current = order[current]) { already_moved[current] = true; // "if" can be simply omitted, with probably a small // performance penalty if (order[current] != i) swap(container[i], container[order[current]]); else break; } } } // Similar to reorder, but order is new index -> old index mapping template<class Container> void reorder_bwd(Container& container, const std::vector<size_t>& order) { std::vector<size_t> fwd_order(order.size()); for (size_t i = 0; i < order.size(); ++i) fwd_order[order[i]] = i; reorder(container, fwd_order); }
Isn't the STLAlgorithmExtensions/ReorderAlgorithm the same as the STLAlgorithmExtensions/PermuteAlgorithm? --People/JeremySiek