35 bool operator()(
const T&
a,
const T&
b)
const {
40 template <
class Container>
41 void check_invariant(Container&
c) {
49 for (; it !=
end; ++it, ++prev) {
54 struct OneAtATimePolicy {
55 template <
class Container>
56 void increase_capacity(Container& c) {
57 if (c.size() == c.capacity()) {
58 c.reserve(c.size() + 1);
63 struct CountCopyCtor {
64 explicit CountCopyCtor() : val_(0) {}
66 explicit CountCopyCtor(
int val) : val_(val), count_(0) {}
68 CountCopyCtor(
const CountCopyCtor& c) : val_(c.val_), count_(c.count_ + 1) {}
70 bool operator<(
const CountCopyCtor& o)
const {
81 return a.value == b.value;
84 return a.value < b.value;
86 struct Compare : std::less<int>, std::less<Opaque> {
87 using is_transparent = void;
88 using std::less<int>::operator();
89 using std::less<Opaque>::operator();
90 bool operator()(
int a, Opaque
b)
const {
91 return std::less<int>::operator()(a, b.value);
93 bool operator()(Opaque
a,
int b)
const {
94 return std::less<int>::operator()(a.value, b);
101 TEST(SortedVectorTypes, SetAssignmentInitListTest) {
110 TEST(SortedVectorTypes, MapAssignmentInitListTest) {
111 using v = std::pair<int, const char*>;
112 v p = {3,
"a"}, q = {4,
"b"}, r = {5,
"c"};
121 TEST(SortedVectorTypes, SimpleSetTest) {
124 for (
int i = 0;
i < 1000; ++
i) {
125 s.
insert(rand() % 100000);
141 auto oldSz = s2.
size();
172 check_invariant(cpy);
178 check_invariant(cpy2);
181 check_invariant(cpy2);
188 TEST(SortedVectorTypes, TransparentSetTest) {
189 using namespace folly::string_piece_literals;
192 constexpr
auto buddy =
"buddy"_sp;
193 constexpr
auto hello =
"hello"_sp;
194 constexpr
auto stake =
"stake"_sp;
195 constexpr
auto world =
"world"_sp;
196 constexpr
auto zebra =
"zebra"_sp;
229 for (
auto value : {buddy, hello, stake, world, zebra}) {
231 std::make_pair(
s.lower_bound(
value),
s.upper_bound(
value)) ==
237 TEST(SortedVectorTypes, BadHints) {
238 for (
int toInsert = -1; toInsert <= 7; ++toInsert) {
239 for (
int hintPos = 0; hintPos <= 4; ++hintPos) {
241 for (
int i = 0;
i <= 3; ++
i) {
245 size_t expectedSize = (toInsert % 2) == 0 ? 4 : 5;
252 TEST(SortedVectorTypes, SimpleMapTest) {
254 for (
int i = 0;
i < 1000; ++
i) {
272 auto it = m2.lower_bound(1 << 20);
274 m2.insert(it, std::make_pair(1 << 20, 10.0
f));
292 m3.
insert(m2.begin(), m2.end());
313 TEST(SortedVectorTypes, TransparentMapTest) {
314 using namespace folly::string_piece_literals;
317 constexpr
auto buddy =
"buddy"_sp;
318 constexpr
auto hello =
"hello"_sp;
319 constexpr
auto stake =
"stake"_sp;
320 constexpr
auto world =
"world"_sp;
321 constexpr
auto zebra =
"zebra"_sp;
324 {{hello.str(), -1.}, {world.str(), +1.}});
355 for (
auto value : {buddy, hello, stake, world, zebra}) {
357 std::make_pair(
m.lower_bound(
value),
m.upper_bound(
value)) ==
363 TEST(SortedVectorTypes, Sizes) {
367 sizeof(std::vector<std::pair<int, int>>));
379 std::allocator<std::pair<int, int>>,
383 EXPECT_EQ(
sizeof(SetT),
sizeof(std::vector<int>));
384 EXPECT_EQ(
sizeof(MapT),
sizeof(std::vector<std::pair<int, int>>));
387 TEST(SortedVectorTypes, InitializerLists) {
392 EXPECT_EQ(1, singleton_initialized_set.size());
393 EXPECT_EQ(1, *singleton_initialized_set.begin());
397 EXPECT_EQ(2, forward_initialized_set.size());
398 EXPECT_EQ(1, *forward_initialized_set.begin());
399 EXPECT_EQ(2, *forward_initialized_set.rbegin());
400 EXPECT_TRUE(forward_initialized_set == backward_initialized_set);
406 EXPECT_EQ(1, singleton_initialized_map.size());
407 EXPECT_EQ(10, singleton_initialized_map[1]);
411 EXPECT_EQ(2, forward_initialized_map.size());
412 EXPECT_EQ(10, forward_initialized_map[1]);
413 EXPECT_EQ(20, forward_initialized_map[2]);
414 EXPECT_TRUE(forward_initialized_map == backward_initialized_map);
417 TEST(SortedVectorTypes, CustomCompare) {
419 for (
int i = 0;
i < 200; ++
i) {
425 for (
int i = 0;
i < 200; ++
i) {
431 TEST(SortedVectorTypes, GrowthPolicy) {
434 std::less<CountCopyCtor>,
435 std::allocator<CountCopyCtor>,
440 for (
int i = 0;
i < 20; ++
i) {
441 a.insert(CountCopyCtor(
i));
444 SetT::iterator it = a.begin();
453 std::list<CountCopyCtor>
v;
454 for (
int i = 0;
i < 20; ++
i) {
455 v.emplace_back(20 +
i);
457 a.insert(v.begin(), v.end());
469 TEST(SortedVectorTest, EmptyTest) {
475 EXPECT_TRUE(emptyMap.lower_bound(10) == emptyMap.end());
480 TEST(SortedVectorTest, MoveTest) {
482 s.
insert(std::make_unique<int>(5));
483 s.
insert(s.
end(), std::make_unique<int>(10));
486 for (
const auto& p : s) {
491 m.
insert(std::make_pair(5, std::make_unique<int>(5)));
492 m.
insert(m.
end(), std::make_pair(10, std::make_unique<int>(10)));
498 TEST(SortedVectorTest, ShrinkTest) {
512 TEST(SortedVectorTypes, EraseTest) {
520 TEST(SortedVectorTypes, EraseTest2) {
522 for (
int i = 0;
i < 1000; ++
i) {
531 it = s.
erase(it, it + 5);
535 while (it != s.
end()) {
546 for (
int i = 0;
i < 1000; ++
i) {
547 m.insert(std::make_pair(
i,
i));
550 auto it2 = m.lower_bound(32);
555 it2 = m.erase(it2, it2 + 5);
559 while (it2 != m.end()) {
560 if (it2->first >= 5) {
571 std::vector<int> ret;
575 std::back_inserter(ret),
576 [](
const CountCopyCtor&
c) {
return c.val_; });
580 template <
typename T,
typename S>
583 ts.reserve(ss.size());
584 for (
auto const&
s : ss) {
590 TEST(SortedVectorTypes, TestSetBulkInsertionSortMerge) {
591 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
594 check_invariant(vset);
597 s = makeVectorOfWrappers<CountCopyCtor, int>({10, 7, 5, 1});
599 vset.insert(
s.begin(),
s.end());
600 check_invariant(vset);
608 TEST(SortedVectorTypes, TestSetBulkInsertionMiddleValuesEqualDuplication) {
609 auto s = makeVectorOfWrappers<CountCopyCtor, int>({4, 6, 8});
612 check_invariant(vset);
614 s = makeVectorOfWrappers<CountCopyCtor, int>({8, 10, 12});
616 vset.insert(
s.begin(),
s.end());
617 check_invariant(vset);
624 TEST(SortedVectorTypes, TestSetBulkInsertionSortMergeDups) {
625 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
628 check_invariant(vset);
631 s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2});
633 vset.insert(
s.begin(),
s.end());
634 check_invariant(vset);
640 TEST(SortedVectorTypes, TestSetInsertionDupsOneByOne) {
641 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
644 check_invariant(vset);
647 s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2});
649 for (
const auto& elem :
s) {
652 check_invariant(vset);
658 TEST(SortedVectorTypes, TestSetBulkInsertionSortNoMerge) {
659 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
662 check_invariant(vset);
665 s = makeVectorOfWrappers<CountCopyCtor, int>({20, 15, 16, 13});
667 vset.insert(
s.begin(),
s.end());
668 check_invariant(vset);
675 TEST(SortedVectorTypes, TestSetBulkInsertionNoSortMerge) {
676 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
679 check_invariant(vset);
682 s = makeVectorOfWrappers<CountCopyCtor, int>({1, 3, 5, 9});
684 vset.insert(
s.begin(),
s.end());
685 check_invariant(vset);
691 TEST(SortedVectorTypes, TestSetBulkInsertionNoSortNoMerge) {
692 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
695 check_invariant(vset);
698 s = makeVectorOfWrappers<CountCopyCtor, int>({21, 22, 23, 24});
700 vset.insert(
s.begin(),
s.end());
701 check_invariant(vset);
708 TEST(SortedVectorTypes, TestSetBulkInsertionEmptyRange) {
709 std::vector<CountCopyCtor>
s;
714 check_invariant(vset);
716 s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
718 vset.insert(s.begin(), s.end());
722 vset.insert(s.begin(), s.end());
723 check_invariant(vset);
730 TEST(SortedVectorTypes, TestBulkInsertionUncopyableTypes) {
731 std::vector<std::pair<int, std::unique_ptr<int>>>
s;
732 s.emplace_back(1, std::make_unique<int>(0));
735 std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
738 s.emplace_back(3, std::make_unique<int>(0));
740 std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
752 ADD_FAILURE() <<
"Copy assignment should not be called";
760 TEST(SortedVectorTypes, TestBulkInsertionMovableTypes) {
761 std::vector<std::pair<int, Movable>>
s;
766 std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
772 std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
775 TEST(SortedVectorTypes, TestSetCreationFromVector) {
776 std::vector<int>
vec = {3, 1, -1, 5, 0};
778 check_invariant(vset);
782 TEST(SortedVectorTypes, TestMapCreationFromVector) {
783 std::vector<std::pair<int, int>>
vec = {
784 {3, 1}, {1, 5}, {-1, 2}, {5, 3}, {0, 3}};
786 check_invariant(vmap);
787 auto contents = std::vector<std::pair<int, int>>(vmap.
begin(), vmap.
end());
788 auto expected_contents = std::vector<std::pair<int, int>>({
798 TEST(SortedVectorTypes, TestBulkInsertionWithDuplicatesIntoEmptySet) {
801 std::vector<int>
const vec = {0, 1, 0, 1};
802 set.insert(vec.begin(), vec.end());
807 TEST(SortedVectorTypes, TestDataPointsToFirstElement) {
bool operator==(const char *c, CStringRange::Sentinel)
size_type erase(const key_type &key)
#define EXPECT_THROW(statement, expected_exception)
std::pair< iterator, iterator > equal_range(const key_type &key)
iterator lower_bound(const key_type &key)
std::pair< iterator, iterator > equal_range(const key_type &key)
mapped_type & at(const key_type &key)
size_type count(const key_type &key) const
size_type erase(const key_type &key)
#define EXPECT_EQ(val1, val2)
constexpr detail::Map< Move > move
auto begin(TestAdlIterable &instance)
std::pair< iterator, bool > insert(const value_type &value)
PUSHMI_INLINE_VAR constexpr detail::transform_fn transform
Movable & operator=(const Movable &)
iterator find(const key_type &key)
Gen range(Value begin, Value end)
iterator lower_bound(const key_type &key)
internal::ElementsAreArrayMatcher< typename::std::iterator_traits< Iter >::value_type > ElementsAreArray(Iter first, Iter last)
auto end(TestAdlIterable &instance)
std::pair< iterator, bool > insert(const value_type &value)
static map< string, int > m
std::vector< T > makeVectorOfWrappers(std::vector< S > ss)
static const char *const value
size_type capacity() const
#define EXPECT_TRUE(condition)
#define EXPECT_THAT(value, matcher)
#define EXPECT_DOUBLE_EQ(val1, val2)
iterator upper_bound(const key_type &key)
size_type count(const key_type &key) const
iterator upper_bound(const key_type &key)
#define EXPECT_NE(val1, val2)
void swap(sorted_vector_map &o)
#define EXPECT_FALSE(condition)
iterator find(const key_type &key)
static constexpr uint64_t data[1]
const value_type * data() const noexcept
std::vector< int > extractValues(sorted_vector_set< CountCopyCtor > const &in)
void swap(sorted_vector_set &o)
std::enable_if< IsLessThanComparable< Value >::value, bool >::type operator<(const Expected< Value, Error > &lhs, const Expected< Value, Error > &rhs)
TEST(SortedVectorTypes, SetAssignmentInitListTest)