2674. Bidirectional iterator requirement on path::iterator is very expensive

Section: 30.11.7.5 [fs.path.itr] Status: C++17 Submitter: Jonathan Wakely Opened: 2015-09-15 Last modified: 2017-07-30

Priority: 2

View all issues with C++17 status.

Discussion:

30.11.7.5 [fs.path.itr] requires path::iterator to be a BidirectionalIterator, which also implies the ForwardIterator requirement in [forward.iterators] p6 for the following assertion to pass:

path p("/");
auto it1 = p.begin();
auto it2 = p.begin();
assert( &*it1 == &*it2 );

This prevents iterators containing a path, or constructing one on the fly when dereferenced, the object they point to must exist outside the iterators and potentially outlive them. The only practical way to meet the requirement is for p to hold a container of child path objects so the iterators can refer to those children. This makes a path object much larger than would naïvely be expected.

The Boost and MSVC implementations of Filesystem fail to meet this requirement. The GCC implementation meets it, but it makes sizeof(path) == 64 (for 64-bit) or sizeof(path) == 40 for 32-bit, and makes many path operations more expensive.

[21 Nov 2015 Beman comments:]

The ForwardIterator requirement in [forward.iterators] "If a and b are both dereferenceable, then a == b if and only if *a and *b are bound to the same object." will be removed by N4560, Working Draft, C++ Extensions for Ranges. I see no point in requiring something for the File System TS that is expensive, has never to my knowledge been requested by users, and is going to go away soon anyhow. The wording I propose below removes the requirement.

[Apr 2016 Issue updated to address the C++ Working Paper. Previously addressed File System TS]

Proposed resolution:

This wording is relative to N4582.

  1. Change 30.11.7.5 [fs.path.itr] paragraph 2:

    A path::iterator is a constant iterator satisfying all the requirements of a bidirectional iterator (C++14 §24.1.4 Bidirectional iterators) except that there is no requirement that two equal iterators be bound to the same object. Its value_type is path.