Member Avatar for daviddoria
daviddoria 334 Posting Virtuoso

I've seen a few questions about this floating around here (mostly from me :) ) but I finally got this is into a nice working form - maybe it will be useful for someone.

It is called like this:

void TestParallelSort()
{
	vector<double> Numbers;
	Numbers.push_back(3.4);
	Numbers.push_back(4.5);
	Numbers.push_back(1.2);
	
	vector<string> Names;
	Names.push_back("David");
	Names.push_back("Hayley");
	Names.push_back("Joe");

	Tools::ParallelSort(Numbers, Names);
		
	/*
	output should be
	1.2 Joe
	3.4 David
	4.5 Hayley
	*/
	
	//Tools::OutputVector(Indices);
	Tools::OutputVector(Numbers);
	Tools::OutputVector(Names);
}

And here is the code:

template <typename T>
	struct NumberedItem
	{
		unsigned int index;
		T Item;
	};

	template <typename T>
	bool operator<(NumberedItem<T> NI1, NumberedItem<T> NI2)
	{
		//return NI1.index < NI2.index;
		return NI1.Item < NI2.Item;
	}
	
	template <class T, class S>
	void ParallelSort(vector<T> &Things1, vector<S> &Things2)
	{
		//this function sorts Things1 and reorders Things2 so that it is in the same order as the sorted Things1
		assert(Things1.size() == Things2.size());
		
		unsigned int NumThings = Things1.size();
		
		//create the sortable objects
		vector<NumberedItem<T> > Pairs(NumThings);
		for(unsigned int i = 0; i < NumThings; i++)
		{
			Pairs[i].index = i;
			Pairs[i].Item = Things1[i];
		}
		
		sort(Pairs.begin(), Pairs.end());
		
		vector<unsigned int> SortedIndices(NumThings);
		for(unsigned int i = 0; i < NumThings; i++)
			SortedIndices[i] = Pairs[i].index;
		
		vector<T> Things1Out(NumThings);
		vector<S> Things2Out(NumThings);
		for(unsigned int i = 0; i < NumThings; i++)
		{
			Things1Out[i] = Pairs[i].Item;
			Things2Out[i] = Things2[SortedIndices[i]];
		}
		
		//return by reference
		Things1 = Things1Out;
		Things2 = Things2Out;
	}
  • 1 Contributor
  • 0 Replies
  • 239 Views

Dani AI

Generated

Nice, clean solution from — it makes the intent obvious (sort a key vector and carry a parallel vector along). A few concise improvements and alternatives that work better with modern C++ and common edge cases.

A compact, idiomatic pattern is to sort an index array rather than wrap each element. This keeps the original containers intact until the final reorder, lets a custom comparator be injected, and plays nicely with move-only types:

template<typename T, typename S, typename Comp = std::less<T>>
void parallel_sort_by_key(std::vector<T>& keys, std::vector<S>& vals, Comp cmp = {})
{
    assert(keys.size() == vals.size());
    size_t n = keys.size();
    std::vector<size_t> idx(n);
    std::iota(idx.begin(), idx.end(), 0);
    std::stable_sort(idx.begin(), idx.end(), [&](size_t a, size_t b){ return cmp(keys[a], keys[b]); });

    std::vector<T> k2; k2.reserve(n);
    std::vector<S> v2; v2.reserve(n);
    for (size_t i : idx) { k2.push_back(std::move(keys[i])); v2.push_back(std::move(vals[i])); }
    keys.swap(k2); vals.swap(v2);
}

Alternatively, keep data together by zipping into a vector<pair<T,S>>, sort that with a comparator on .first, then unzip. That is simpler and often faster for small objects.

Notes and cautions:

  • Use std::stable_sort when equal-key relative order matters (stable pairing).
  • Moving elements saves copies but leaves moved-from objects; avoid moves if original containers must remain usable.
  • If extra O(n) memory is unacceptable, apply an in-place permutation (cycle-following) using the computed index map.
  • “Parallel sort” can be confused with multithreaded sorting; these patterns refer to keeping two sequences paired, not parallel execution.
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.