How can I define a "Do-Nothing" sort?

Question

Hi,

I'm working on a system where I need to be able to sort a vector by a given predicate, which my classes shouldn't have control over. Basically, I pass them a derived class and they blindly sort on it.

As one of the "delightful quirks", one of the sort patterns is order of entry. Here's what I've got so far.

struct Strategy
{
   virtual bool operator()(const Loan& lhs, const Loan& rhs) const = 0;
};

struct strategyA : public Strategy
{
   bool operator()(const Loan& lhs, const Loan& rhs) const
   {
      return true;
   }
};

struct strategyB : public Strategy
{
   bool operator()(const Loan& lhs, const Loan& rhs) const
   {
      return lhs.getID() > rhs.getID();
   }
};

struct strategyC : public Strategy
{
   bool operator()(const Loan& lhs, const Loan& rhs) const
   {
      return lhs.getFee() > rhs.getFee();
   }
};

Obviously, as strategyA is reflexive, it can't be used, and if I set it to false, it'll treat everything as equal and I can kiss my data goodbye.

So here's my question. Is there a way of defining a predicate function for sorting a vector which will NOT change anything?

I'm aware that possibly the simplest solution is to add an order of entry variable to the Loan class, or partner it with one in a pair. Alternatively I could feed a parameter in with the predicate that tells the sorter whether to use it or not.

Answer 1

if it is simply a vector you are talking about, perhaps you can get away with providing an interface that determines whether you should sort or not. vectors are not an ordered container, so you need to explicitly sort them. Just don't sort them at all.

Answer 2

Is there a way of defining a predicate function for sorting a vector which will NOT change anything?

It depends on the algorithm. If your sort is a stable sort, the order of "equal" elements won't be changed (which is undefined for unstable sorts).

Consider using std::stable_sort.

Answer 3

There is no sort function which would keep the order of items based only on items' values. You need to provide more information to your Strategy, if it's possible.

Answer 4

A different approach might be to bring the semantics of your data to the container. Consider using boost::multi_index for different ways of access and ordering on the same data:

http://www.boost.org/doc/libs/1_42_0/libs/multi_index/doc/index.html

Answer 5

Personally, I think your strategy class should have a "sort" method. That way, it can either call std::sort or not, as it sees fit. Whether as well as how becomes part of the sorting strategy.

Darios stable_sort answer is very good, if you can use it.

It is possible to do sorting based on item position in a vector, but it doesn't mean items won't move (many sort algorithms will basically scramble-then-resort your data), so you have to have some reliable way of determining where the items were when you started.

It's possible for the comparison to keep a mapping of current-position to original-position, but a lot of work. Ideally the logic needs to be built into the sort algorithm - not just the comparison - and that's essentially how stable_sort works.

Another problem - depending on the container - the order of (say) item addresses isn't always the order of the items.