12

I have a class akin to the following:

struct Config
{
   using BindingContainer = std::map<ID, std::vector<Binding>>;
   using BindingIterator  = BindingContainer::mapped_type::const_iterator;

   boost::iterator_range<BindingIterator> bindings(ID id) const;
private:
   BindingContainer m_bindings;
};

Since the ID passed to bindings() might not exist, I need to be able to represent a 'no bindings' value in the return type domain.

I don't need to differentiate an unknown ID from an ID mapped to an empty vector, so I was hoping to be able to achieve this with the interface as above and return an empty range with default-constructed iterators. Unfortunately, although a ForwardIterator is DefaultConstructible [C++11 24.2.5/1] the result of comparing a singular iterator is undefined [24.2.1/5], so without a container it seems this is not possible.

I could change the interface to e.g wrap the iterator_range in a boost::optional, or return a vector value instead; the former is a little more clunky for the caller though, and the latter has undesirable copy overheads.

Another option is to keep a statically-allocated empty vector and return its iterators. The overhead wouldn't be problematic in this instance, but I'd like to avoid it if I can.

Adapting the map iterator to yield comparable default-constructed iterators is a possibility, though seems over-complex...

Are there any other options here that would support returning an empty range when there is no underlying container?

(Incidentally I'm sure a while back I read a working paper or article about producing empty ranges for standard container type when there is no container object, but can't find anything now.)

(Note I am limited to C++11 features, though I'd be interested if there is any different approach requiring later features.)

Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
boycy
  • 1,473
  • 12
  • 25
  • 1
    In my mind an empty range would be one where `begin` equals `end`. – Some programmer dude Mar 31 '15 at 09:49
  • 4
    [N3644](http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3644.pdf). In C++14, value-initialized forward iterators can be compared to each other and must compare equal. – T.C. Mar 31 '15 at 09:50
  • @Joachim - yes, that's what I'd like, but AFAICT I can't create that without a container due to the undefined result cited from the standard. – boycy Mar 31 '15 at 09:51
  • Thanks @T.C. that's exactly the paper I was thinking of. – boycy Mar 31 '15 at 09:55
  • You could use a `unique_ptr` to hold the pair, and leave it unitialized to represent 'no bindings'. – Jonathan Potter Mar 31 '15 at 09:57
  • 1
    @JonathanPotter - that's equivalent in functionality as a `boost::optional`, but with added performance penalty and less accurate semantics. – boycy Mar 31 '15 at 10:01
  • vector iterators are usually pointers. two `nullptr` will compare equal – sp2danny Mar 31 '15 at 11:14
  • @sp2danny the standard allows for default-constructed iterators (which are singular) to have uninitialised pointers internally, hence "the result of comparing a singular iterator is undefined". – boycy Mar 31 '15 at 11:28
  • it might not be portable, or perfectly standards conforming, but on most implementations, `std::vector::iterator` wont *contain* a `T*`, it **is** a `T*` – sp2danny Mar 31 '15 at 13:35
  • I don't feel comfortable baking that assumption into code for which the standard library implementation is not guaranteed to be fixed for the code's lifetime, since a change may silently break it. Thanks for your input though. – boycy Mar 31 '15 at 13:52
  • 2
    @sp2danny On most modern implementations, `std::vector::iterator` is *not* a `T*`. – T.C. Mar 31 '15 at 15:39
  • Can one of you cite your assertions? – boycy Apr 01 '15 at 08:33
  • I looked it up. It has changed since last I did. Forget what I said – sp2danny Apr 01 '15 at 12:34

2 Answers2

3

Nope, there aren't. Your options are as you suggest. Personally, I would probably go with the idea of hijacking an iterator pair from a static empty vector; I can't imagine what notional "overhead" would be involved here, beyond a couple of extra bytes in your process image.

And this hasn't changed in either C++14 or C++17 (so far).

Community
  • 1
  • 1
Lightness Races in Orbit
  • 378,754
  • 76
  • 643
  • 1,055
  • Whats wrong with a default constructed `boost::iterator_range` ? – darune Sep 11 '18 at 08:40
  • reference here: https://www.boost.org/doc/libs/1_55_0/libs/range/doc/html/range/reference/utilities/iterator_range.html – darune Sep 11 '18 at 09:10
0

You may use a default constructed boost::iterator_range

from (https://www.boost.org/doc/libs/1_55_0/libs/range/doc/html/range/reference/utilities/iterator_range.html):

However, if one creates a default constructed iterator_range, then one can still call all its member functions. This design decision avoids the iterator_range imposing limitations upon ranges of iterators that are not singular.

Example here: https://wandbox.org/permlink/zslaPwmk3lBI4Q9N

darune
  • 10,480
  • 2
  • 24
  • 62
  • 2
    But, also, _"Any singularity limitation is simply propagated from the underlying iterator type"_, and note the final phrase in your quote, _"iterators that are not singular"_. The way I read it, this means the _range_ doesn't impose any constraints if singular, but if the underlying iterator is singular then you still must abide by those constraints. I don't quite understand it though because it would effectively make the paragraph pointless. Perhaps a default-constructed range just "bypasses" the encapsulated iterator entirely? Might be nice to get some clarification from the mailing list. – Lightness Races in Orbit Sep 11 '18 at 10:37
  • However this is promising! Let us know how it works out – Lightness Races in Orbit Sep 11 '18 at 10:38
  • I'm inclined to agree with @LightnessRacesinOrbit's interpretation of the docs there, so I don't think this is viable, but thanks anyway. – boycy Sep 11 '18 at 11:15
  • It works fine. While the documentation is a bit obfuscated it merely is talking about what happens if you default construct an iterator as compared to a default constructed `boost::range` and the fact that the underlying iterator is just propagated. Example here https://wandbox.org/permlink/zslaPwmk3lBI4Q9N – darune Sep 11 '18 at 11:40