Здравствуйте, Sinix, Вы писали:
EP>>В STL используются "left-closed, right open" диапазоны. То есть два итератора (индекса) first, second задают диапазон [tt][first, second
S>Дак выяснили, обсудили и закрыли тему уже
S>У нас проблема в следующем: проект не на плюсах, целевая аудитория привыкла, что API проектируется так, чтобы его было удобно использовать без чтения документации.
Читать придётся при любом интерфейсе бинарного поиска. Использовать его не приходя в сознание не получится.
Вот например List<T>.BinarySearch:
https://msdn.microsoft.com/ru-ru/library/w4e7fxsh(v=vs.110).aspx
The zero-based index of item in the sorted List<T>, if item is found; otherwise, a negative number that is the bitwise complement of the index of the next element that is larger than item or, if there is no larger element, the bitwise complement of Count.
...
If the List<T> contains more than one element with the same value, the method returns only one of the occurrences, and it might return any one of the occurrences, not necessarily the first one.
Это как-нибудь можно было вывести без чтения документации?
S>С этой точки зрения lower и upper bounds у нас вышли фейлом, но все прочие варианты, судя по обсуждению, заметно хуже.
Безотносительно языков, partition_point, lower_bound и upper_bound имеют лучший интерфейс и чёткую семантику бинарного поиска.
Без всякой мути а-ля "it might return any one of the occurrences, not necessarily the first one", подобное кстати есть и в C'ишном bsearch — то есть на них даже пример с поиском бажной ревизии нормально не реализуем.
S>И в итоге выбор у нас получается такой: или вот такой вот компромисс, или вообще убирать методы. Т.е. вот такой вот компромисс
Убрать полезные методы только потому что есть те кто не читает документацию?
Здравствуйте, Sinix, Вы писали:
А я правильно понимаю, что самого обычного бинарного поиска а-ля:
var items = LoadItems().OrderBy(item => item.ID).ToList();
...
TItem item10;
if (items.TryBinarySearchItem(item => item.ID, 10, out item10)
{
}
нема? Имхо намного полезнее всяких LowerBound и ежи с ними.
Здравствуйте, Jack128, Вы писали:
J>А я правильно понимаю, что самого обычного бинарного поиска а-ля:
Нету. Заводи реквест — будет
Здравствуйте, Jack128, Вы писали:
А нужен? Он тривиально реализуется через LowerBound:
var comparer = (item, id) => item.ID - id;
var index = items.LowerBound(10, comparer);
if (index != items.Count && items[index].ID == 10)
{
// есть значение
}
else
{
// нет значения
}
Я посчитал, что городить еще одну функцию смысла нет, тем более, что мне чистый бинарный поиск нужен крайне редко. Гораздо чаще нужен поиск элемента или позиции вставки в одном флаконе.
J>нема? Имхо намного полезнее всяких LowerBound и ежи с ними.
У меня другое ИМХО.
Но, если хочется, то нет проблем добавить и бинарный поиск в исходном стиле:
public static int BinarySearch<T,TValue>(this IList<T> list, TValue value, Func<T, TValue, int> comparer);
Твой Try... через него потом делается с полпинка:
public static bool TryBinarySearch<T,TValue>(this IList<T> list, Func<T, TValue> projection, TValue value, out T result)
{
var comparer = (item, value) => Comparer<TValue>.Default.Compare(projection(item), value);
var index = list.BinarySearch(value, comparer);
if (index != list.Count)
{
result = list[index];
return true;
}
result = default(T);
return false;
}
И сразу видно минус твоего интерфейса — приходится внутри еще создавать дополнительный компаратор.
Здравствуйте, Jack128, Вы писали:
J>А я правильно понимаю, что самого обычного бинарного поиска а-ля:
J>J>var items = LoadItems().OrderBy(item => item.ID).ToList();
J>...
J>TItem item10;
J>if (items.TryBinarySearchItem(item => item.ID, 10, out item10)
J>{
J>}
J>
J>нема? Имхо намного полезнее всяких LowerBound и ежи с ними.
Для подобных случаев обычно нужна не отдельная функция, а полноценная map у которой внутри отсортированный массив, а-ля
boost::container::flat_map.
Для тех же случаев когда нужна именно функция — достаточно простой обёртки над lower_bound. Я себе сделал возвращающую
boost::optional<T>, использование вот такое:
if(auto x = binary_search(xs, value))
{
// ...
}
