[Filesystem] Reverse traversal of boost::filesystem::path::const_iterator?
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?
On Thu, Nov 1, 2012 at 4:07 AM, Nat Linden <nat@lindenlab.com> 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])."
On Thu, Nov 1, 2012 at 11:55 AM, Joshua Boyce <raptorfactor@raptorfactor.com> wrote:
On Thu, Nov 1, 2012 at 4:07 AM, Nat Linden <nat@lindenlab.com> 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...)
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 <raptorfactor@raptorfactor.com> wrote:
On Thu, Nov 1, 2012 at 4:07 AM, Nat Linden <nat@lindenlab.com> 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
On Fri, Nov 2, 2012 at 8:43 AM, Sebastian Messerschmidt <sebastian.messerschmidt@gmx.de> 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?
Hi Nat, On Fri, Nov 2, 2012 at 9:22 AM, Nat Linden <nat@lindenlab.com> 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
On Fri, Nov 2, 2012 at 12:06 PM, Nathan Crookston <nathan.crookston@gmail.com> 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().
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
On Wed, Oct 31, 2012 at 10:07 AM, Nat Linden <nat@lindenlab.com> 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
participants (6)
-
Jeffrey Lee Hellrung, Jr. -
Joshua Boyce -
Nat Linden -
Nathan Crookston -
Nathan Ridge -
Sebastian Messerschmidt