Re: indirect / index sorting with the STL
Joshua Lehrer wrote:
I was challenged to come up with a way to use existing STL algorithms
to sort one vector but given sorting precedence in a separate vector.
An additional constraint is that only O(1) constant external storage
may be used.
A const amount of storage, not dependent on the number of elements? You don't mean O(n), do you? Anyway...
In other words, a vector<string> containing "A","B","C" sorted
indirectly given the precedence vector<int> of 22,11,33 would yield a
vector<string> of "B","A","C".
Okay.
I tried to write my own container class
This would violate the O(1) space limit already, I'd say.
I've come to the conclusion that this can't be done with std::sort,
but is there another algorithm that can help? Aside from rewriting
sort on my own, does anyone have another suggestion?
What you can do is to create a container wrapper class that operates on the
two underlying containers which it takes as reference. However, you don't
need a container for std::sort, you only need iterators! More precisely, you
need random access iterators (I hope I remember that correctly, but you
should get errors while compiling otherwise).
This iterator would look like this:
struct iterator
{
iterator& operator++()
{
++m_it1;
++m_it2;
return *this;
}
friend bool operator==(iterator& lhs, iterator& rhs)
{
return lhs.m_it1 == rhs.m_it1;
}
struct value_type
{
int& i;
string& s;
};
value_type operator*() const
{
value_type r = {*m_it1, *m_it2};
return r;
}
iterator<int> m_it1;
iterator<string> m_it2;
};
The main features are:
- The iterator provides a random access iterator interface.
- The value_type combines access to elements of both sequences so that
assignment/swap will operate on both elements.
Thinking about it, I believe the value_type above will become a lot more
complex because it has to delegate any change to the underlying sequence
elements, but possibly be default-constructible, too.
In any case, I would take a look at an iterator construction kit like e.g.
Boost.Iterator, which provides lots of boilerplate already.
Good luck!
Uli
--
Domino Laser GmbH
Gesch??ftsf??hrer: Thorsten F??cking, Amtsgericht Hamburg HR B62 932
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]