[Filesystem] Reverse traversal of boost::filesystem::path::const_iterator?

Nat Linden

31 Oct 2012 31 Oct '12

5:07 p.m.

I've stumbled across some code in our code base that wants to walk up a fixed number of containing parent directories from the starting path. (It's in a Mac application bundle nested within another.) boost::filesystem::path::[const_]iterator is described as bidirectional. But boost::filesystem::path has no rbegin() or rend(). In libs/filesystem/test/path_test.cpp's iterator_tests(), I see, for a path variable named itr_ck, use of boost::prior(itr_ck.end()). That suggests that usage of this form would be legal: path mypath = /* ...something... */; for (path::const_iterator rcomp(mypath.end()), rend(mypath.begin()); rcomp != rend; --rcomp) { // ... use boost::prior(rcomp) ... } Am I correct? Given the way some containers implement end(), I always feel nervous about decrementing end(). I'm happy to see that Boost.Filesystem's own tests guarantee that usage; but is there anything in the documentation that would have assured me of that?

Show replies by date

Joshua Boyce

1 Nov 1 Nov

3:55 p.m.

On Thu, Nov 1, 2012 at 4:07 AM, Nat Linden wrote:

...

Am I correct? Given the way some containers implement end(), I always feel nervous about decrementing end(). I'm happy to see that Boost.Filesystem's own tests guarantee that usage; but is there anything in the documentation that would have assured me of that?

http://www.boost.org/doc/libs/1_49_0/libs/filesystem/v3/doc/reference.html#p... "A path::iterator is a constant iterator satisfying all the requirements of a bidirectional iterator (C++ Std, 24.1.4 Bidirectional iterators [lib.bidirectional.iterators])."

Nat Linden

8:01 p.m.

On Thu, Nov 1, 2012 at 11:55 AM, Joshua Boyce wrote:

...

On Thu, Nov 1, 2012 at 4:07 AM, Nat Linden wrote:

...

...
Am I correct? Given the way some containers implement end(), I always feel nervous about decrementing end(). I'm happy to see that Boost.Filesystem's own tests guarantee that usage; but is there anything in the documentation that would have assured me of that?

...

http://www.boost.org/doc/libs/1_49_0/libs/filesystem/v3/doc/reference.html#p...

"A path::iterator is a constant iterator satisfying all the requirements of a bidirectional iterator (C++ Std, 24.1.4 Bidirectional iterators [lib.bidirectional.iterators])."

Until I can dig up a copy of the standard -- pardon me, but this feels slightly divergent from the question I'm asking. Does the standard's description of "bidirectional iterators" guarantee the operations legal on the value returned by a container's end() method? The only operation I feel confident assuming on a value returned by a container's end() method is [in]equality comparison with another iterator value. (Of course, this discussion would be moot if boost::filesystem::path supported rbegin() and rend() methods... hint, hint...)

Sebastian Messerschmidt

2 Nov 2 Nov

12:43 p.m.

Hello Nat, Bidirectional Iterators and rbegin/rend are not necessarily the same thing. The bidirectional property only guarantees that the operator-- is supported [1] additionally to the ++ operator. [1] http://www.sgi.com/tech/stl/BidirectionalIterator.html cheers Sebastian

...

On Thu, Nov 1, 2012 at 11:55 AM, Joshua Boyce wrote:

...
On Thu, Nov 1, 2012 at 4:07 AM, Nat Linden wrote:

...
Am I correct? Given the way some containers implement end(), I always feel nervous about decrementing end(). I'm happy to see that Boost.Filesystem's own tests guarantee that usage; but is there anything in the documentation that would have assured me of that? http://www.boost.org/doc/libs/1_49_0/libs/filesystem/v3/doc/reference.html#p...

"A path::iterator is a constant iterator satisfying all the requirements of a bidirectional iterator (C++ Std, 24.1.4 Bidirectional iterators [lib.bidirectional.iterators])." Until I can dig up a copy of the standard -- pardon me, but this feels slightly divergent from the question I'm asking. Does the standard's description of "bidirectional iterators" guarantee the operations legal on the value returned by a container's end() method?

The only operation I feel confident assuming on a value returned by a container's end() method is [in]equality comparison with another iterator value.

(Of course, this discussion would be moot if boost::filesystem::path supported rbegin() and rend() methods... hint, hint...) _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

Nat Linden

3:22 p.m.

On Fri, Nov 2, 2012 at 8:43 AM, Sebastian Messerschmidt wrote:

...

Bidirectional Iterators and rbegin/rend are not necessarily the same thing.

Understood. I mention rbegin()/rend() only to say that if boost::filesystem::path supported them, my question about boost::filesystem::path::end() would become moot because I would use the rbegin()/rend() idiom instead.

...

The bidirectional property only guarantees that the operator-- is supported [1] additionally to the ++ operator.

