Iterating through a string

[Steve]

Hi Guys,

I have a string which contains data elements separated by spaces. I also
have a function which returns the number of characters from the beginning of
the string for a given number of spaces. I am using a loop with strchr for
the number of spaces, and I was just wondering if there was a more efficient
(ie faster) way of achieving this. Any ideas please? Current function code
below:

int GetNewPosition( const std::string& DataStr, const int Spaces)
{
int i = 0; // space counter
char* b = const_cast<char *>(DataStr.c_st r()); // beginning of string

do {
b = strchr(b, ' '); // find next space
++i; ++b; // increment space counter and pointer
} while(i<Spaces && b != NULL);

if(b) return b - DataStr.c_str() ;
else return -1;
}
Any help is appreciated,
Thanks for reading,
Steve.

[David Harmon]

On Tue, 8 Jun 2004 22:42:36 +0100 in comp.lang.c++, "Steve"
<st*******@hotm ail.com> wrote,

the string for a given number of spaces. I am using a loop with strchr for
the number of spaces, and I was just wondering if there was a more efficient
(ie faster) way of achieving this.

For efficiency, avoid going over the same ground more than once, i.e.
continue from the previous position and do not restart at the beginning
of the string.

Use string::find() functions rather than .c_str() and dropping down to
low-level old library strchr().

Do not subtract one .c_str() from another. There is no guarantee that
..c_str() will point to the same buffer every time.

See if using a string splitter function would suit you better?
http://groups.google.com/gr*********....earthlink.net

[Dave Townsend]

There's probably a standard library input stream class which you can use to
suck out the pieces of data you want.
If you want to roll your own, you could create a specialized iterator object
which takes your string and lets you iterate over it. It seems that you
are always starting from the beginning when you want the next position and
count through the string to find the next one. By using an object to wrap
the
string, you could maintain this state information in the object and wouldn't
need to compute it from scratch every time.
class FooBar
{
public:
FooBar( const std::string& DataStr )
:_DataStr(DataS tr), _position(0)
{
// move position to point to the first data item.
}

std::string GetDataItem( ) const
{
// return a string representing the next data item.
}
bool IsValid() const ; // return true if there are more items to return,
false otherwise.
bool Next(); // advance through datastring until end of string or next
data item is found,
// update position counter.

bool First() ; // wind back position to be at the first data item, so we
can iterate again over
// the string.

private:
const std::string _DataStr
int _position;

};

.......

FooBar myfoobar( DataStr);

for ( myfoobar.First( ) ; myfoobar.IsVali d( DataItem); myfoobar.Next() )
{
string ds = myfoobar.GetDat aItem();

}

"Steve" <st*******@hotm ail.com> wrote in message
news:Ohrxc.1911 $ud5.1728@newsf e4-gui...

Hi Guys,

I have a string which contains data elements separated by spaces. I also
have a function which returns the number of characters from the beginning of the string for a given number of spaces. I am using a loop with strchr for
the number of spaces, and I was just wondering if there was a more efficient (ie faster) way of achieving this. Any ideas please? Current function code
below:

int GetNewPosition( const std::string& DataStr, const int Spaces)
{
int i = 0; // space counter
char* b = const_cast<char *>(DataStr.c_st r()); // beginning of string

do {
b = strchr(b, ' '); // find next space
++i; ++b; // increment space counter and pointer
} while(i<Spaces && b != NULL);

if(b) return b - DataStr.c_str() ;
else return -1;
}
Any help is appreciated,
Thanks for reading,
Steve.

[Daniel T.]

In article <Ohrxc.1911$ud5 .1728@newsfe4-gui>,
"Steve" <st*******@hotm ail.com> wrote:

Hi Guys,

I have a string which contains data elements separated by spaces. I also
have a function which returns the number of characters from the beginning of
the string for a given number of spaces. I am using a loop with strchr for
the number of spaces, and I was just wondering if there was a more efficient
(ie faster) way of achieving this. Any ideas please? Current function code
below:

int GetNewPosition( const std::string& DataStr, const int Spaces)
{
int i = 0; // space counter
char* b = const_cast<char *>(DataStr.c_st r()); // beginning of string

do {
b = strchr(b, ' '); // find next space
++i; ++b; // increment space counter and pointer
} while(i<Spaces && b != NULL);

if(b) return b - DataStr.c_str() ;
else return -1;
}

I don't think your code does what you want it to do, but since you
didn't show what you wanted, I'm not sure.

I wrote this:

int main() {
string elements( "aaa bbb ccc ddd" );
for ( int x = 0; x < 10; ++x ) {
int pos = GetNewPosition( elements, x );
cout << pos << endl;
}
}

