This page is a snapshot from the LWG issues list, see the Library Active Issues List for more information and the meaning of NAD Editorial status.

862. Impossible complexity for 'includes'

Section: 26.8.7.2 [includes] Status: NAD Editorial Submitter: Alisdair Meredith Opened: 2008-07-02 Last modified: 2016-01-28

Priority: Not Prioritized

View all other issues in [includes].

View all issues with NAD Editorial status.

Discussion:

In 26.8.7.2 [includes] the complexity is "at most -1 comparisons" if passed two empty ranges. I don't know how to perform a negative number of comparisions!

This same issue also applies to:

• set_union
• set_intersection
• set_difference
• set_symmetric_difference
• merge

[ 2009-03-30 Beman adds: ]

Suggest NAD. The complexity of empty ranges is -1 in other places in the standard. See 26.8.6 [alg.merge] merge and inplace_merge, and forward_list merge, for example. The time and effort to find and fix all places in the standard where empty range[s] result in negative complexity isn't worth the very limited benefit.

[ 2009-05-09 Alisdair adds: ]

I'm not happy with NAD if we can find a simple solution.

How about adding a rider somewhere in clause 17 suggesting that complexities that specify a negative number of operations are treated as specifying zero operations? That should generically solve the issue without looking for further cases.

[ Batavia (2009-05): ]

Pete to provide "straightforward" wording. Move to NAD Editorial.

Proposed resolution:

Recommend NAD.