Re: Sorting by a transformation function
On 19 Aug., 01:58, ShaunJ <sjack...@gmail.com> wrote:
On Aug 18, 11:45 am, Daniel Kr?gler <daniel.krueg...@googlemail.com>
wrote:
On 18 Aug., 02:17, ShaunJ <sjack...@gmail.com> wrote:
I would like to sort a vector ordered by the return value of a unary
transformation function, op. The elements of the vector do not have a
copy constructor.
It is a bit irritating that in your example the elements (std::string)
do have a copy constructor.
Sorry about that. I wanted to show an example of how the algorithm
would be called. Just pretend std::string does not have a copy
constructor. What I should have said is, the object being sorted may
not have a copy constructor, and if it does, may be expensive.
std::swap for this object is not expensive.
[..]
a) A sort algorithm that does move instead of copy
b) You don't want to sort the elements themselves, but you just
want to get the sort information from the sequence and apply
this sort information to other containers.
Yes, the former (a). I'm looking for a sort algorithm that moves but
does not copy. In my solution, I achieved this by implementing the
latter (b). The vector keys contains the sort information, which I
then use to rearrange the original elements.
OK, understood.
I am modifying the actual container. The result is sorted. The actual
container is modified at this line:
swap(first[i], first[j]);
[..]
This method will call fn N*log(N) times. I indicated that the
transformation function is expensive and should be
called exactly once for each element of the vector. Storing the result
of the transformation function is desired in this case.
Yes, you are right, sorry for the wrong analysis. It was a bit
late and (a) I overlooked the fact, that your sort just sorts
according
to string length and (b) I didn't notice your remark that calling the
transformation function should be done only once.
In regard to your currently suggested version:
template <class It, class Op>
void sort_by_transform(It first, It last, Op op)
{
typedef typename std::iterator_traits<It>::difference_type
size_type;
typedef typename Op::result_type key_type;
size_type n = last - first;
std::vector< std::pair<key_type, size_type> > keys;
keys.reserve(n);
for (It it = first; it != last; ++it)
keys.push_back(std::make_pair(op(*it), it - first));
sort(keys.begin(), keys.end());
for (size_type i = 0; i < n; i++) {
size_type j = keys[i].second;
while (j < i)
j = keys[j].second;
if (i != j)
swap(first[i], first[j]);
keys[i].second = j;
}
}
you were asking for providing a way to provide an alternative
binary predicate. I assume you meant that to be a binary
predicate acting on the actual *key type*, right?
It seems to me that the code could be better divided into
separate responsibilities, when you don't enforce a pair
container. What about the following partitioning:
1) Transform into key type
2) Determining sort order of key vector
3) Sort original container in this sort order
To realize that use the previously suggested form of
an indirect sort predicate adapted to you types and
style:
template <class RanIt, class BinPred>
struct IndexComp {
RanIt iter;
BinPred pred;
typedef typename std::iterator_traits<RanIt>::difference_type
size_type;
IndexComp(RanIt iter, BinPred pred)
: iter(iter), pred(pred)
{}
bool operator()(size_type i, size_type j) const {
return pred(iter[i], iter[j]);
}
};
which allow then to write the following algorithm:
template <class It, class Op, class BinPred>
void sort_by_transform(It first, It last, Op op, BinPred pred)
{
typedef typename std::iterator_traits<It>::difference_type
size_type;
typedef typename Op::result_type key_type;
// Transform:
size_type n = last - first;
typedef std::vector<key_type> key_cont_t;
key_cont_t keys;
keys.reserve(n);
for (It it = first; it != last; ++it)
keys.push_back(op(*it));
// Determine sort order of keys:
std::vector<size_type> indices;
indices.reserve(n);
for (It it = first; it != last; ++it)
indices.push_back(it - first);
sort(indices.begin(), indices.end(), IndexComp<
key_cont_t::const_iterator, BinPred>(keys.begin(),
pred));
// Sort original container in sort order:
for (size_type i = 0; i < n; ++i) {
size_type j = indices[i];
while (j < i)
j = indices[j];
if (i != j)
swap(first[i], first[j]);
indices[i] = j;
}
}
HTH & Greetings from Bremen,
Daniel Kr?gler
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]