How to assign -1 to size_type?

[Lambda]

I'm writing a function to partition a vector according to a predicate.
For example:

vector<string>::size_type partition(vector<Student_info> &v)
{
vector<string>::size_type i, j;
i = -1;
j = v.size();

while (true)
{
cout << i << ' ' << j << endl;
do ++i; while (i <= v.size() - 1 && !fgrade(v));
do --j; while (j >= 0 && fgrade(v[j]));
if (i > j)
break;
exchange(v, i, j);
}
return i;
}
fgrade will return true if the student's grade is less than 60.

I want the i is the position one before the first element
and j is the position one after the last element.
But size_type is an unsigned int, so it's wrong to assign -1 to i, i
will become a larger integer.
If I change type of i and j to int, I'll encounter signed/unsigned
mismatch problem.

What can I do to handle this situation?

 

[Ian Collins]

I'm writing a function to partition a vector according to a predicate.
For example:

vector<string>::size_type partition(vector<Student_info> &v)
{
vector<string>::size_type i, j;
i = -1;
j = v.size();

while (true)
{
cout << i << ' ' << j << endl;
do ++i; while (i <= v.size() - 1 && !fgrade(v));
do --j; while (j >= 0 && fgrade(v[j]));
if (i > j)
break;
exchange(v, i, j);
}
return i;
}
fgrade will return true if the student's grade is less than 60.

I want the i is the position one before the first element
and j is the position one after the last element.
But size_type is an unsigned int, so it's wrong to assign -1 to i, i
will become a larger integer.
If I change type of i and j to int, I'll encounter signed/unsigned
mismatch problem.

What can I do to handle this situation?

Use forward and reverse iterators rather than indexing.

 

[Kai-Uwe Bux]

I'm writing a function to partition a vector according to a predicate.
For example:

vector<string>::size_type partition(vector<Student_info> &v)
{
vector<string>::size_type i, j;
i = -1;
j = v.size();

while (true)
{
cout << i << ' ' << j << endl;
do ++i; while (i <= v.size() - 1 && !fgrade(v));
do --j; while (j >= 0 && fgrade(v[j]));
if (i > j)
break;
exchange(v, i, j);
}
return i;
}
fgrade will return true if the student's grade is less than 60.

I want the i is the position one before the first element
and j is the position one after the last element.
But size_type is an unsigned int, so it's wrong to assign -1 to i, i
will become a larger integer.
If I change type of i and j to int, I'll encounter signed/unsigned
mismatch problem.

What can I do to handle this situation?

You can use std:artition.


Best

Kai-Uwe Bux

 

[Lambda]

I'm writing a function to partition a vector according to a predicate.
For example:

vector<string>::size_type partition(vector<Student_info> &v)
{
vector<string>::size_type i, j;
i = -1;
j = v.size();

while (true)
{
cout << i << ' ' << j << endl;
do ++i; while (i <= v.size() - 1 && !fgrade(v));
do --j; while (j >= 0 && fgrade(v[j]));
if (i > j)
break;
exchange(v, i, j);
}
return i;
}
fgrade will return true if the student's grade is less than 60.

I want the i is the position one before the first element
and j is the position one after the last element.
But size_type is an unsigned int, so it's wrong to assign -1 to i, i
will become a larger integer.
If I change type of i and j to int, I'll encounter signed/unsigned
mismatch problem.

What can I do to handle this situation?

You can use std:artition.

Best

Kai-Uwe Bux

Thank you.
It's an exercise in a book. The author has not mentioned 'partition'
yet.
And I'd like to figure out how can I implement 'partition'.
My only idea is using reverse iterator, rend().
Using index is impossible?

 

[Bo Persson]

I'm writing a function to partition a vector according to a
predicate. For example:

vector<string>::size_type partition(vector<Student_info> &v)
{
vector<string>::size_type i, j;
i = -1;
j = v.size();

while (true)
{
cout << i << ' ' << j << endl;
do ++i; while (i <= v.size() - 1 && !fgrade(v));
do --j; while (j >= 0 && fgrade(v[j]));
if (i > j)
break;
exchange(v, i, j);
}
return i;
}
fgrade will return true if the student's grade is less than 60.

I want the i is the position one before the first element
and j is the position one after the last element.
But size_type is an unsigned int, so it's wrong to assign -1 to
i, i will become a larger integer.
If I change type of i and j to int, I'll encounter signed/unsigned
mismatch problem.

What can I do to handle this situation?

