Example of an <algorithm>-like version of R's order.

order.cc

// Usage:
// c++ -std=c++11 -o order order.cc
// ./order
//
// A "standard library*"-like implementation of R's order.
// To back-port this to C++98, one would need to
// replace the lambda closures with functors.  But there's no need
// to do such silliness anymore.
//
// The implementation is in terms of sorting iterators and then
// calculating their offsets with respect to the input order.
// This method works for any iterator value_type, even non-copyable/move-only
// types, because the iterators are copyable.  Also, sizeof(iterator) may
// be << sizeof(value_type), so we save memory during the sort.
//
// One non-idiomatic thing that I've done is implemented the standard form 
// in terms of the form taking a custom comparison function.
//
// See documentation of standard form (e.g., w/o custom comparison closure)
// for alternatives that are faster.
//
// * <pedantry> The term STL refers to an early commercial implementation
// by HP/Bell Labs.  It is the basis for most modern implementations,
// but it not a "thing" anymore. </pedantry>

#include <vector>
#include <list>
#include <memory>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <iostream>

template <typename Iterator, typename OutputIterator, typename Comp>
void
order(Iterator beg, Iterator end, OutputIterator out, Comp comp)
/// Overload for custom ordering function
/// \param comp A closure used for ordering. It must compare two
///        elements of type Iterator::value_type.
{
    auto dist = std::distance(beg, end);
    if (dist <= 0)
        return;

    std::vector<Iterator> temp;
    temp.reserve(static_cast<std::size_t>(dist));

    // Must use != and not < to support containers
    // w/o random-access iterators.
    for (Iterator begc = beg; begc != end; ++begc)
        {
            temp.push_back(begc);
        }
    std::sort(temp.begin(), temp.end(),
              [comp](Iterator a, Iterator b) { return comp(*a, *b); });
    for (auto&& i : temp)
        {
            *out++ = std::distance(beg, i);
        }
}

template <typename Iterator, typename OutputIterator>
void
order(Iterator beg, Iterator end, OutputIterator out)
/// \param beg An iterator to start of range.  Any compliant iterator will
/// work.
/// \param end An iterator to end or range.  Any compliant iterator will work.
/// \param out An output iterator.
///
/// The range specified by \a out will be filled such that the largest
/// element in [\a beg, \a end) has value 0 and the smallest has
/// value std::distance(\a beg, \a end) - 1.
///
/// The complexity is 2N + O(NlogN) where N is std::distance(\a beg, \a end).
///
/// If you are just looking for location of min and/or max elements, the
/// std::min_element and std::max_element perform better in both time and
/// in space.
///
/// \note There is no dealing with ties here.  In principle, a custom
/// comparison function (see overload above) can trivially implement
/// various different methods.
{
    // In order to be compatible with bare pointers,
    // we must use iterator traits to deduce value_type.
    using value_type = typename std::iterator_traits<Iterator>::value_type;
    return order(beg, end, out, [](value_type const& a, value_type const& b) {
        return a < b;
    });
}

int
main()
{
    // Fill a vector
    std::vector<int> x{ 5, 4, 1, 7, 3 };

    // Containers for us to store output from order
    std::vector<int> o1, o2, o3, o4;

    // Get default version
    order(std::begin(x), std::end(x), std::back_inserter(o1));

    // Call overload version with closure that is equivalent
    // to R's descending=TRUE option.
    const auto descending = [](const int a, const int b) { return a > b; };
    order(std::begin(x), std::end(x), std::back_inserter(o2), descending);

    // It is compatible with C-style arrays in the usual fashion:
    order(x.data(), x.data() + x.size(), std::back_inserter(o3));
    assert(o1 == o3);
    order(x.data(), x.data() + x.size(), std::back_inserter(o4), descending);
    assert(o2 == o4);

    // And, to prove it is generic, we can use a std::list, too
    std::list<int> y{ 5, 4, 1, 7, 3 };
    std::vector<int> y_order;
    order(y.begin(), y.end(), std::back_inserter(y_order));
    assert(o1 == y_order);

    // You can also output to pointers if you like to
    // make life hard.
    std::unique_ptr<int> up_int(new int[x.size()]);
    order(x.cbegin(), x.cend(), up_int.get());
    assert(std::equal(o1.begin(), o1.end(), up_int.get()));

    // Some lazy output
    for (auto& xi : x)
        {
            std::cout << xi << ' ';
        }
    std::cout << '\n';
    for (auto& oi : o1)
        {
            std::cout << oi << ' ';
        }
    std::cout << '\n';
    for (auto& oi : o2)
        {
            std::cout << oi << ' ';
        }
    std::cout << '\n';
}