Sign in to follow this  
WiredCat

sort std::vector<int> but not just like that (that would be too easy)

Recommended Posts

i have two vectors

 

std::vector<int> PersonID;
std::vector<int> HitRatio;
 
 
now i would like to sort HitRatio but using std::sort (never used it anyway) will sort only HitRatio but PersonID[index] corresponds to HitRatio[index] so whenever i sort HitRatio PersonID needs to be changed too. Since im lazy i wonder if theres a function for that.

Share this post


Link to post
Share on other sites
You can find "zip" utilities that form a tuple of iterators to multiple ranges, and then sort on that with a custom predicate. Something like this exists in my code for instance:

array_view<DrawID> ids;
array_view<SpriteTranform> transforms;
array_view<Texture> textures;
array_view<int> atlasIndices;

sort(zip(ids, transforms, textures, atlasIndices), [](auto& lhs, auto& rhs){ return get<0>(left) < get<0>(right); });
The zip function forms a range of tuple of references. The predicate sorts on the first element, which is the draw ID. The internal swap calls of the sort algorithm swap the tuples of references, which swaps all the referenced data. The range (effectively a pair of iterators) supports the necessary iteration semantics sort requires, as in this case the zip range is random access because all the input ranges are range access.

You can find versions of such functions around the Internet. Boost has copies, if you dare to include Boost. Ranges-v3 has it. There's been other various versions posted online for years.

If you're just got the one case of needing this, writing something locally is easy enough too. Just make a custom small iterator, along the lines of (untested):

struct zip_iter
{
  int* _first = nullptr;
  int* _second = nullptr;

public:
  using iterator_category = random_access_iterator_tag;
  using value_type = pair<int, int>;
  using reference = pair<int&, int&>;
  using difference_type = ptrdiff_t;

  zip_iter() = default;
  zip_iter(int* a, int* b) : _first(a), _second(b) {}

  zip_iterator& operator++() { ++_first; ++second; return *this; }

  reference operator*() { return {*_first, *_second}; }

  // only need to check the first pointer since the two should be synchronized
  bool operator==(zip_iter rhs) const { return _first == rhs._first; }
  bool operator!=(zip_iter rhs) const { return _first != rhs._first; }

  // add all the other crap required at http://en.cppreference.com/w/cpp/concept/RandomAccessIterator
};

Share this post


Link to post
Share on other sites

i wonder if i wrote that properly.


inline void SortTwoVectorsByOne(std::vector<int> & tosort, std::vector<int> & second)
{
int i,j;
	 int len = tosort.size();

	for (i = 0; 	i < len; i++)
	for (j = 0; 	j < len-1; j++)
		if ( tosort[j] > tosort[j+1] )
		{
 int tmp = tosort[j+1];
 tosort[j+1] = tosort[j];
 tosort[j] = tmp;

 tmp = second[j+1];
 second[j+1] = second[j];
 second[j] = tmp;
		}

}

and then call it by

std::vector<int> PersonID;
std::vector<int> HitRatio;
SortTwoVectorsByOne(HitRatio,PersonID);

code seems to work fine but i wonder if i dont have some sort of bug here with 

nline void SortTwoVectorsByOne(std::vector<int> & tosort, std::vector<int> & second)

and

if ( tosort[j] > tosort[j+1] )

and

int tmp = tosort[j+1];

and

tosort[j+1] = tosort[j];
Edited by WiredCat

Share this post


Link to post
Share on other sites

Do you really need them sorted, or do you just need to go through them in a sorted order?

 

In the latter case, you could just generate an index array and sort just that...

    std::vector<int> order;
    order.reserve(PersonID.size());
    for(int i=0; i<PersonID.size(); i++)
        order.push_back(i);

    std::sort(begin(order), end(order), [&](int a, int b){
        return HitRatio[a] < HitRatio[b];
    });

    for (int idx : order) {
        std::cout << PersonID[idx] << ": " << HitRatio[idx] << std::endl;
    }

Or you could abuse std::multimap since it automatically sorts itself...

    std::multimap<int,int> hack;
    for (int i=0; i<PersonID.size(); i++)
        hack.emplace(HitRatio[i], PersonID[i]);
    
    for (const auto &hit_person : hack) {
        std::cout << hit_person.second << ": " << hit_person.first << std::endl;
    }

Or you could make a struct for your hitratio records, even a dummy one just inside your function that needs it...

    struct HitRatioRecord {
        int id;
        int ratio;
        bool operator< (const HitRatioRecord &other) const {
            return ratio < other.ratio;
        }
    };
    
    std::vector<HitRatioRecord> hrr;
    for (int i=0; i<PersonID.size(); i++)
        hrr.push_back({ PersonID[i], HitRatio[i] });
    
    std::sort(begin(hrr), end(hrr));
    
    for (const auto &v : hrr) {
        std::cout << v.id << ": " << v.ratio << std::endl;
    }

I could come up with a dozen more ways to do this but I suppose I'll stop here :)

 

EDIT: const auto & instead of just auto to avoid unnecessary temporary object copies...

Edited by mzbear

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this