To be clear about my question, let me pose it as a syllogism, where 'container' is an instance of SomeContainer: IF SomeContainer::end() is documented to return a bidirectional iterator, AND container.end() != container.begin(), THEN the following code is valid, and references the last item in container: SomeContainer::const_iterator it = container.end(); --it; SomeContainer::value_type const& last = *it; Always true?

Nathan Crookston

4:06 p.m.

Hi Nat, On Fri, Nov 2, 2012 at 9:22 AM, Nat Linden wrote:

...

IF SomeContainer::end() is documented to return a bidirectional iterator, AND container.end() != container.begin(), THEN the following code is valid, and references the last item in container:

SomeContainer::const_iterator it = container.end(); --it; SomeContainer::value_type const& last = *it;

Always true?

It isn't really clear to me by me reading of the standard (well, n3126). On the one hand, in 24.2.6, the pre/post conditions are: pre: there exists s such that r == ++s. post: r is dereferenceable. --(++r) == r. --r == --s implies r == s. &r == &--r. Given that s references the last element, and r is the past-the-end iterator, then it would imply that your syllogism is true. Of course, a previous section (24.2.1.5) talks about the possibility of singular iterators and default constructable iterators. I've never seen such things in the context of a bidirectional iterator. Of course, having now quoted the standard, this is when someone that really knows what they're talking about comes and corrects me. ;) HTH, Nate

Nat Linden

5:30 p.m.

On Fri, Nov 2, 2012 at 12:06 PM, Nathan Crookston wrote:

...

Given that s references the last element, and r is the past-the-end iterator, then it would imply that your syllogism is true.

That's really the question, isn't it. If a container's end() method is documented to return a bidirectional iterator, is that iterator value guaranteed to be past-the-end, or might it reasonably be a singular iterator?

...

Of course, a previous section (24.2.1.5) talks about the possibility of singular iterators and default constructable iterators. I've never seen such things in the context of a bidirectional iterator.

Good to know... My question all along has been: to a knowledgeable reader, is the documented assertion that boost::filesystem::path::const_iterator is a bidirectional iterator sufficient to imply that, given a non-empty boost::filesystem::path value, you can validly decrement and dereference the iterator returned by path::end()? It appears that there's room for doubt about this implication. For me, the bottom line is a request to add to the Boost.Filesystem documentation a promise that it's valid to traverse a boost::filesystem::path value backwards by decrementing the value returned by path::end().

Nathan Ridge

9:01 p.m.

New subject: [Filesystem] Reverse traversal of boost::filesystem::path::const_iterator?

...

To be clear about my question, let me pose it as a syllogism, where 'container' is an instance of SomeContainer:

IF SomeContainer::end() is documented to return a bidirectional iterator, AND container.end() != container.begin(), THEN the following code is valid, and references the last item in container:

SomeContainer::const_iterator it = container.end(); --it; SomeContainer::value_type const& last = *it;

Always true?

I'm not a language lawyer, but I'll point out that at least boost::reverse_iterator [1] seems to assume this (I don't see how it could be implemented otherwise). (Not so) incidentally, boost::reverse_iterator seems like an appropriate solution to your original problem of iterating over a path in reverse :) Regards, Nate [1] http://www.boost.org/doc/libs/1_51_0/libs/iterator/doc/reverse_iterator.html

Jeffrey Lee Hellrung, Jr.

10:39 p.m.

On Wed, Oct 31, 2012 at 10:07 AM, Nat Linden wrote:

...

I've stumbled across some code in our code base that wants to walk up a fixed number of containing parent directories from the starting path. (It's in a Mac application bundle nested within another.) boost::filesystem::path::[const_]iterator is described as bidirectional. But boost::filesystem::path has no rbegin() or rend().

In libs/filesystem/test/path_test.cpp's iterator_tests(), I see, for a path variable named itr_ck, use of boost::prior(itr_ck.end()). That suggests that usage of this form would be legal:

path mypath = /* ...something... */; for (path::const_iterator rcomp(mypath.end()), rend(mypath.begin()); rcomp != rend; --rcomp) { // ... use boost::prior(rcomp) ... }

Am I correct? Given the way some containers implement end(), I always feel nervous about decrementing end(). I'm happy to see that Boost.Filesystem's own tests guarantee that usage; but is there anything in the documentation that would have assured me of that?

If an iterator is bidirectional, you can decrement any iterator not equal to the begin of the range. I.e., decrementing from end is fine (so long as the range is non-empty). - Jeff

4411

Age (days ago)

4413

Last active (days ago)

List overview

Download

8 comments

6 participants

participants (6)

Jeffrey Lee Hellrung, Jr.
Joshua Boyce
Nat Linden
Nathan Crookston
Nathan Ridge
Sebastian Messerschmidt