The Goal:
Come up with a std::sort friendly generic functor that allows for a (run-time) dynamic member-wise comparison of an object.
e.g., given:
struct Foo
{
int a, b, c;
};
vector<Foo> foos;
sort(foos, mycomparisonobject());
If foos[0].a == foos[1].a, then compare .b, and if those are equal, compare .c... and so on for any given permutation of a, b, and c.
The Motivation:
Primarily my own curiosity. I've often wondered how one would sort a database table on any given column, or sort a list of files based on its various attributes (think: a window manager's file view in 'details' mode, where one clicks on a column heading to sort on that attribute).
The Request:
I'd like a little feedback on the implementation I've come up with below. style, correctness, performance, whatever.
The Implementation:
I'd recommend jumping down to main first to get a feel for how the SortObject class is used. One quirk you may notice is the Holder class. The functor passed to std::sort is copy constructed for every comparison. That didn't jive well with the heap-allocated members of SortObject, and a deep copy would have been prohibitively expensive given its frequency. I'd definitely be interested in a better solution.
I've also added some extras (sort direction, accessor binding, etc) for completeness.
#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <vector>
template <class IdType, class ClassType>
class SortOrder
{
private:
template <class Order>
class Holder
{
public:
Holder(const Order& order) : order_(order) {}
Holder(const Holder& holder) : order_(holder.order_) {}
inline bool operator () (const typename Order::sort_class_type& lhs,
const typename Order::sort_class_type& rhs) const
{
return order_.compare(lhs, rhs);
}
private:
const Order& order_;
};
public:
typedef ClassType sort_class_type;
typedef IdType id_type;
enum Direction { Ascend = 0, Descend = 1};
SortOrder() {}
~SortOrder()
{
for(MembersItr itr = members_.begin(); itr != members_.end(); ++itr)
{
delete itr->second;
}
}
std::vector<IdType> order() const
{
std::vector<IdType> ids(members_.size());
typename std::vector<IdType>::iterator idsItr = ids.begin();
for(MembersCItr memItr = members_.begin(); memItr != members_.end(); ++memItr, ++idsItr)
{
*idsItr = memItr->first;
}
}
template <class MemberType>
SortOrder& add(IdType id, const MemberType ClassType::* member, Direction direction = Ascend)
{
members_.push_back(std::make_pair(id, new TemplatedVar<MemberType>(member, direction)));
return *this;
}
template <class AccessorType>
SortOrder& add(IdType id, AccessorType (ClassType::* accessor)() const, Direction direction = Ascend)
{
members_.push_back(std::make_pair(id, new TemplatedAccessor<AccessorType>(accessor, direction)));
return *this;
}
void remove(IdType id)
{
for(MembersItr itr = members_.begin(); itr != members_.end(); ++itr)
{
if(itr->first == id)
{
delete itr->second;
itr->second = NULL;
std::swap((*itr), *(members_.end())); // move the one we want to remove to the end
members_.pop_back(); // remove the one we just swapped to the end from the back.
return;
}
}
}
void promote(IdType id)
{
for(MembersItr itr = members_.begin(); itr != members_.end(); ++itr)
{
if(itr->first == id)
{
std::swap(*(members_.begin()), (*itr));
return;
}
}
}
void toggleDirection(IdType id)
{
for(MembersItr itr = members_.begin(); itr != members_.end(); ++itr)
{
if(itr->first == id)
{
itr->second->direction_ = ((itr->second->direction_ == Ascend) ? Descend : Ascend);
}
}
}
bool compare(const ClassType& lhs, const ClassType& rhs) const
{
for(MembersCItr itr = members_.begin(); itr != members_.end(); ++itr)
{
const GenericVar* var = itr->second;
if(var->compare(lhs, rhs))
{
return true;
}
else
{
if(var->equal(lhs, rhs))
{
continue;
}
else
{
return false;
}
}
}
return false;
}
Holder<SortOrder> operator() () { return Holder<SortOrder>(*this); }
private:
class GenericVar
{
public:
GenericVar(Direction direction) : direction_(direction) {}
virtual bool compare(const ClassType& lhs, const ClassType& rhs) const
{
return ((direction_ == Ascend) ? lessThan(lhs, rhs) : greaterThan(lhs, rhs));
}
virtual bool equal (const ClassType& lhs, const ClassType& rhs) const = 0;
virtual bool lessThan (const ClassType& lhs, const ClassType& rhs) const = 0;
virtual bool greaterThan(const ClassType& lhs, const ClassType& rhs) const = 0;
Direction direction_;
};
template <class MemberType>
class TemplatedVar : public GenericVar
{
public:
typedef MemberType member_type;
TemplatedVar(const MemberType ClassType::* member, Direction direction) : GenericVar(direction), member_(member) {}
virtual bool equal(const ClassType& lhs, const ClassType& rhs) const
{
return (lhs.*member_ == rhs.*member_);
}
virtual bool greaterThan(const ClassType& lhs, const ClassType& rhs) const
{
return (lhs.*member_ > rhs.*member_);
}
virtual bool lessThan(const ClassType& lhs, const ClassType& rhs) const
{
return (lhs.*member_ < rhs.*member_);
}
private:
const MemberType ClassType::* member_;
};
template <class AccessorType>
class TemplatedAccessor : public GenericVar
{
public:
typedef AccessorType accessor_type;
TemplatedAccessor(AccessorType (ClassType::* accessor)() const, Direction direction) : GenericVar(direction), accessor_(accessor) {}
virtual bool equal(const ClassType& lhs, const ClassType& rhs) const
{
return ((lhs.*accessor_)() == (rhs.*accessor_)());
}
virtual bool greaterThan(const ClassType& lhs, const ClassType& rhs) const
{
return ((lhs.*accessor_)() > (rhs.*accessor_)());
}
virtual bool lessThan(const ClassType& lhs, const ClassType& rhs) const
{
return ((lhs.*accessor_)() < (rhs.*accessor_)());
}
private:
AccessorType (ClassType::* accessor_)() const;
};
typedef std::pair<IdType, GenericVar*> Member;
typedef std::vector<Member> Members;
typedef typename Members::iterator MembersItr;
typedef typename Members::const_iterator MembersCItr;
SortOrder(const SortOrder& sortOrder); // Disable: declare, but not define.
SortOrder& operator = (const SortOrder& sortOrder); // Disable: declare, but not define.
Members members_;
};
class Foo
{
public:
Foo(int a, int b, int c, const std::string& str) : a_(a), b_(b), c_(c), str_(str) {}
int a_;
int b_;
std::string str_;
inline int getC() const { return c_; }
private:
int c_;
};
std::ostream& operator << (std::ostream& os, const Foo& foo)
{
return (os << '(' << foo.a_ << ", " << foo.b_ << ", " << foo.getC() << ", " << foo.str_ << ')');
}
int main(int argc, char** argv)
{
std::vector<Foo> foos;
foos.push_back(Foo(2, 4, 75, "lamda"));
foos.push_back(Foo(1, 5, 8, "gamma"));
foos.push_back(Foo(3, 3, 90, "alpha"));
foos.push_back(Foo(4, 2, 1, "omega"));
foos.push_back(Foo(5, 1, 26, "beta"));
foos.push_back(Foo(1, 1, 1, "beta"));
SortOrder<std::string, Foo> sortOrder;
sortOrder.add("a", &Foo::a_)
.add("b", &Foo::b_)
.add("c", &Foo::getC)
.add("str", &Foo::str_);
using std::cin;
using std::cout;
using std::endl;
using std::ostream_iterator;
cout << "Unmodified" << endl;
copy(foos.begin(), foos.end(), ostream_iterator<Foo>(cout, "\n")); cout << endl;
cout << "Sorted by default order" << endl;
sort(foos.begin(), foos.end(), sortOrder());
copy(foos.begin(), foos.end(), ostream_iterator<Foo>(cout, "\n")); cout << endl;
cout << "Promote \"b\", order is now: b, a, c, str" << endl;
sortOrder.promote("b");
sort(foos.begin(), foos.end(), sortOrder());
copy(foos.begin(), foos.end(), ostream_iterator<Foo>(cout, "\n")); cout << endl;
cout << "Promote \"str\", order is now: str, b, a, c" << endl;
sortOrder.promote("str");
sort(foos.begin(), foos.end(), sortOrder());
copy(foos.begin(), foos.end(), ostream_iterator<Foo>(cout, "\n")); cout << endl;
cout << "Promote \"c\", order is now: c, str, b, a" << endl;
sortOrder.promote("c");
sort(foos.begin(), foos.end(), sortOrder());
copy(foos.begin(), foos.end(), ostream_iterator<Foo>(cout, "\n")); cout << endl;
cout << "Change the direction of of sort for \"c\" to descending" << endl;
sortOrder.toggleDirection("c");
sort(foos.begin(), foos.end(), sortOrder());
copy(foos.begin(), foos.end(), ostream_iterator<Foo>(cout, "\n")); cout << endl;
cin.get();
return 1;
}
Sample output:
Unmodified
(2, 4, 75, lamda)
(1, 5, 8, gamma)
(3, 3, 90, alpha)
(4, 2, 1, omega)
(5, 1, 26, beta)
(1, 1, 1, beta)
Sorted by default order
(1, 1, 1, beta)
(1, 5, 8, gamma)
(2, 4, 75, lamda)
(3, 3, 90, alpha)
(4, 2, 1, omega)
(5, 1, 26, beta)
Promote "b", order is now: b, a, c, str
(1, 1, 1, beta)
(5, 1, 26, beta)
(4, 2, 1, omega)
(3, 3, 90, alpha)
(2, 4, 75, lamda)
(1, 5, 8, gamma)
Promote "str", order is now: str, b, a, c
(3, 3, 90, alpha)
(1, 1, 1, beta)
(5, 1, 26, beta)
(1, 5, 8, gamma)
(2, 4, 75, lamda)
(4, 2, 1, omega)
Promote "c", order is now: c, str, b, a
(1, 1, 1, beta)
(4, 2, 1, omega)
(1, 5, 8, gamma)
(5, 1, 26, beta)
(2, 4, 75, lamda)
(3, 3, 90, alpha)
Change the direction of of sort for "c" to descending
(3, 3, 90, alpha)
(2, 4, 75, lamda)
(5, 1, 26, beta)
(1, 5, 8, gamma)
(1, 1, 1, beta)
(4, 2, 1, omega)
[Edited by - godecho on June 24, 2008 9:35:27 AM]