BOOST WIKI | STLAlgorithmExtensions | RecentChanges | Preferences | Page List | Links List

Reorder is used to rearrange elements in a container with random access.

    // 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>
        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;
                    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>
        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);

-- People/Vladimir Prus

Isn't the STLAlgorithmExtensions/ReorderAlgorithm the same as the STLAlgorithmExtensions/PermuteAlgorithm? --People/JeremySiek

You're absolutely right. I've noticed a function invert_permutation in BGL. What does it do? Could it be used to achive semantics of reorder_bwd? --People/Vladimir Prus
BOOST WIKI | STLAlgorithmExtensions | RecentChanges | Preferences | Page List | Links List
Edit text of this page | View other revisions
Last edited December 6, 2001 7:41 am (diff)
Disclaimer: This site not officially maintained by Boost Developers