Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Can I create an empty range (iterator pair) without an underlying container object?

Tags:

c++

c++11

boost

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

like image 840
boycy Avatar asked Mar 31 '15 09:03

boycy


1 Answers

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.

  • Is this a singular iterator and, if so, can I compare it to another one?
  • Comparing default-constructed iterators with operator==

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

like image 149
Lightness Races in Orbit Avatar answered Oct 29 '22 01:10

Lightness Races in Orbit