folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container > Class Template Reference

#include <sorted_vector_types.h>

Inheritance diagram for folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >:

Classes
struct	EBO
struct	value_compare

Public Types
typedef Key	key_type
typedef Value	mapped_type
typedef Container::value_type	value_type
typedef Compare	key_compare
typedef Container::pointer	pointer
typedef Container::reference	reference
typedef Container::const_reference	const_reference
typedef Container::iterator	iterator
typedef Container::const_iterator	const_iterator
typedef Container::difference_type	difference_type
typedef Container::size_type	size_type
typedef Container::reverse_iterator	reverse_iterator
typedef Container::const_reverse_iterator	const_reverse_iterator

Public Member Functions
	sorted_vector_map (const Compare &comp=Compare(), const Allocator &alloc=Allocator())
template<class InputIterator >
	sorted_vector_map (InputIterator first, InputIterator last, const Compare &comp=Compare(), const Allocator &alloc=Allocator())
	sorted_vector_map (std::initializer_list< value_type > list, const Compare &comp=Compare(), const Allocator &alloc=Allocator())
	sorted_vector_map (Container &&container, const Compare &comp=Compare())
	sorted_vector_map (presorted_t, Container &&container, const Compare &comp=Compare())
sorted_vector_map &	operator= (std::initializer_list< value_type > ilist)
key_compare	key_comp () const
value_compare	value_comp () const
iterator	begin ()
iterator	end ()
const_iterator	cbegin () const
const_iterator	begin () const
const_iterator	cend () const
const_iterator	end () const
reverse_iterator	rbegin ()
reverse_iterator	rend ()
const_reverse_iterator	rbegin () const
const_reverse_iterator	rend () const
void	clear ()
size_type	size () const
size_type	max_size () const
bool	empty () const
void	reserve (size_type s)
void	shrink_to_fit ()
size_type	capacity () const
std::pair< iterator, bool >	insert (const value_type &value)
std::pair< iterator, bool >	insert (value_type &&value)
iterator	insert (iterator hint, const value_type &value)
iterator	insert (iterator hint, value_type &&value)
template<class InputIterator >
void	insert (InputIterator first, InputIterator last)
size_type	erase (const key_type &key)
iterator	erase (iterator it)
iterator	erase (iterator first, iterator last)
iterator	find (const key_type &key)
const_iterator	find (const key_type &key) const
template<typename K >
if_is_transparent< K, iterator >	find (const K &key)
template<typename K >
if_is_transparent< K, const_iterator >	find (const K &key) const
mapped_type &	at (const key_type &key)
const mapped_type &	at (const key_type &key) const
size_type	count (const key_type &key) const
template<typename K >
if_is_transparent< K, size_type >	count (const K &key) const
iterator	lower_bound (const key_type &key)
const_iterator	lower_bound (const key_type &key) const
template<typename K >
if_is_transparent< K, iterator >	lower_bound (const K &key)
template<typename K >
if_is_transparent< K, const_iterator >	lower_bound (const K &key) const
iterator	upper_bound (const key_type &key)
const_iterator	upper_bound (const key_type &key) const
template<typename K >
if_is_transparent< K, iterator >	upper_bound (const K &key)
template<typename K >
if_is_transparent< K, const_iterator >	upper_bound (const K &key) const
std::pair< iterator, iterator >	equal_range (const key_type &key)
std::pair< const_iterator, const_iterator >	equal_range (const key_type &key) const
template<typename K >
if_is_transparent< K, std::pair< iterator, iterator > >	equal_range (const K &key)
template<typename K >
if_is_transparent< K, std::pair< const_iterator, const_iterator > >	equal_range (const K &key) const
void	swap (sorted_vector_map &o)
mapped_type &	operator[] (const key_type &key)
bool	operator== (const sorted_vector_map &other) const
bool	operator!= (const sorted_vector_map &other) const
bool	operator< (const sorted_vector_map &other) const
bool	operator> (const sorted_vector_map &other) const
bool	operator<= (const sorted_vector_map &other) const
bool	operator>= (const sorted_vector_map &other) const
const value_type *	data () const noexcept

