Flat_Set

A tool which mimics the C++23 std::flat_set from the <flat_set> header - a set backed by some contiguous storage (defaults to std::vector<Key>) which allows logarithmic-time lookup of elements with the benefit of cache locality. This may result in faster lookup than using the standard's own std::set. A flat_set contains a set of unique elements, sorted according to the comparison functor used to create it (defaults to std::less<Key>). The header also includes dp::sorted_unique_t - a tag type used to differentiate between constructors and functions which accept an initial set of values to inform the class that the set used is already sorted and unique and that dp::flat_set need not perform a sort and unique operation of its own. Note that if these overloads are used with an initial set of values which are not sorted and unique with respect to the comparison functor, the behaviour of dp::flat_set will be undefined.

There are some notable limitations in C++98 when mimicking the C++23 interface of this class. Most notable are the lack of uses-allocator support and the lack of move semantics. For the former, it means that the uses-allocator constructors are not implemented. Even if the library did implement uses-allocator functionality on its own, I am unable to add this functionality to standard library containers so it would be meaningless to "forward" allocators to them. For the latter, it means that some functions (particularly extract and replace) must perform more copies than their standard counterparts.

Features

sorted_unique sorted_unique_t	A tag type indended to signal that a range is already sorted and uniqued with respect to the comparison function
flat_set	A container adaptor to provide set-like functionality backed by contiguous storage

dp::flat_set members

begin cbegin	Obtains the begin iterator of the set.
end cend	Obtains the end iterator of the set.
rbegin crbegin	Obtains the reverse begin iterator of the set.
rend crend	Obtains the reverse end iterator of the set.
empty	Checks whether the set is empty.
size	Returns the number of elements in the set.
max_size	Returns the maximum possible number of elements the set may hold.
insert	Inserts an element into the set, or a range of elements given by an iterator pair.
extract	Extracts the underlying container from the set, and clears the set's elements.
replace	Replaces the set's underlying container with a different one. If the new container is not sorted and uniqued, the behaviour is undefined.
erase	Erases elements of the set.
swap	Swaps the set with another.
clear	Erases all elements of the set.
find	Returns an iterator to a specific key, or the end iterator if not found.
count	Counts the number of elements which compare equivalent to a specific key. As this is a set, this number will be either 0 or 1.
contains	Returns whether the set contains a particular element.
lower_bound	Returns an iterator to the first element which compares as not less than the provided key.
upper_bound	Returns an iterator to the first element which compares greater than the provided key.
equal_range	Returns an iterator pair representing the range of all elements with a given key.
key_comp value_comp	Returns a copy of the comparison functor used by the set.
operator== operator!= operator< operator<= operator> operator>=	Lexicographically compares elements of the set with another.
dp::swap	Free function swap in the same namespace as flat_set
dp::erase_if	Free function erase_if implementation.

Sample Code

std::vector<my_large_class> full_data = generate_extended_data();

dp::flat_set<my_large_class> fls(full_data); //Will internally sort and unique the data. If it's already sorted we could use the sorted_unique_t overload

while(some_long_condition){
    dp::flat_set<my_large_class>::const_iterator iter = fls.find(some_element); //O(logn) lookup
    if(iter != fls.end()) do_things_with(*iter);
}