تابعی همانند std::sort با قابلیت برگداندن indexs

Question

سلام.

آیا راهی وجود داره که یک تابع همانند std::sort بنویسم که begin و end و lambda بگیره با این تفاوت که indexs جدید یعنی موقعیت جدید هر یک از خانه ها را بر گردونه؟

 

ممنون

Answer 1

میتونین ایندکس به همراه مقادیر رو ّبا استفاده از std::pair  جفت کنید و pair رو مرتب کنین.

template< class RandomAccessIterator,class Compare >
auto sort2(RandomAccessIterator begin,RandomAccessIterator end,Compare cmp) ->
   std::vector<std::pair<std::uint32_t,RandomAccessIterator>>
{
    using valueType=typename std::iterator_traits<RandomAccessIterator>::value_type;
    using Pair=std::pair<std::uint32_t,RandomAccessIterator>;

    std::vector<Pair> index_pair;
    index_pair.reserve(std::distance(begin,end));

    for(uint32_t idx=0;begin!=end;++begin,++idx){
        index_pair.push_back(Pair(idx,begin));
    }

    std::sort( index_pair.begin(),index_pair.end(),[&](const Pair& lhs,const Pair& rhs){
          return cmp(*lhs.second,*rhs.second);
    });

    return index_pair;
}

اجرای زنده 

Answer 2

می تونید توی function یک کلاس جدید از کلاس مدنطرتون مشتق کنید و تو اون کلاس فیلد  Index به عنوان شاخص استفاده کنید.البته اگر کلاس شما move constructor داشته باشه کد زیر perforamce بهتری خواهد داشت.

vs2013
 

#include <functional>
#include <vector>
#include <algorithm>
#include <iostream>
#include <functional>
using namespace std;

struct Foo{
    Foo(int _a,int _b ,int _c):a(_a),b(_b),c(_c){}
    int a,b,c;
};
template<typename T, typename U >
vector<int> sortGetIndexProc(T begin, T end, std::function<bool(const U&p1, const U& p2)> comp_func){
    class UIndex :public U{
    public:
        UIndex(U u, int index) :U(u), index_(index){}
        int index_;
    };
    vector<UIndex> arr;
    size_t size = std::distance(begin, end);
    arr.reserve(size);
    size_t index = 0;
    for (T it = begin; it != end; it++)
        arr.push_back(UIndex(*it, index++));
    sort(arr.begin(), arr.end(), comp_func);
    vector<int> result(size);
    T it = begin;
    for (size_t i = 0; i < size; i++){
        result[i] = arr[i].index_;
        U u(arr[i]);
        (*it++) = u;
    }
    return result;
}
template<typename T, typename U>
vector<int> sortGetIndex(T begin, T end, U comp_func){
    using TV = std::iterator_traits<T>::value_type;
    return sortGetIndexProc<T, TV>(begin, end, comp_func);
}

int main()
{
    std::vector<Foo> arr{Foo(105,1,4),Foo(66,1,6),Foo(11,1,5,),Foo(44,5,6)};
    vector<int> indexs = sortGetIndex(arr.begin(), arr.end(), [](const Foo& f1, const Foo& f2){return f2.b > f1.b; });
    for (auto& index :indexs)
        cout << index << endl;
    return 0;
}

 

یک راه حل ساده دیگر:

template <typename T>
vector<size_t> sortIndexes(const vector<T> &v) {

	auto vv = v;
	vector<size_t> indexs(v.size());
	iota(indexs.begin(), indexs.end(), 0);

	sort(indexs.begin(), indexs.end(),[&vv](size_t i1, size_t i2) {
		return vv[i1] < vv[i2]; 
	});

	return indexs;
}