Private Types
template<typename K , typename V , typename C = Compare>
using	if_is_transparent = _t< detail::sorted_vector_enable_if_is_transparent< void, C, K, V >>
template<typename Self >
using	self_iterator_t = _t< std::conditional< std::is_const< Self >::value, const_iterator, iterator >>

Private Member Functions
detail::growth_policy_wrapper< GrowthPolicy > &	get_growth_policy ()
Private Member Functions inherited from folly::detail::growth_policy_wrapper< GrowthPolicy >
Iterator	increase_capacity (Container &c, Iterator desired_insertion)

Static Private Member Functions
template<typename Self , typename K >
static self_iterator_t< Self >	find (Self &self, K const &key)
template<typename Self , typename K >
static self_iterator_t< Self >	lower_bound (Self &self, K const &key)
template<typename Self , typename K >
static self_iterator_t< Self >	upper_bound (Self &self, K const &key)
template<typename Self , typename K >
static std::pair< self_iterator_t< Self >, self_iterator_t< Self > >	equal_range (Self &self, K const &key)

Private Attributes
folly::sorted_vector_map::EBO	m_

Detailed Description

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>
class folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >

A sorted_vector_map is similar to a sorted_vector_set but stores <key,value> pairs instead of single elements.

Parameters

class	Key Key type
class	Value Value type
class	Compare Function that can compare key types and impose a strict weak ordering over them.
class	Allocator allocation policy
class	GrowthPolicy policy object to control growth

Author

Aditya Agarwal adity.nosp@m.a@fb.nosp@m..com

Akhil Wable akhil.nosp@m.@fb..nosp@m.com

Jordan DeLong delon.nosp@m.g.j@.nosp@m.fb.co.nosp@m.m

Definition at line 609 of file sorted_vector_types.h.

Member Typedef Documentation

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

typedef Container::const_iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::const_iterator

Definition at line 638 of file sorted_vector_types.h.

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

typedef Container::const_reference folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::const_reference

Definition at line 636 of file sorted_vector_types.h.

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

typedef Container::const_reverse_iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::const_reverse_iterator

Definition at line 642 of file sorted_vector_types.h.

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

typedef Container::difference_type folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::difference_type

Definition at line 639 of file sorted_vector_types.h.

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

template<typename K , typename V , typename C = Compare>

using folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::if_is_transparent = _t<detail::sorted_vector_enable_if_is_transparent<void, C, K, V>>

private

Definition at line 616 of file sorted_vector_types.h.

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

typedef Container::iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::iterator

Definition at line 637 of file sorted_vector_types.h.

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

typedef Compare folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::key_compare

Definition at line 622 of file sorted_vector_types.h.

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

typedef Key folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::key_type

Definition at line 619 of file sorted_vector_types.h.

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

typedef Value folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::mapped_type

Definition at line 620 of file sorted_vector_types.h.

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

typedef Container::pointer folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::pointer

Definition at line 634 of file sorted_vector_types.h.

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

typedef Container::reference folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::reference

Definition at line 635 of file sorted_vector_types.h.

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

typedef Container::reverse_iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::reverse_iterator

Definition at line 641 of file sorted_vector_types.h.

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

template<typename Self >

using folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::self_iterator_t = _t< std::conditional<std::is_const<Self>::value, const_iterator, iterator>>

private

Definition at line 963 of file sorted_vector_types.h.

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

typedef Container::size_type folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::size_type

Definition at line 640 of file sorted_vector_types.h.

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

typedef Container::value_type folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::value_type

Definition at line 621 of file sorted_vector_types.h.

Constructor & Destructor Documentation

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::sorted_vector_map ( const Compare &  comp = Compare(), const Allocator &  alloc = Allocator()  )

inlineexplicit

