Circular buffer offsets and sorted set of offsets sorted on their index
One way is to supply uint16_t as the third template argument to boost::counting_iterator so that it allows wrapping around, allowing the code to be greatly simplified:

#include &lt;algorithm&gt;
#include &lt;deque&gt;
#include &lt;boost/iterator/counting_iterator.hpp&gt;

// Assumes _count == 65536 (0x10000)
typedef boost::counting_iterator&lt;uint16_t,
                                 boost::use_default,
                                 uint16_t&gt; uint16_wrapping_counting_iterator;


// Insert the inclusive range [beginOffset, lastOffset] into the recentItems
// ordered deque of offsets.  The offsets are into a circular array of 65,536
// items, so the range may wrap around.  The ordering of the offsets is based
// upon the index that corresponds to each offset.  For example, a beginOffset
// of 65,000 and a lastOffset of 100 means to insert the range of offsets
// [65000, 65535] into the deque at insertionPoint followed by the range of
// offsets [0, 100] and the beginOffset of 65,000 may correspond to an index of
// 65,000 but the lastOffset of 100 could correspond to an index of 65636 for
// the first time the circual buffer to which these offsets refer wraps around.

void
insertRecentRange(const int beginOffset,
                  const int lastOffset,
                  std::deque&lt;int&gt;::iterator insertionPoint,
                  std::deque&lt;int&gt; &amp;recentItems)
{
  const uint16_t startOffset = uint16_t(beginOffset);
  const uint16_t endOffset   = uint16_t(lastOffset + 1);

  // The recentItems is an ordered set of offsets that have been noted.
  recentItems.insert(insertionPoint,
                     uint16_wrapping_counting_iterator(startOffset),
                     uint16_wrapping_counting_iterator(endOffset));
}