You can use std:artition.

Best

Kai-Uwe Bux

Thank you.
It's an exercise in a book. The author has not mentioned 'partition'
yet.
And I'd like to figure out how can I implement 'partition'.
My only idea is using reverse iterator, rend().
Using index is impossible?

It is much harder, obviously.

The usual way to process a vector is to use v.begin() and v.end(), or
v.rbegin() and v.rend() if you want to traverse in the other
direction.

In this case, where size_type is unsigned, assigning size_type(-1)
actually works. Unsigned types do wrap around, instead of overflowing.
It wouldn't make you program very easy to understand though.


Also, after solving the problem with i, you have another problem with
the j variable. As it is unsigned, the comparison "while (j >= 0" will
always be true. An unsigned variable cannot easily be less that zero,
can it?


Bo Persson

 

[Kai-Uwe Bux]

I'm writing a function to partition a vector according to a predicate.
For example:

vector<string>::size_type partition(vector<Student_info> &v)
{
vector<string>::size_type i, j;
i = -1;
j = v.size();

while (true)
{
cout << i << ' ' << j << endl;
do ++i; while (i <= v.size() - 1 && !fgrade(v));
do --j; while (j >= 0 && fgrade(v[j]));
if (i > j)
break;
exchange(v, i, j);
}
return i;
}
fgrade will return true if the student's grade is less than 60.

I want the i is the position one before the first element
and j is the position one after the last element.
But size_type is an unsigned int, so it's wrong to assign -1 to i, i
will become a larger integer.
If I change type of i and j to int, I'll encounter signed/unsigned
mismatch problem.

What can I do to handle this situation?

You can use std:artition.

Best

Kai-Uwe Bux

Thank you.
It's an exercise in a book. The author has not mentioned 'partition'
yet.
And I'd like to figure out how can I implement 'partition'.
My only idea is using reverse iterator, rend().
Using index is impossible?

If you are going for the learning experience, then I suggest you really
implement the generic algorithm "partition". Here is a starting point:

template < typename Iter, typename Pred >
Iter partition ( Iter begin, Iter end, Pred p ) {
Iter from = begin;
Iter to = end;
while ( from != to ) {
// loop invariant:
// a) all elements in [begin,from) satisfy p.
// b) all elements in [to, end) don't satisfy p.
...
}
return ( from );
}

You are allowed to assume that Iter is a bidirectional iterator type. That
is, you can use ++ and --. So, all you have to do inside the loop is
getting from and to one step closer together possibly doing a swap.


Hope that helps

Kai-Uwe Bux

 

[Lambda]

Lambda wrote:
I'm writing a function to partition a vector according to a
predicate. For example:
vector<string>::size_type partition(vector<Student_info> &v)
{
vector<string>::size_type i, j;
i = -1;
j = v.size();
while (true)
{
cout << i << ' ' << j << endl;
do ++i; while (i <= v.size() - 1 && !fgrade(v));
do --j; while (j >= 0 && fgrade(v[j]));
if (i > j)
break;
exchange(v, i, j);
}
return i;
}
fgrade will return true if the student's grade is less than 60.
I want the i is the position one before the first element
and j is the position one after the last element.
But size_type is an unsigned int, so it's wrong to assign -1 to
i, i will become a larger integer.
If I change type of i and j to int, I'll encounter signed/unsigned
mismatch problem.
What can I do to handle this situation?
You can use std:artition.
Best
Kai-Uwe Bux

Thank you.
It's an exercise in a book. The author has not mentioned 'partition'
yet.
And I'd like to figure out how can I implement 'partition'.
My only idea is using reverse iterator, rend().
Using index is impossible?

It is much harder, obviously.

The usual way to process a vector is to use v.begin() and v.end(), or
v.rbegin() and v.rend() if you want to traverse in the other
direction.

In this case, where size_type is unsigned, assigning size_type(-1)
actually works. Unsigned types do wrap around, instead of overflowing.
It wouldn't make you program very easy to understand though.

Also, after solving the problem with i, you have another problem with
the j variable. As it is unsigned, the comparison "while (j >= 0" will
always be true. An unsigned variable cannot easily be less that zero,
can it?

Bo Persson

Yes, j is another problem. Checking j >= 0 is not effective.
Now I understand why iterator is more powerful than index with C++.

Stephen Hsu

 

[Lambda]