Definition at line 644 of file sorted_vector_types.h.

      : m_(value_compare(comp), alloc) {}

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

template<class InputIterator >

folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::sorted_vector_map ( InputIterator  first, InputIterator  last, const Compare &  comp = Compare(), const Allocator &  alloc = Allocator()  )

inlineexplicit

Definition at line 650 of file sorted_vector_types.h.

      : m_(value_compare(comp), alloc) {
    insert(first, last);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::sorted_vector_map ( std::initializer_list< value_type >  list, const Compare &  comp = Compare(), const Allocator &  alloc = Allocator()  )

inlineexplicit

Definition at line 659 of file sorted_vector_types.h.

      : m_(value_compare(comp), alloc) {
    insert(list.begin(), list.end());
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::sorted_vector_map ( Container &&  container, const Compare &  comp = Compare()  )

inlineexplicit

Definition at line 675 of file sorted_vector_types.h.

      : sorted_vector_map(
            presorted,
            detail::as_sorted(std::move(container), value_compare(comp)),
            comp) {}

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::sorted_vector_map ( presorted_t  , Container &&  container, const Compare &  comp = Compare()  )

inline

Definition at line 692 of file sorted_vector_types.h.

      : m_(value_compare(comp), container.get_allocator()) {
    assert(std::is_sorted(container.begin(), container.end(), value_comp()));
    m_.cont_.swap(container);
  }

Member Function Documentation

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

mapped_type& folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::at ( const key_type &  key )

inline

Definition at line 829 of file sorted_vector_types.h.

References folly::test::end().

Referenced by TEST().

                                       {
    iterator it = find(key);
    if (it != end()) {
      return it->second;
    }
    throw_exception<std::out_of_range>("sorted_vector_map::at");
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

const mapped_type& folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::at ( const key_type &  key ) const

inline

Definition at line 837 of file sorted_vector_types.h.

References folly::test::end().

                                                   {
    const_iterator it = find(key);
    if (it != end()) {
      return it->second;
    }
    throw_exception<std::out_of_range>("sorted_vector_map::at");
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::begin ( )

inline

Definition at line 714 of file sorted_vector_types.h.

Referenced by TEST().

                   {
    return m_.cont_.begin();
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

const_iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::begin ( ) const

inline

Definition at line 723 of file sorted_vector_types.h.

                               {
    return m_.cont_.begin();
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

size_type folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::capacity ( ) const

inline

Definition at line 763 of file sorted_vector_types.h.

                             {
    return m_.cont_.capacity();
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

const_iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::cbegin ( ) const

inline

Definition at line 720 of file sorted_vector_types.h.

                                {
    return m_.cont_.cbegin();
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

const_iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::cend ( ) const

inline

Definition at line 726 of file sorted_vector_types.h.

                              {
    return m_.cont_.cend();
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

void folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::clear ( )

inline

Definition at line 745 of file sorted_vector_types.h.

               {
    return m_.cont_.clear();
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

size_type folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::count ( const key_type &  key ) const

inline

Definition at line 845 of file sorted_vector_types.h.

References folly::test::end().

Referenced by TEST().

                                             {
    return find(key) == end() ? 0 : 1;
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

template<typename K >

if_is_transparent<K, size_type> folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::count ( const K &  key ) const

inline

Definition at line 850 of file sorted_vector_types.h.

References folly::test::end().

                                                            {
    return find(key) == end() ? 0 : 1;
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

const value_type* folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::data ( ) const

inlinenoexcept

Definition at line 948 of file sorted_vector_types.h.

Referenced by TEST().

                                          {
    return m_.cont_.data();
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

bool folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::empty ( ) const

inline

Definition at line 754 of file sorted_vector_types.h.

                     {
    return m_.cont_.empty();
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::end ( )

inline

Definition at line 717 of file sorted_vector_types.h.

Referenced by TEST().

                 {
    return m_.cont_.end();
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

const_iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::end ( ) const

inline

Definition at line 729 of file sorted_vector_types.h.

                             {
    return m_.cont_.end();
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

std::pair<iterator, iterator> folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::equal_range ( const key_type &  key )

inline

Definition at line 890 of file sorted_vector_types.h.

Referenced by TEST().

                                                               {
    return equal_range(*this, key);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

std::pair<const_iterator, const_iterator> folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::equal_range ( const key_type &  key ) const

inline

Definition at line 894 of file sorted_vector_types.h.

                                 {
    return equal_range(*this, key);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

template<typename K >

if_is_transparent<K, std::pair<iterator, iterator> > folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::equal_range ( const K &  key )

inline

Definition at line 900 of file sorted_vector_types.h.

                    {
    return equal_range(*this, key);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

template<typename K >

if_is_transparent<K, std::pair<const_iterator, const_iterator> > folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::equal_range ( const K &  key ) const

inline

Definition at line 906 of file sorted_vector_types.h.

                          {
    return equal_range(*this, key);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

template<typename Self , typename K >

static std::pair<self_iterator_t<Self>, self_iterator_t<Self> > folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::equal_range ( Self &  self, K const &  key  )

inlinestaticprivate

Definition at line 992 of file sorted_vector_types.h.

                    {
    // Note: std::equal_range can't be passed a functor that takes
    // argument types different from the iterator value_type, so we
    // have to do this.
    return {lower_bound(self, key), upper_bound(self, key)};
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

size_type folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::erase ( const key_type &  key )

inline

Definition at line 794 of file sorted_vector_types.h.

References folly::test::end().

Referenced by TEST().

                                       {
    iterator it = find(key);
    if (it == end()) {
      return 0;
    }
    m_.cont_.erase(it);
    return 1;
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::erase ( iterator  it )

inline

Definition at line 803 of file sorted_vector_types.h.

                              {
    return m_.cont_.erase(it);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::erase ( iterator  first, iterator  last  )

inline

Definition at line 807 of file sorted_vector_types.h.

                                                {
    return m_.cont_.erase(first, last);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::find ( const key_type &  key )

inline

Definition at line 811 of file sorted_vector_types.h.

Referenced by TEST().

                                     {
    return find(*this, key);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

const_iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::find ( const key_type &  key ) const

inline

Definition at line 815 of file sorted_vector_types.h.

                                                 {
    return find(*this, key);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

template<typename K >

if_is_transparent<K, iterator> folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::find ( const K &  key )

inline

Definition at line 820 of file sorted_vector_types.h.

                                                    {
    return find(*this, key);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

template<typename K >

if_is_transparent<K, const_iterator> folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::find ( const K &  key ) const

inline

Definition at line 825 of file sorted_vector_types.h.

                                                                {
    return find(*this, key);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

template<typename Self , typename K >

static self_iterator_t<Self> folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::find ( Self &  self, K const &  key  )

inlinestaticprivate

Definition at line 966 of file sorted_vector_types.h.

References folly::test::end().

                                                              {
    auto end = self.end();
    auto it = self.lower_bound(key);
    if (it == end || !self.key_comp()(key, it->first)) {
      return it;
    }
    return end;
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

detail::growth_policy_wrapper<GrowthPolicy>& folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::get_growth_policy ( )

inlineprivate

Definition at line 610 of file sorted_vector_types.h.

                                                                 {
    return *this;
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

std::pair<iterator, bool> folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::insert ( const value_type &  value )

inline

Definition at line 767 of file sorted_vector_types.h.

References folly::gen::move.

Referenced by TEST().

                                                          {
    return insert(std::move(value_type(value)));
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

std::pair<iterator, bool> folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::insert ( value_type &&  value )

inline

Definition at line 771 of file sorted_vector_types.h.

References folly::test::end(), folly::gen::move, and folly::value().

                                                     {
    iterator it = lower_bound(value.first);
    if (it == end() || value_comp()(value, *it)) {
      it = get_growth_policy().increase_capacity(m_.cont_, it);
      return std::make_pair(m_.cont_.insert(it, std::move(value)), true);
    }
    return std::make_pair(it, false);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::insert ( iterator  hint, const value_type &  value  )

inline

Definition at line 780 of file sorted_vector_types.h.

References folly::gen::move.

                                                          {
    return insert(hint, std::move(value_type(value)));
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::insert ( iterator  hint, value_type &&  value  )

inline

Definition at line 784 of file sorted_vector_types.h.

References folly::detail::insert_with_hint(), folly::gen::move, and folly::value().

                                                     {
    return detail::insert_with_hint(
        *this, m_.cont_, hint, std::move(value), get_growth_policy());
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

template<class InputIterator >

void folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::insert ( InputIterator  first, InputIterator  last  )

inline

Definition at line 790 of file sorted_vector_types.h.

References folly::detail::bulk_insert().

                                                       {
    detail::bulk_insert(*this, m_.cont_, first, last);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

key_compare folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::key_comp ( ) const

inline

Definition at line 707 of file sorted_vector_types.h.

                               {
    return m_;
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::lower_bound ( const key_type &  key )

inline

Definition at line 854 of file sorted_vector_types.h.

Referenced by TEST().

                                            {
    return lower_bound(*this, key);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

const_iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::lower_bound ( const key_type &  key ) const

inline

Definition at line 858 of file sorted_vector_types.h.

                                                        {
    return lower_bound(*this, key);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

template<typename K >

if_is_transparent<K, iterator> folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::lower_bound ( const K &  key )

inline

Definition at line 863 of file sorted_vector_types.h.

                                                           {
    return lower_bound(*this, key);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

template<typename K >

if_is_transparent<K, const_iterator> folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::lower_bound ( const K &  key ) const

inline

Definition at line 868 of file sorted_vector_types.h.

                                                                       {
    return lower_bound(*this, key);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

template<typename Self , typename K >

static self_iterator_t<Self> folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::lower_bound ( Self &  self, K const &  key  )

inlinestaticprivate

Definition at line 976 of file sorted_vector_types.h.

References a, b, folly::test::begin(), c, folly::test::end(), and f.

                                                                     {
    auto f = [c = self.key_comp()](value_type const& a, K const& b) {
      return c(a.first, b);
    };
    return std::lower_bound(self.begin(), self.end(), key, f);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

size_type folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::max_size ( ) const

inline

Definition at line 751 of file sorted_vector_types.h.

                             {
    return m_.cont_.max_size();
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

bool folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::operator!= ( const sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container > &  other ) const

inline

Definition at line 931 of file sorted_vector_types.h.

References folly::operator==().

                                                        {
    return !operator==(other);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

bool folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::operator< ( const sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container > &  other ) const

inline

Definition at line 935 of file sorted_vector_types.h.

References folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::EBO::cont_, and folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::m_.

                                                       {
    return m_.cont_ < other.m_.cont_;
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

bool folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::operator<= ( const sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container > &  other ) const

inline

Definition at line 941 of file sorted_vector_types.h.

References folly::operator>().

                                                        {
    return !operator>(other);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

sorted_vector_map& folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::operator= ( std::initializer_list< value_type >  ilist )

inline

Definition at line 701 of file sorted_vector_types.h.

                                                                      {
    clear();
    insert(ilist.begin(), ilist.end());
    return *this;
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

bool folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::operator== ( const sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container > &  other ) const

inline

Definition at line 928 of file sorted_vector_types.h.

References folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::EBO::cont_, and folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::m_.

                                                        {
    return m_.cont_ == other.m_.cont_;
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

bool folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::operator> ( const sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container > &  other ) const

inline

Definition at line 938 of file sorted_vector_types.h.

                                                       {
    return other < *this;
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

bool folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::operator>= ( const sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container > &  other ) const

inline

Definition at line 944 of file sorted_vector_types.h.

References folly::operator<().

                                                        {
    return !operator<(other);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

mapped_type& folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::operator[] ( const key_type &  key )

inline

Definition at line 920 of file sorted_vector_types.h.

References folly::test::end().

                                               {
    iterator it = lower_bound(key);
    if (it == end() || key_comp()(key, it->first)) {
      return insert(it, value_type(key, mapped_type()))->second;
    }
    return it->second;
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

reverse_iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::rbegin ( )

inline

Definition at line 732 of file sorted_vector_types.h.

                            {
    return m_.cont_.rbegin();
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

const_reverse_iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::rbegin ( ) const

inline

Definition at line 738 of file sorted_vector_types.h.

                                        {
    return m_.cont_.rbegin();
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

reverse_iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::rend ( )

inline

Definition at line 735 of file sorted_vector_types.h.

                          {
    return m_.cont_.rend();
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

const_reverse_iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::rend ( ) const

inline

Definition at line 741 of file sorted_vector_types.h.

                                      {
    return m_.cont_.rend();
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

void folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::reserve ( size_type  s )

inline

Definition at line 757 of file sorted_vector_types.h.

                            {
    return m_.cont_.reserve(s);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

void folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::shrink_to_fit ( )

inline

Definition at line 760 of file sorted_vector_types.h.

                       {
    m_.cont_.shrink_to_fit();
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

size_type folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::size ( ) const

inline

Definition at line 748 of file sorted_vector_types.h.

                         {
    return m_.cont_.size();
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

void folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::swap ( sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container > &  o )

inline

Definition at line 912 of file sorted_vector_types.h.

References a, b, folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::EBO::cont_, folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::m_, and folly::swap().

Referenced by folly::swap(), and TEST().

                                  {
    using std::swap; // Allow ADL for swap(); fall back to std::swap().
    Compare& a = m_;
    Compare& b = o.m_;
    swap(a, b);
    m_.cont_.swap(o.m_.cont_);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::upper_bound ( const key_type &  key )

inline

Definition at line 872 of file sorted_vector_types.h.

Referenced by TEST().

                                            {
    return upper_bound(*this, key);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

const_iterator folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::upper_bound ( const key_type &  key ) const

inline

Definition at line 876 of file sorted_vector_types.h.

                                                        {
    return upper_bound(*this, key);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

template<typename K >

if_is_transparent<K, iterator> folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::upper_bound ( const K &  key )

inline

Definition at line 881 of file sorted_vector_types.h.

                                                           {
    return upper_bound(*this, key);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

template<typename K >

if_is_transparent<K, const_iterator> folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::upper_bound ( const K &  key ) const

inline

Definition at line 886 of file sorted_vector_types.h.

                                                                       {
    return upper_bound(*this, key);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

template<typename Self , typename K >

static self_iterator_t<Self> folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::upper_bound ( Self &  self, K const &  key  )

inlinestaticprivate

Definition at line 984 of file sorted_vector_types.h.

References a, b, folly::test::begin(), c, folly::test::end(), and f.

                                                                     {
    auto f = [c = self.key_comp()](K const& a, value_type const& b) {
      return c(a, b.first);
    };
    return std::upper_bound(self.begin(), self.end(), key, f);
  }

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

value_compare folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::value_comp ( ) const

inline

Definition at line 710 of file sorted_vector_types.h.

                                   {
    return m_;
  }

Member Data Documentation

template<class Key, class Value, class Compare = std::less<Key>, class Allocator = std::allocator<std::pair<Key, Value>>, class GrowthPolicy = void, class Container = std::vector<std::pair<Key, Value>, Allocator>>

folly::sorted_vector_map::EBO folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::m_

private

Referenced by folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::operator<(), folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::operator==(), and folly::sorted_vector_map< Key, Value, Compare, Allocator, GrowthPolicy, Container >::swap().

---

The documentation for this class was generated from the following file:

• proxygen/folly/folly/sorted_vector_types.h