Sorting by a transformation function
ShaunJ
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. The transformation function is expensive and show be
called exactly once for each element of the vector. I have a solution,
included below. I want to know if this operation is possible using
ether standard functions or using boost, and whether my solution could
be improved at all. For bonus points, I'd like to include an optional
binary predicate as a fourth parameter that can be passed to
std::sort.
Cheers,
Shaun
#include <algorithm>
#include <cassert>
#include <iterator>
#include <utility>
#include <vector>
/** Sorts the elements in the range [first,last) ordered by the value
* returned by the unary function op, which is called once for each
* element in the range [first,last). The copy constructor of the
* value_type of It is not used.
* @author Shaun Jackman <sjac...@gmail.com>
*/
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(make_pair(op(*it), it - first));
sort(keys.begin(), keys.end());
// Initialize the permutation matrix P to the identity matrix.
std::vector<size_type> row(n), column(n);
for (size_type i = 0; i < n; i++)
row[i] = column[i] = i;
// Find the row-interchanging elementary matrices of P, and apply
// them to the vector [first,last).
for (size_type i = 0; i < n; i++) {
// The elements [0,i) are in their correct positions.
size_type j = column[keys[i].second];
if (i == j)
continue;
assert(i < j);
swap(first[i], first[j]);
// The elements [0,i] are in their correct positions.
// Swap rows i and j of the matrix.
swap(column[row[i]], column[row[j]]);
swap(row[i], row[j]);
assert(row[i] == keys[i].second);
assert(column[row[i]] == row[column[i]]);
assert(column[row[j]] == row[column[j]]);
}
}
#include <fuctional>
#include <iostream>
#include <iterator>
#include <vector>
using namespace std;
int main()
{
vector<string> data;
copy(istream_iterator<string>(cin), istream_iterator<string>(),
back_inserter(data));
sort_by_transform(data.begin(), data.end(),
mem_fun_ref(&string::length));
copy(data.begin(), data.end(),
ostream_iterator<string>(cout, "\n"));
return 0;
}
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Daniel Krügler
> 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. I assume that std::string is just a
bad model of your actual data. Is your code intended to be executed
in C++03 or in C++0x? So, by saying that you want to sort
a sequence of elements that are not copyable to you actually
mean
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.
> The transformation function is expensive and show be
> called exactly once for each element of the vector. I have a solution,
> included below.
The below code looks a bit suspicious to me. You say that
you want to sort elements and the code looks as if it would
sort the elements and shows at the end the sorted sequence.
Since you are not modifying the actual container, the result
has the same order as before.
> I want to know if this operation is possible using
> ether standard functions or using boost, and whether my solution could
> be improved at all. For bonus points, I'd like to include an optional
> binary predicate as a fourth parameter that can be passed to
> std::sort.
I'm not really sure what you want to realize. Even though your
code doesn't look like that, you just may want to extract the
sort information of some container of non-copyable (and maybe
not-movable) things and use this information to sort data that has
the same order as the original sequence. If this assumption is
correct,
you can use an indirect sort algorithm. John Potter provided some
code when I asked a similar question quite a while ago:
http://preview.tinyurl.com/27s3cdp
The basic idea is that you initialize a vector of std::size_t (or
of the size_type of the container) with values 0, 1, .. N-1
(in the following referred to as the "index vector") and to use a
wrapping functor that performs the comparison based on the
actual data. You can simply replace the template IndexComp
used in the link provided above by the more general form:
template <class RanIt, class UnaryFn>
struct IndexComp {
RanIt iter;
UnaryFn fn;
IndexComp(RanIt iter, UnaryFn fn)
: iter(iter), fn(fn)
{}
bool operator()(size_t i, size_t j) const {
return fn(*(iter + i)) < fn(*(iter + j));
}
};
Now you apply std::sort to the index vector, where
the sort predicate is specified by an object of
IndexComp, that is initialized with the begin iterator
of the original sequence of non-copyable things
and the actual unary functor (mem_fun_ref(&string::length)
in your example). In fact, the IndexComp in my own code
does contain an arbitrary binary predicate instead of
the fixed ordering of < and does not have need for an
unary transformation (The binary predicate cam be considered
as performing the transformation implicitly while evaluating
the predicate evaluation). This means that std::sort reorders
only the index vector to extract the sort information quite
similar as in your example, but without the overhead of
storing the key values as well.
You can now use the indirect sort algorithm shown in the
link above to sort any sequence with the same order as
the original one using the sort information with an overall
complexity of O(N log(N)). Given the more general form of
IndexComp with an arbitrary binary ordering predicate you
should be able to implement your bonus task as well ;-)
HTH & Greetings from Bremen,
Daniel Krügler
ShaunJ
Thank your for your detailed response. I've hopefully clarified my
original post below.
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.
> I assume that std::string is just a
> bad model of your actual data. Is your code intended to be executed
> in C++03 or in C++0x? So, by saying that you want to sort
> a sequence of elements that are not copyable to you actually
> mean
>
> 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.
> > The transformation function is expensive and show be
> > called exactly once for each element of the vector. I have a solution,
> > included below.
>
> The below code looks a bit suspicious to me. You say that
> you want to sort elements and the code looks as if it would
> sort the elements and shows at the end the sorted sequence.
> Since you are not modifying the actual container, the result
> has the same order as before.
I am modifying the actual container. The result is sorted. The actual
container is modified at this line:
swap(first[i], first[j]);
> > I want to know if this operation is possible using
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.
Cheers,
Shaun
red floyd
> Hi,
>
> 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.
Then forget it, you can't create a vector of them.
Per 23.2.4/2 ([lib.vector]/2):
"A vector satisfies all of the requirements of a container and of
a reversible container (given in two tables in 23.1)..."
Per 23.1/3
"The type of objects stored in these components must meet the
requirements of CopyConstructible types..."
Your type is not CopyConstructible, hence you can't create a
vector of it. Do not pass Go, do not collect $200.
ShaunJ
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'm not really sure what you want to realize. Even though your
> code doesn't look like that, you just may want to extract the
> sort information of some container of non-copyable (and maybe
> not-movable) things and use this information to sort data that has
> the same order as the original sequence. If this assumption is
> correct,
> you can use an indirect sort algorithm. John Potter provided some
> code when I asked a similar question quite a while ago:
>
> http://preview.tinyurl.com/27s3cdp
...
Thanks for this code! I'm suitably impressed. It's much more compact
than my solution which decomposed the permutation matrix. I've adapted
it to my code which caches the result of the transformation function
for each element.
Cheers,
Shaun
#include <algorithm>
#include <iterator>
#include <utility>
#include <vector>
/** Sorts the elements in the range [first,last) ordered by the value
* returned by the unary function op, which is called once for each
* element in the range [first,last). The copy constructor of the
* value_type of It is not used.
*/
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;
Daniel Krügler
> 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
ShaunJ
wrote:
...
Nice and tidy. I like it. The transform section could be replaced with
std::transform. The permutation section would be useful as an
algorithm all on its own.
How would you go about making BinPred pred default to
Op::result_type::operator< ?
Cheers,
Shaun
Daniel Krügler
[..]
> How would you go about making BinPred pred default to
> Op::result_type::operator< ?
Do you mean conceptually? Or do you mean it in the
way the standard library does specify it? Since you
already require the existence of Op::result_type,
it would probably make sense. Alternatively you could
get rid of the requirement of the existence of
Op::result_type at all by delegating to result_of (for
a C++0x target compiler), i.e. by referring to
typename std::result_of<Op(typename std::iterator_traits<
It>::value_type)>::type
instead.
You might want to consider template and function
default arguments (again, for a C++0x target
compiler):
template <class It, class Op, class BinPred =
std::less<typename Op::result_type>
>
void sort_by_transform(It first, It last, Op op,
BinPred pred = BinPred());
or using result_of as indicated above:
template <class It, class Op, class BinPred =
std::less<typename std::result_of<Op(typename
std::iterator_traits<It>::value_type)>::type>
>
void sort_by_transform(It first, It last, Op op,
BinPred pred = BinPred())
{
typedef typename std::iterator_traits<It>::difference_type
size_type;
typedef typename std::result_of<Op(typename
std::iterator_traits<It>::value_type)>::type
key_type;
...
}
[std::less is not the exact equivalent to operator<, but it
usually fits this purpose]
HTH & Greetings from Bremen,
Daniel Krügler