folly::merge() - std::merge() with stronger guarantees (probably same implementation...
authorMarc Celani <marccelani@fb.com>
Sun, 16 Mar 2014 03:04:47 +0000 (20:04 -0700)
committerDave Watson <davejwatson@fb.com>
Tue, 18 Mar 2014 17:02:24 +0000 (10:02 -0700)
commitcd3fcbcf5f7bbf06c5cae424b15fdc02e24407f5
treed68109389f9194a2089dc0c53a24b1e31db3b758
parentc3633870bb96623fc188f2fb2564dbf18c58a2e9
folly::merge() - std::merge() with stronger guarantees (probably same implementation in practice)

Summary:
std::merge() does not guarantee the ordering when equal elements belong in two ranges(comparator(it_a, it_b) == comparator(it_b, it_a) == 0). For maps, it is important that we can specify the ordering (see array_merge in php, where we guarantee which array's value will be present in the output if a key is present in both inputs).

Also removes folly::merge that is specfic for sorted_vector_map since this will not be needed. NOTE: I expect this to break feed, will fix in a separate non-folly diff.

Test Plan: This implementation is directly ripped from cppreference.com, but unit tests added none-the-less. Specifically, one is added where the output is a std::map to demonstrate its usefulness.

Reviewed By: delong.j@fb.com

FB internal diff: D1223401

@override-unit-failures
folly/Merge.h [new file with mode: 0644]
folly/sorted_vector_types.h
folly/test/MergeTest.cpp [new file with mode: 0644]
folly/test/SortedVectorBenchmark.cpp [deleted file]
folly/test/sorted_vector_test.cpp