By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,928 Members | 1,173 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,928 IT Pros & Developers. It's quick & easy.

Is incrementing iterators actually this slow?

P: n/a
Hey all,

I have a bit of code that implements a suffix array, which is essentially an
array of iterators or indexes into a string. The array starts out like this

String: ABAB
Array: 0123

But then gets sorted

Array: 2031
2 AB
0 ABAB
3 B
1 BAB

All of this is well and good, but I have a little problem. Currently, I am
using the STL's sort algorithm and providing a custom comparison function,
which ends up sorting this vector<string::iterator> alphabetically. Here is
the comparison and other associated functions:

bool itLess(string::const_iterator it1, string::const_iterator it2, int
skip)
{
advanceIterators(it1, it2, skip);
return (*it1 < *it2 || *it1 == '\0');
}

int advanceIterators(string::const_iterator &it1, string::const_iterator
&it2,
int skip)
{
string::const_iterator ref(it1);
advanceNoCheck(it1, it2, skip);

while (*it1 == *it2 && !(*it1 == '\0')) {
++it1;
++it2;
}

return it1 - ref;
}

void advanceNoCheck(string::const_iterator &it1, string::const_iterator
&it2,
int skip)
{
if (skip) {
it1 += skip;
it2 += skip;
}
}

The way the sorting works is that one method goes through the text string
and makes an iterator for each position, putting it into the array.
Afterwards, I call 'sort(m_array.begin(), m_array.end(), &itLess).' It
takes entirely too long.

I have profiled my code with gprof (I know, it's platform specific, but you
should be able to read the output). The code was compiled with all
optimizations turned on, and run on a text of 10 million characters that did
not have a high incidence of repetition. Here is the output of the
profiler:

% cumulative self self total
time seconds seconds calls Ks/call Ks/call name
int advanceIterators(string::const_iterator &, string::const_iterator &):
98.92 1196.55 1196.55 302747982 0.00 0.00
bool itLess(string::const_iterator, string::const_iterator):
0.42 1201.59 5.04 282747983 0.00 0.00
std::__unguarded_partition([template junk]):
0.21 1204.10 2.51 1074094 0.00 0.00
void advanceNoCheck(string::const_iterator &, string::const_iterator &):
0.09 1205.20 1.10 302747982 0.00 0.00

Clearly, my advanceIterators (and hence, all of my iterator comparison) is
far too slow. If I run my code without optimizations (that is, if I do not
inline iterator::operator ++ and iterator::operator *), you would see that
most of the time spent in advanceIterators is actually spent in those two
methods. Does anyone know a faster way to sort string::const_iterators
lexicographically?

- JFA1
Jul 23 '05 #1
Share this Question
Share on Google+
3 Replies


P: n/a
"James Aguilar" <jf**@cec.wustl.edu> wrote in message
news:d2**********@newsreader.wustl.edu...
bool itLess(string::const_iterator it1, string::const_iterator it2, int
skip)
{
advanceIterators(it1, it2, skip);
return (*it1 < *it2 || *it1 == '\0');
}
I suspect that this code doesn't do what you think it does.

I am guessing that you are using the comparison *it1 == '\0' as a way of
checking whether it1 has run off the end of the string.

It doesn't do that. It is your responsibility to know where the end of the
string is, and to dereference only iterators that you know refer to elements
of the string.

int advanceIterators(string::const_iterator &it1, string::const_iterator
&it2,
int skip)
{
string::const_iterator ref(it1);
advanceNoCheck(it1, it2, skip);

while (*it1 == *it2 && !(*it1 == '\0')) {
++it1;
++it2;
}

return it1 - ref;
}


Same problem here: It looks like you are assuming that once you run off the
end of the string, *it1 will be 0. It won't, in general. You'll get what
you get.
Jul 23 '05 #2

P: n/a
"Andrew Koenig" <ar*@acm.org> wrote in message
news:ii*******************@bgtnsc04-news.ops.worldnet.att.net...

Same problem here: It looks like you are assuming that once you run off
the end of the string, *it1 will be 0. It won't, in general. You'll get
what you get.


It seems to work on small problems (sorting them correctly. Also, a little
test code shows that, at least with g++ 3.3.3, it works:

#include <string>
#include <iostream>

using namespace std;

int main()
{
string a;

cout << (*(a.begin() + a.length()) == '\0') << '\n';

a += "asad";
cout << (*(a.begin() + a.length()) == '\0') << '\n';

a = "OMGZ?";
cout << (*(a.begin() + a.length()) == '\0') << '\n';

return 0;
}

prints 1, 1, 1 on my system. Even if this is non-standard, I'm almost
positive that it is not the problem.

- JFA1
Jul 23 '05 #3

P: n/a
"James Aguilar" <jf**@cec.wustl.edu> wrote in message
news:d2**********@newsreader.wustl.edu...
It seems to work on small problems (sorting them correctly. Also, a
little test code shows that, at least with g++ 3.3.3, it works:
No, it happens to do something that appears to work in this particular case.
prints 1, 1, 1 on my system. Even if this is non-standard, I'm almost
positive that it is not the problem.


It doesn't matter. As written, the program's behavior is undefined.
There's no point in investigating further until this problem is corrected.
Jul 23 '05 #4

This discussion thread is closed

Replies have been disabled for this discussion.