Modify

#12117 closed Feature Requests (fixed)

flat_set constructor with ordered_unique_range

Reported by: dariomt@… Owned by: Ion Gaztañaga
Milestone: To Be Determined Component: container
Version: Boost 1.61.0 Severity: Not Applicable
Keywords: Cc: igaztanaga@…

Description

I would expect that the constructors taking a ordered_unique_range_t would assert that the passed range indeed is sorted and unique according to the sorting criteria of the flat_set.

e.g. I'd expect the following code to assert, but instead it prints 0

#include <boost/container/flat_set.hpp>
#include <iostream>

using namespace std;
using namespace boost::container;

int main()
{
    auto l = {3, 2, 1};    
    flat_set<int> s (ordered_unique_range, l);
    cout << s.count(1) << endl;
}

I think the constructor should use std::is_sorted (or the Boost equivalent) to assert that the passed range indeed meets the specified ordered_unique_range.

std::is_sorted has complexity Linear in N, so with this change these constructors would keep their current complexity (which is also Linear in N) even when NDEBUG is not #defined.

Attachments (0)

Change History (1)

comment:1 Changed 14 months ago by Ion Gaztañaga

Resolution: fixed
Status: newclosed

Thanks for the proposal. The check was easy to implement in constructors. In insert() it's really tricky as the input iterator's value_type needs to only be EmplaceConstructible? and values are inserted quite differently, so insert() functions are left intact. Checks for constructors added in commit:

https://github.com/boostorg/container/commit/fb1be6fa75c965c24a03a658c4990137e547d492

Modify Ticket

Change Properties
Set your email in Preferences
Action
as closed The owner will remain Ion Gaztañaga.
The resolution will be deleted.

Add Comment


E-mail address and name can be saved in the Preferences.

 
Note: See TracTickets for help on using tickets.