Re: indirect / index sorting with the STL
On 19/05/11 23:38, Joshua Lehrer wrote:
On May 18, 4:46 pm, cpp4ever <n2xssvv.g02gfr12...@ntlworld.com> wrote:
This is not a complete answer, but why not sort a separate list of
indices/pointers/iterators? The std::sort algorithm can easily be
provided with a specific comparison function/functor. For large objects
swapping indices/pointers/iterators is far quicker and more simple.
Regards
cpp4ever
Because that would require O(N) external storage. If I had a list of
strings N elements long and a list of ints to sort by, also N elements
long, I'd need to create a list of pair<string*,int*> also N elements
long, thus requiring O(N) external storage. This should be doable
with O(1) external storage.
-J
Let me explain further. Once you have sorted the
indices/pointers/iterators, you can determine the indices into the
original list.
std::vector<int> itmp(4,23);
std::vector<char *> ctmp(4,"hello");
......
......
std::vector<int>::const_iterator i = tmp.begin() + 3;
int index = i - tmp.begin();
std::cout << ctmp[i]; // Outputs the equivalent string
I accept that this requires an extra O(N) external storage, but it is
not as complicated as you suggest.
Creating a specialist container class and iterator class that is a
wrapper around the 2 lists. When used with std::sort it would swap
elements from both lists is another alternative, but IMHO this is an
overly complex solution, and for large memory objects would most
probably be slow.
regards
cpp4ever
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]