Нередко алгоритм std::find используется не для того, чтобы действительно найти некоторый элемент, а только для того, чтобы узнать, есть такой элемент или нет:
if (find(begin, end, value) == end)
То есть подошел бы позволяющий более короткую запись алгоритм found:
if (found(begin, end, value))
Ни в стандартной библиотеке, ни в Boost'е алгоритма found нет.
Вопросы:
В скольки процентах всех случаев, когда вы используете std::find, подошел бы found?
Определяете ли вы алгоритм found сами?
Если вы определяете found, как вы думаете, почему его нет в Boost'е?
PS. Собственно мое мнение таково: определяя алгоритм возвращающий найденный элемент или конец последовательности в случае, если элемент не был найден, нужно определять соответствующий ему алгоритм возвращающий true, если элемент существует, и false в противном случае. Это как, к примеру, перегрузка по std::string const& и char const*, хотя аналогия конечно тут непрямая. Но мнение мое не важно, вопросы вверху.
I>В скольки процентах всех случаев, когда вы используете std::find, подошел бы found? I>Определяете ли вы алгоритм found сами?
нет I>Если вы определяете found, как вы думаете, почему его нет в Boost'е?
см. выше. I>
1. 0, в случаях когда был нужен found, оказывалось разумнее отсортировать последовательность и использовать std::binary_search, либо вообще заменить коллекцию на std::set/std::map/boost::multi_index_array
2. нет
3. нет
Здравствуйте, igna, Вы писали:
I>Нередко алгоритм std::find используется не для того, чтобы действительно найти некоторый элемент, а только для того, чтобы узнать, есть такой элемент или нет:
Ну не знаю насчёт "нередко". Обычно, когда я что-то ищу, я предполагаю это использовать.
I>То есть подошел бы позволяющий более короткую запись алгоритм found: I>
I> if (found(begin, end, value))
I>
I>Ни в стандартной библиотеке, ни в Boost'е алгоритма found нет.
Две секунды написать
template<class It, class Value> bool found (It i, It j, Value v) { return std::find (i,j,v)!=j; }
template<class It, class Pred> bool found_if(It i, It j, Pred p) { return std::find_if(i,j,p)!=j; }
Вообще, ни STL, ни boost не являются законченными библиотеками на все случаи жизни. Они предоставляют неплохой базис.
Если какой-то специальный фокус ты проделываешь больше одного раза — заводишь себе библиотеку my_cpp_utils и складываешь эти фокусы туда для повторного использования.
Здравствуйте, igna, Вы писали:
I>Нередко алгоритм std::find используется не для того, чтобы действительно найти некоторый элемент, а только для того, чтобы узнать, есть такой элемент или нет:
I>
I> if (find(begin, end, value) == end)
I>
I>То есть подошел бы позволяющий более короткую запись алгоритм found:
I>
I> if (found(begin, end, value))
I>
I>Ни в стандартной библиотеке, ни в Boost'е алгоритма found нет.
I>Вопросы:
I>
I>В скольки процентах всех случаев, когда вы используете std::find, подошел бы found?
На вскидку — примерно в 70% случаев.
I>Определяете ли вы алгоритм found сами?
Нет. Необходимосить писать сравнение с end() не приводит к внутреннему протесту, из-за которого бы стоило написать такой алгоритм .
I>Если вы определяете found, как вы думаете, почему его нет в Boost'е?
Не определяю, но думаю из-за боязни вопросов "а почему подобного метода нет в стандартных ассоциативных контейнерах?" I>
XMK>1. 0, в случаях когда был нужен found, оказывалось разумнее отсортировать последовательность и использовать std::binary_search, либо вообще заменить коллекцию на std::set/std::map/boost::multi_index_array
Если элементов очень мало и сравнение дешовое — выгоднее перебрать все элементы, вместо поддержки сортировки
"For every complex problem, there is a solution that is simple, neat,
and wrong."
Здравствуйте, AndrewJD, Вы писали:
AJD>Если элементов очень мало и сравнение дешовое — выгоднее перебрать все элементы, вместо поддержки сортировки
я в курсе, но последний раз когда встретил такой подход, заменил std::vector на std::set и получил в ряде случаев 20ти кратный прирост производительности
Хотя, если брать в расчет не только алгоритм find, но и метод find, то примерно в 50% случаев пишу Collection.find(key) != Collection.end(), о том чтобы сделать свой метод, или вместо find использовать count мыслей не возникало.
I>То есть подошел бы позволяющий более короткую запись алгоритм found:
наверное таки лучше его назвать exists или is_exists если уж так хочется такую функциональность...
I>Вопросы:
I>
I>В скольки процентах всех случаев, когда вы используете std::find, подошел бы found?
примерно в 0%
I>Определяете ли вы алгоритм found сами?
конечно же нет
I>Если вы определяете found, как вы думаете, почему его нет в Boost'е? I>
I>PS. Собственно мое мнение таково: определяя алгоритм возвращающий найденный элемент или конец последовательности в случае, если элемент не был найден, нужно определять соответствующий ему алгоритм возвращающий true, если элемент существует, и false в противном случае. Это как, к примеру, перегрузка по std::string const& и char const*, хотя аналогия конечно тут непрямая. Но мнение мое не важно, вопросы вверху.
как правило если речь идет о контейнерах с большим числом элементов то я использую либо ассоциативные контейнеры из std либо boost::multi_index_container и соответственно использую метод соответствующего класса. искать чего либо в контейнере с малым числом элементов мне не както обычно не нужно... как правило они временное хранилище (очереди) или буфера для чегото большего...
Иногда begin и end вычисляются непосредственно перед вызовом алгоритма поиска, что может привести к избыточному вычислению end:
if (find(container.begin(), container.end(), value) == container.end())
Чтобы этого не происходило можно вычислить container.end() и сохранить его в переменной, но тогда разница по сравнению с использованием found усиливается в пользу последнего:
if (found(container.begin(), container.end(), value))
Собственно это один из аргументов, которые приводит Мейерс в Effective STL в пользу использования алгоритмов по сравнению с циклами (Item 43. Prefer algorithm calls to hand-written loops).
Здравствуйте, igna, Вы писали:
I>Нередко алгоритм std::find используется не для того, чтобы действительно найти некоторый элемент, а только для того, чтобы узнать, есть такой элемент или нет:
Здравствуйте, teufelsjunge, Вы писали:
T>Для поиска элемента есть std::lower_bound.
Во-первых этот алгоритм применим только для отсортированной последовательности, во-вторых как раз для отсортированных последовательностей аналог алгоритма found есть и называется std::binary_search. То есть непонятно, ты о чем?
Здравствуйте, igna, Вы писали:
I>Здравствуйте, teufelsjunge, Вы писали:
T>>Для поиска элемента есть std::lower_bound.
I>Во-первых этот алгоритм применим только для отсортированной последовательности, во-вторых как раз для отсортированных последовательностей аналог алгоритма found есть и называется std::binary_search. То есть непонятно, ты о чем?
Я немного невнимательно прочитал вопрос, сорри.
Ну, в не отсортированных последовательностях искать кроме как перебором всех элементов нет смысла. Так что, требование отсортированности вполне логично. А по поводу found, которую ты хочешь, она есть и назвается binary_search.
Из документации
binary_search --- Test if value exists in sorted array (function template)
lower_bound --- Return iterator to lower bound
Т.е. binary_search — как раз твой found, который ты хотел писать.
Перекуём баги на фичи!
.
