# STLAlgorithmExtensions/ReorderAlgorithm

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

Difference (from prior major revision) (no other diffs)

 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

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

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])
{

// "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

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