and got this output:

4
4
8
12
-654603

*crash*

I'm not entirely sure what your code is supposed to do, but this
function may be more in line with what you are looking for:

int GetNewPosition( const std::string& DataStr, int Spaces)
{
assert( Spaces >= 0 );
int result = -1;
unsigned working = DataStr.find_fi rst_not_of( ' ' );
// strictly speaking 'working != string::npos' in the
// below isn't necessary. It makes the code more efficient.
while ( working != string::npos && Spaces-- ) {
working = DataStr.find_fi rst_not_of( ' ',
DataStr.find( ' ', working ) );
}
assert( working == string::npos || working <= INT_MAX );
if ( working != string::npos )
result = working;
return result;
}

On most computers, I could have done without the 'working' variable,
instead using the 'result' variable. However, from what I understand -1
== string::npos is not guaranteed to be true.

Also note the two asserts in the function. They check the assumptions
made in the algorighm (a) Spaces isn't negitive (it may work with a
negitive value for Spaces, but I didn't test it, (b) that the position
of the char we are looking for is small enough to fit in an int (what
would it take to generate a string that would cause this assert to fire?)

[Daniel T.]

In article <25************ ********@comcas t.com>,
"Dave Townsend" <da********@com cast.net> wrote:

If you want to roll your own, you could create a specialized iterator object
which takes your string and lets you iterate over it.
If the OP decides to do this, I think he would be better off if he
followed the standard iterator concept.

class FooBar
{
public:
FooBar( const std::string& DataStr )
:_DataStr(DataS tr), _position(0)
{
// move position to point to the first data item.
}

std::string GetDataItem( ) const
{
// return a string representing the next data item.
}
bool IsValid() const ; // return true if there are more items to return,
false otherwise.
bool Next(); // advance through datastring until end of string or next
data item is found,
// update position counter.

bool First() ; // wind back position to be at the first data item, so we
can iterate again over
// the string.

private:
const std::string _DataStr
int _position;

};

The class below is a standard input iterator:

class word_iterator:
public std::iterator<s td::input_itera tor_tag, std::string>
{
friend bool operator==( const word_iterator& lhs,
const word_iterator& rhs );
friend std::ostream& operator<<( std::ostream& lhs,
const word_iterator& rhs ); // for testing only

const std::string* str;
std::string::si ze_type pos;

public:
word_iterator( const std::string* s = 0 ):
str( s && !s->empty() ? s: 0 ),
pos(std::string ::npos) {
if ( s )
pos = s->find_first_not _of( ' ' );
}

const std::string operator*() const {
assert( pos != std::string::np os );
unsigned len = str->find( ' ', pos );
if ( len < std::string::np os ) len -= pos;
return str->substr( pos, len );
}

const std::string* operator->() const {
// is there a better way to write this function?
static std::string bit;
bit = **this;
return &bit;
}

const word_iterator& operator++() {
assert( pos != std::string::np os );
if ( pos != std::string::np os )
pos = str->find_first_not _of( ' ', str->find( ' ', pos ) );
return *this;
}

const word_iterator operator++(int) {
word_iterator tmp( *this );
++(*this);
return tmp;
}
};

bool operator==( const word_iterator& lhs, const word_iterator& rhs ) {
// comparing iterators from two different containers is undefined
return lhs.pos == rhs.pos;
}

bool operator!=( const word_iterator& lhs, const word_iterator& rhs ) {
return !( lhs == rhs );
}

std::ostream& operator<<( std::ostream& lhs, const word_iterator& rhs ) {
// for testing purposes only
lhs << "Pos: " << rhs.pos << " of string: '"
<< ((rhs.str) ? *rhs.str : std::string("NU LL")) << "'";
return lhs;
}
FooBar myfoobar( DataStr);

for ( myfoobar.First( ) ; myfoobar.IsVali d( DataItem); myfoobar.Next() )
{
string ds = myfoobar.GetDat aItem();

}

Mine would be used like this:

string s;
//...
for ( word_iterator x( &s ); x != word_iterator() ; ++x )
cout << "word: " << *x
<< " is " << x->length() << "long.\n";
Or you could use it in the standard algorithms:

string s;
//...
copy( word_iterator(& s), word_iterator() ,
ostream_iterato r<string>(cout , "\n"));

[Siemel Naran]

"David Harmon" <so****@netcom. com.invalid> wrote in message

Use string::find() functions rather than .c_str() and dropping down to
low-level old library strchr().

The strcmp, strchr, memcmp functions may be more efficient than std::equal,
std::find because of block optimizations (ie. builtin CPU instructions to
analyze an entire block of bytes at once). In principle an implementation
may specialize std::find etc to call strchr, but I have yet to find one.