Lambda wrote:
I'm writing a function to partition a vector according to a predicate.
For example:
vector<string>::size_type partition(vector<Student_info> &v)
{
vector<string>::size_type i, j;
i = -1;
j = v.size();
while (true)
{
cout << i << ' ' << j << endl;
do ++i; while (i <= v.size() - 1 && !fgrade(v));
do --j; while (j >= 0 && fgrade(v[j]));
if (i > j)
break;
exchange(v, i, j);
}
return i;
}
fgrade will return true if the student's grade is less than 60.
I want the i is the position one before the first element
and j is the position one after the last element.
But size_type is an unsigned int, so it's wrong to assign -1 to i, i
will become a larger integer.
If I change type of i and j to int, I'll encounter signed/unsigned
mismatch problem.
What can I do to handle this situation?
You can use std:artition.
Best
Kai-Uwe Bux

Thank you.
It's an exercise in a book. The author has not mentioned 'partition'
yet.
And I'd like to figure out how can I implement 'partition'.
My only idea is using reverse iterator, rend().
Using index is impossible?

If you are going for the learning experience, then I suggest you really
implement the generic algorithm "partition". Here is a starting point:

template < typename Iter, typename Pred >
Iter partition ( Iter begin, Iter end, Pred p ) {
Iter from = begin;
Iter to = end;
while ( from != to ) {
// loop invariant:
// a) all elements in [begin,from) satisfy p.
// b) all elements in [to, end) don't satisfy p.
...
}
return ( from );
}

You are allowed to assume that Iter is a bidirectional iterator type. That
is, you can use ++ and --. So, all you have to do inside the loop is
getting from and to one step closer together possibly doing a swap.

Hope that helps

Kai-Uwe Bux

Implementing the partition generic algorithm is not a easy task, let
me try later.
Just a question, if i and j are adjust, in the next step,
i and j will exchange their places. It's possible that they will never
be equal.
What do you think?

Stephen Hsu

 

[utab]

Lambda wrote:
I'm writing a function to partition a vector according to a predicate.
For example:
vector<string>::size_type partition(vector<Student_info> &v)
{
vector<string>::size_type i, j;
i = -1;
j = v.size();
while (true)
{
cout << i << ' ' << j << endl;
do ++i; while (i <= v.size() - 1 && !fgrade(v));
do --j; while (j >= 0 && fgrade(v[j]));
if (i > j)
break;
exchange(v, i, j);
}
return i;
}
fgrade will return true if the student's grade is less than 60.
I want the i is the position one before the first element
and j is the position one after the last element.
But size_type is an unsigned int, so it's wrong to assign -1 to i, i
will become a larger integer.
If I change type of i and j to int, I'll encounter signed/unsigned
mismatch problem.
What can I do to handle this situation?
You can use std:artition.
Best
Kai-Uwe Bux
Thank you.
It's an exercise in a book. The author has not mentioned 'partition'
yet.
And I'd like to figure out how can I implement 'partition'.
My only idea is using reverse iterator, rend().
Using index is impossible?

If you are going for the learning experience, then I suggest you really
implement the generic algorithm "partition". Here is a starting point:

template < typename Iter, typename Pred >
Iter partition ( Iter begin, Iter end, Pred p ) {
Iter from = begin;
Iter to = end;
while ( from != to ) {
// loop invariant:
// a) all elements in [begin,from) satisfy p.
// b) all elements in [to, end) don't satisfy p.
...
}
return ( from );
}

You are allowed to assume that Iter is a bidirectional iterator type. That
is, you can use ++ and --. So, all you have to do inside the loop is
getting from and to one step closer together possibly doing a swap.

Hope that helps

Kai-Uwe Bux

Implementing the partition generic algorithm is not a easy task, let
me try later.

You are going to implement them in chapter 8 anyway.

 

[James Kanze]

On Apr 20, 7:11 pm, "Bo Persson" <[email protected]> wrote:

[...]

Yes, j is another problem. Checking j >= 0 is not effective.

No. But you don't really have to, do you?

Now I understand why iterator is more powerful than index with
C++.

An iterator is more powerful because it can apply to containers
which don't support random access. As soon as you have random
access, iterator operations map exactly to index operations.

I've not looked at his code, but off hand, I don't see the need
to ever go backwards to create a partition. If the container is
already sorted, a binary search will reveal the correct element
immediately. Otherwise, something like the following can be
used:

