How to assign -1 to size_type?

Discussion in 'C++' started by Lambda, Apr 20, 2008.

  1. Lambda

    Lambda Guest

    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?
    Lambda, Apr 20, 2008
    #1
    1. Advertising

  2. Lambda

    Ian Collins Guest

    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?


    Use forward and reverse iterators rather than indexing.

    --
    Ian Collins.
    Ian Collins, Apr 20, 2008
    #2
    1. Advertising

  3. Lambda

    Kai-Uwe Bux Guest

    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::partition.


    Best

    Kai-Uwe Bux
    Kai-Uwe Bux, Apr 20, 2008
    #3
  4. Lambda

    Lambda Guest

    On Apr 20, 5:09 pm, Kai-Uwe Bux <> wrote:
    > 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::partition.
    >
    > 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?
    Lambda, Apr 20, 2008
    #4
  5. Lambda

    Bo Persson Guest

    Lambda wrote:
    > On Apr 20, 5:09 pm, Kai-Uwe Bux <> wrote:
    >> 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::partition.
    >>
    >> 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
    Bo Persson, Apr 20, 2008
    #5
  6. Lambda

    Kai-Uwe Bux Guest

    Lambda wrote:

    > On Apr 20, 5:09 pm, Kai-Uwe Bux <> wrote:
    >> 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::partition.
    >>
    >> 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
    Kai-Uwe Bux, Apr 20, 2008
    #6
  7. Lambda

    Lambda Guest

    On Apr 20, 7:11 pm, "Bo Persson" <> wrote:
    > Lambda wrote:
    > > On Apr 20, 5:09 pm, Kai-Uwe Bux <> wrote:
    > >> 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::partition.

    >
    > >> 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, Apr 20, 2008
    #7
  8. Lambda

    Lambda Guest

    On Apr 20, 7:21 pm, Kai-Uwe Bux <> wrote:
    > Lambda wrote:
    > > On Apr 20, 5:09 pm, Kai-Uwe Bux <> wrote:
    > >> 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::partition.

    >
    > >> 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
    Lambda, Apr 20, 2008
    #8
  9. Lambda

    utab Guest

    On Apr 20, 2:08 pm, Lambda <> wrote:
    > On Apr 20, 7:21 pm, Kai-Uwe Bux <> wrote:
    >
    >
    >
    > > Lambda wrote:
    > > > On Apr 20, 5:09 pm, Kai-Uwe Bux <> wrote:
    > > >> 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::partition.

    >
    > > >> 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.

    > 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, Apr 20, 2008
    #9
  10. Lambda

    James Kanze Guest

    On 20 avr, 13:57, Lambda <> wrote:
    > On Apr 20, 7:11 pm, "Bo Persson" <> wrote:


    [...]
    > > 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:
    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
    James Kanze, Apr 20, 2008
    #10
  11. Lambda

    James Kanze Guest

    On 20 avr, 13:21, Kai-Uwe Bux <> wrote:
    > 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 (GABI Software) email:
    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
    James Kanze, Apr 20, 2008
    #11
  12. Lambda

    James Kanze Guest

    On 20 avr, 14:08, Lambda <> wrote:
    > On Apr 20, 7:21 pm, Kai-Uwe Bux <> 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.


    > 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.

    --
    James Kanze (GABI Software) email:
    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
    James Kanze, Apr 20, 2008
    #12
  13. Lambda

    Kai-Uwe Bux Guest

    James Kanze wrote:

    > On 20 avr, 13:21, Kai-Uwe Bux <> wrote:
    >> 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
    Kai-Uwe Bux, Apr 20, 2008
    #13
  14. Lambda

    Lambda Guest

    On Apr 21, 12:08 am, James Kanze <> wrote:
    > On 20 avr, 13:57, Lambda <> wrote:
    >
    > > On Apr 20, 7:11 pm, "Bo Persson" <> wrote:

    >
    > [...]
    >
    > > > 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:
    > 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, Apr 21, 2008
    #14
  15. Lambda

    Lambda Guest

    On Apr 21, 4:09 am, Andrey Tarasevich <>
    wrote:
    > Lambda wrote:
    > > ...
    > > 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. :)

    >
    > Finally, there's the "loser's way out": use a signed type for the index and
    > silence the warnings by using explicit casts and/or compiler settings. This is,
    > of course, the ugliest approach.
    >
    > --
    > Best regards,
    > Andrey Tarasevich
    Lambda, Apr 21, 2008
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Fraser Ross

    allocator size_type

    Fraser Ross, Jul 31, 2003, in forum: C++
    Replies:
    1
    Views:
    426
    John Harrison
    Jul 31, 2003
  2. Kevin Goodsell

    size_type requirements

    Kevin Goodsell, Sep 12, 2003, in forum: C++
    Replies:
    1
    Views:
    518
    Josh Sebastian
    Sep 13, 2003
  3. Alex J. Dam

    size_type, pos_type, etc.

    Alex J. Dam, Jan 26, 2004, in forum: C++
    Replies:
    6
    Views:
    5,673
    Ron Natalie
    Jan 27, 2004
  4. Denis Remezov

    size_t and size_type

    Denis Remezov, Apr 1, 2004, in forum: C++
    Replies:
    9
    Views:
    19,054
    Pete Becker
    Apr 3, 2004
  5. Replies:
    2
    Views:
    468
Loading...

Share This Page