[Siemel Naran]

"Steve" <st*******@hotm ail.com> wrote in message
news:Ohrxc.1911 $ud5.1728@newsf e4-gui...

int GetNewPosition( const std::string& DataStr, const int Spaces)
{
int i = 0; // space counter
char* b = const_cast<char *>(DataStr.c_st r()); // beginning of string

do {
b = strchr(b, ' '); // find next space
++i; ++b; // increment space counter and pointer
} while(i<Spaces && b != NULL);

if(b) return b - DataStr.c_str() ;
else return -1;
}

In addition to the other points, what happens when strchr returns NULL?
Your code does ++b, which may (and should) crash the program.

As Dave points out, you should store the result of the first DataStr.c_str
in a pointer, and avoid calling the function a second time as it is allowed
to return a different pointer.

[John Harrison]

"Steve" <st*******@hotm ail.com> wrote in message
news:Ohrxc.1911 $ud5.1728@newsf e4-gui...

Hi Guys,

I have a string which contains data elements separated by spaces. I also
have a function which returns the number of characters from the beginning of the string for a given number of spaces. I am using a loop with strchr for
the number of spaces, and I was just wondering if there was a more efficient (ie faster) way of achieving this. Any ideas please? Current function code
below:

int GetNewPosition( const std::string& DataStr, const int Spaces)
{
int i = 0; // space counter
char* b = const_cast<char *>(DataStr.c_st r()); // beginning of string

do {
b = strchr(b, ' '); // find next space
++i; ++b; // increment space counter and pointer
} while(i<Spaces && b != NULL);

if(b) return b - DataStr.c_str() ;
else return -1;
}

Your current function is bugged. If there are no spaces, then b == NULL,
then you increment b, then you test it for NULL. That isn't going to work.
You also have a completely gratuitous const_cast in your code.

It's quite a good example of how newbies worry about efficiency without
other more important considerations such as writing working code, and
writing clear code.

However strchr is probably the fastest way to do it, however as with all
these questions there is no official answer as to which method is fastest.
The C++ standard makes no mention of which functions or techniques are
faster than others, the only way to tell for sure is try different methods
and time them.

Here's my version, completely untested, so apologies in advance for any
bugs.

int GetNewPosition( const std::string& DataStr, int Spaces)
{
const char* start = DataStr.c_str() ;
const char* p = start;
for (int i = 0; i < Spaces; ++i)
{
if (p == NULL)
return -1;
p = strchr(p + 1, ' ');
}
return p - start;
}

john

[Siemel Naran]

"John Harrison" <jo************ *@hotmail.com> wrote in message
news:2inljvFpkd 8vU1@uni-

"Steve" <st*******@hotm ail.com> wrote in message

int GetNewPosition( const std::string& DataStr, const int Spaces)
{
int i = 0; // space counter
char* b = const_cast<char *>(DataStr.c_st r()); // beginning of string

You also have a completely gratuitous const_cast in your code.

This last point seems fine to me. The original object was obviously
non-const, as it was created through new char[N] or allocator.alloc ate(N),
so it seems safe to use const_cast. I could be wrong though. Let me know.
I think some libraries provide only strchr(char *, char), but they should
also have strchr(const char *, char).

[John Harrison]

"Siemel Naran" <Si*********@RE MOVE.att.net> wrote in message
news:Aw******** ***********@bgt nsc04-news.ops.worldn et.att.net...

"John Harrison" <jo************ *@hotmail.com> wrote in message
news:2inljvFpkd 8vU1@uni-

"Steve" <st*******@hotm ail.com> wrote in message

int GetNewPosition( const std::string& DataStr, const int Spaces)
{
int i = 0; // space counter
char* b = const_cast<char *>(DataStr.c_st r()); // beginning of

string

You also have a completely gratuitous const_cast in your code.
This last point seems fine to me. The original object was obviously
non-const, as it was created through new char[N] or allocator.alloc ate(N),
so it seems safe to use const_cast. I could be wrong though. Let me

know. I think some libraries provide only strchr(char *, char), but they should
also have strchr(const char *, char).

I agree it's safe, but its also unnecessary. By writing const_cast the OP
gives the impression that something tricky is going on in the code, which
isn't the case. Its a completely normal function which can be written
without any casts.

C++ should provide two overloads for strchr

const char* strchr(const char*, int);

and

char* strchr(char*, int);

Because C doesn't have function overloading it can only provide one version
which is the non-const correct

char* strchr(const char*, int);

Maybe that is what persuaded the OP that he needed to use a cast.

john