template< typename ForwardIterator, class Predicate >
ForwardIterator
partition(
ForwardIterator first,
ForwardIterator last,
Predicate pred )
{
ForwardIterator pivot = first ;
while ( pivot != last && pred( *pivot ) ) {
++ pivot ;
}
if ( pivot != last ) {
ForwardIterator visited = pivot ;
while ( visited != last ) {
if ( pred( *visited ) ) {
std::swap( *pivot, *visited ) ;
++ pivot ;
}
++ visited ;
}
}
return pivot ;
}

And if all you need to deal with is std::vector, this can easily
be rewritten to use the vector and indexes: just pass the vector
instead of the two iterators, use 0 for first, vector.size() for
last, a size_t for the other iterator, and replace each
dereference of the iterator with an index operation on the
vector.

(And while I'm at it, I wonder why the standard requires a
BidirectionalIterator for partition, when it obviously isn't
necessary.)

 

[James Kanze]

Lambda wrote:

[...]

If you are going for the learning experience, then I suggest
you really implement the generic algorithm "partition". Here
is a starting point:

template < typename Iter, typename Pred >
Iter partition ( Iter begin, Iter end, Pred p ) {
Iter from = begin;
Iter to = end;
while ( from != to ) {
// loop invariant:
// a) all elements in [begin,from) satisfy p.
// b) all elements in [to, end) don't satisfy p.
...
}
return ( from );
}

You are allowed to assume that Iter is a bidirectional
iterator type. That is, you can use ++ and --. So, all you
have to do inside the loop is getting from and to one step
closer together possibly doing a swap.

That's the tricky way of doing it, however, since in some cases,
you might instictively want to both increment and decrement, and
if the distance between the two iterators is only one, you'd
best not. (Of course, an additional test can, and should be
used, to avoid this case.) I find it much easier to use a few
extra variables:

Iter pivot = begin ;
Iter top = begin ;
while ( top != end ) {
// loop invariants:
// 1) all elements in [begin...pivot) satisfy p.
// 2) none of the elements in [pivot, top) satisfy p.
// And of course, we advance top each time through
// the loop, so we know we are making progress.
}

Personally, I find this one considerably easier to reason about
(but that may just be a personal preference). It also has the
advantage that it only requires a forward iterator, not a
bidirectional one.

 

[James Kanze]

If you are going for the learning experience, then I suggest
you really implement the generic algorithm "partition". Here
is a starting point:
template < typename Iter, typename Pred >
Iter partition ( Iter begin, Iter end, Pred p ) {
Iter from = begin;
Iter to = end;
while ( from != to ) {
// loop invariant:
// a) all elements in [begin,from) satisfy p.
// b) all elements in [to, end) don't satisfy p.
...
}
return ( from );
}
You are allowed to assume that Iter is a bidirectional
iterator type. That is, you can use ++ and --. So, all you
have to do inside the loop is getting from and to one step
closer together possibly doing a swap.

Implementing the partition generic algorithm is not a easy
task, let me try later.

It's not really harder to write. Still, until you're really
experienced at this sort of thing, I'd start with a non-generic
form. If only because the error messages from the compiler will
be much easier to understand.

Just a question, if i and j are adjust, in the next step, i
and j will exchange their places. It's possible that they will
never be equal. What do you think?

If j - i == 1, and you decrement j and increment i, they will
never be equal, and you're loop will never terminate.
(Actually, it will terminate, with a core dump, when you get out
of bounds.) So don't do it.

Basically: indexes or iterators (using the above algorithm), you
should systematically check for equality before incrementing or
decrementing, except in the special case where you can prove
that it is impossible. (In your code, the while establishes the
inquality for the first increment or decrement, but from then
on, you have to check.)

There are definitely simpler algorithms to do this, however.
See my other posting.

 

[Kai-Uwe Bux]

Lambda wrote:
[...]
If you are going for the learning experience, then I suggest
you really implement the generic algorithm "partition". Here
is a starting point:

template < typename Iter, typename Pred >
Iter partition ( Iter begin, Iter end, Pred p ) {
Iter from = begin;
Iter to = end;
while ( from != to ) {
// loop invariant:
// a) all elements in [begin,from) satisfy p.
// b) all elements in [to, end) don't satisfy p.
...
}
return ( from );
}

You are allowed to assume that Iter is a bidirectional
iterator type. That is, you can use ++ and --. So, all you
have to do inside the loop is getting from and to one step
closer together possibly doing a swap.

That's the tricky way of doing it, however, since in some cases,
you might instictively want to both increment and decrement, and
if the distance between the two iterators is only one, you'd
best not. (Of course, an additional test can, and should be
used, to avoid this case.) I find it much easier to use a few
extra variables:

Iter pivot = begin ;
Iter top = begin ;
while ( top != end ) {
// loop invariants:
// 1) all elements in [begin...pivot) satisfy p.
// 2) none of the elements in [pivot, top) satisfy p.
// And of course, we advance top each time through
// the loop, so we know we are making progress.
}

Personally, I find this one considerably easier to reason about
(but that may just be a personal preference). It also has the
advantage that it only requires a forward iterator, not a
bidirectional one.

I agree: that is better. The version I suggested is closer to the code that
the OP posted and might be a better starting point for Lamda.


Best

Kai-Uwe Bux

 

[Lambda]

[...]

Also, after solving the problem with i, you have another problem with
the j variable. As it is unsigned, the comparison "while (j >= 0" will
always be true. An unsigned variable cannot easily be less that zero,
can it?

Yes, j is another problem. Checking j >= 0 is not effective.

No. But you don't really have to, do you?

Now I understand why iterator is more powerful than index with
C++.

An iterator is more powerful because it can apply to containers
which don't support random access. As soon as you have random
access, iterator operations map exactly to index operations.

I've not looked at his code, but off hand, I don't see the need
to ever go backwards to create a partition. If the container is
already sorted, a binary search will reveal the correct element
immediately. Otherwise, something like the following can be
used:

template< typename ForwardIterator, class Predicate >
ForwardIterator
partition(
ForwardIterator first,
ForwardIterator last,
Predicate pred )
{
ForwardIterator pivot = first ;
while ( pivot != last && pred( *pivot ) ) {
++ pivot ;
}
if ( pivot != last ) {
ForwardIterator visited = pivot ;
while ( visited != last ) {
if ( pred( *visited ) ) {
std::swap( *pivot, *visited ) ;
++ pivot ;
}
++ visited ;
}
}
return pivot ;
}

And if all you need to deal with is std::vector, this can easily
be rewritten to use the vector and indexes: just pass the vector
instead of the two iterators, use 0 for first, vector.size() for
last, a size_t for the other iterator, and replace each
dereference of the iterator with an index operation on the
vector.

(And while I'm at it, I wonder why the standard requires a
BidirectionalIterator for partition, when it obviously isn't
necessary.)

--
James Kanze (GABI Software) email:[email protected]
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34

Hi James,

I implement the algo follow the ForwardIter version of partition
of SGI's STL implementation that similar to your algo.

The SGI's implementation use iterator,
I use index with exactly the same idea.

The idea is clear, all the 'one before the first element' issues
are eliminated. Using two index didn't help me.

 

[Lambda]

...
I want the i is the position one before the first element
and j is the position one after the last element.
But size_type is an unsigned int, so it's wrong to assign -1 to i, i
will become a larger integer.
If I change type of i and j to int, I'll encounter signed/unsigned
mismatch problem.

What can I do to handle this situation?

Well, you can use '(size_type) -1' as the index of the element before the first
one. Of course, you'll have to remember that this value is still positive, so
you'll have to adjust you comparisons accordingly, i.e instead of looking for a
value that is less than zero look for value that is greater than the total size
of the vector.

For example, your conditions in the cycles might now look as follows

do ++i; while (i < v.size() && !fgrade(v));
do --j; while (j < v.size() && fgrade(v[j]));

This looks strange, I know, and it might be a bit hard to understand to an
unprepared reader, but it is in fact an idiom worth learning, when working with
unsigned types. Actually, it has a certain elegance to it, since both cycle
conditions now look the same

Another approach would be to redesign your algorithm in other to eliminate the
need for the "index before the first" altogether. This actually might be a
better idea, because when you'll work, for example, with pointers or iterators
instead of indexes, you won't have the luxury of defined wraparound behavior of
unsigned types. For this reason, it is a good idea to learn the corresponding
idioms, which will help you to do the same thing without the need to rely on the
wraparound.

As I find, I can eliminate the need for the "index before the first"
altogether.
The code I post above is clearer and better than the old one.

For example, a common idiom would be to replace the signed cycle

for (int i = N; i >= 0; --i) {
...

with an unsigned cycle

for (unsigned i = N; i > 0; ) {
--i;
...

or, as some might prefer

for (unsigned i = N; i-- > 0; ) {
...

You can try something like that in your algorithm.

Thank you Andrey, the idiom is useful. Let me memorize it.