Для простого случая gcc выдаёт практически идентичный код.
#include <boost/range/irange.hpp>
void do_the_thing(int);
void oldschool(int a, int b)
{
for (auto i = a; i < b; ++i)
do_the_thing(i);
}
void ranges(int a, int b)
{
for (auto i : boost::irange(a, b))
do_the_thing(i);
}
Перечитал статью внимательнее. Судя по симптомам и лечению, действительно (был) единственный.
ISO IEC 14882-2003 §12.8 Copying class objects [class.copy]
A member function template is never instantiated to perform the copy of a class object to an object of its class type.
Сноска:
106) Because a template constructor is never a copy constructor, the presence of such a template does not suppress the implicit declaration of a copy constructor. Template constructors participate in overload resolution with other constructors, including copy constructors, and a template constructor may be used to copy an object if it provides a better match than other constructors.
ISO IEC 14882-2011 §12.8 Copying class objects [class.copy]
A member function template is never instantiated to produce such a constructor signature.
Т.е. шаблонный конструктор не считается за конструктор копирования как бы вы его не шаблонили, поэтому компилятор сделал свой и использует его когда он лучше подходит, чем шаблонный.
Т.е. нужно явно определять конструктор копирования, что вы в итоге и сделали, но это не «some magic cases», а так и задумано.
However, it is ultimately the decision of the library developer which versions of C++ to support and how.
New libraries will not be rejected because they lack support for older platforms, particularly if new language or library features are integral to the library interface or design. An example would be a library that cannot provide a usable interface without use of a new C++ feature.
Давайте попробуем искать не первый/последний из эквивалентных элементов, а границы содержащего их интервала.
Интервал будет полуоткрытый справа, т.е. [lower_bound, upper_bound) как и все используемые интервалы. В случае, если искомого элемента нет, интервал будет пустой и обе границы (у пустого интервала границы равны) будут указывать на «место для вставки».
Для определения как отсортирована последовательность используем компаратор.
Будем считать, что компаратор comp в нашей последовательности выполняет роль оператора < и элементы в ней отсортированы по возрастанию (возрастанию относительно компаратора).
Т.е. если у нас последовательность целых чисел отсортирована по убыванию, то компаратором в ней будет оператор >. Если у нас последовательность пар чисел, отсортированных по величине второго числа… ну вы поняли о чем я.
lower_bound — позиция первого элемента, который не меньше искомого.
upper_bound — позиция первого элемента, который больше искомого.
Я буду использовать не индексы, а итераторы т.к. считаю, что в данной постановке задачи они уместнее (а ещё потому, что я это буду делать на C++ «в стиле STL»).
Попробуем найти lower_bound:
template<typename FwdIter, typename T, typename Comp>
FwdIter lower_bound(FwdIter first, FwdIter last, T const& x, Comp comp)
{
// если интервал пустой, то его и возвращаем
if (first == last)
return first;
// вычислим позицию среднего элемента
FwdIter middle = first;
std::advance(middle, std::distance(first, last) / 2);
// Если средний элемент меньше искомого, т.е. искомый больше среднего элемента,
// то т.к. последовательность отсортирована по возрастанию,
// искомый элемент должен находиться справа от среднего, иначе — слева
if (comp(*middle, x))
return lower_bound(++middle, last, x, comp);
else
return lower_bound(first, middle, x, comp);
}
upper_bound можно выразить через lower_bound:
У нас есть оператор <, а нам нужен ≤.
Выразим одно через другое:
a ≤ b ⇔ !(b < a)
template<typename FwdIter, typename T, typename Comp>
FwdIter upper_bound(FwdIter first, FwdIter last, T const& x, Comp comp)
{
typedef typename std::iterator_traits<FwdIter>::value_type value_type;
auto less_equal = [&comp](value_type const& a, T const& b){return !comp(b, a);};
return lower_bound(first,last, x, less_equal);
}
Варианты для компаратора по умолчанию пишутся тривиально.
Ну и осталась обертка для проверки входит ли элемент в последовательность и на какой позиции.
template<typename FwdIter, typename T, typename Comp>
FwdIter binary_search(FwdIter first, FwdIter last, T const& x, Comp comp)
{
FwdIter found = lower_bound(first, last, x, comp);
// Если элемент не найден, found может оказаться равен правой границе.
// Если found указывает на существующий элемент, то он не меньше искомого.
// Т.е. *found или больше или равен x, если больше, то x не нашелся.
if (found == last || comp(x, *found))
{
// Элемент не найден.
// Вернем верхнюю границу диапазона в качестве индикатора.
return last;
}
return found;
}
Последняя обертка, не даёт информацию о месте вставки, если элемент не нашелся, однако никто не запрещает воспользоваться lower_bound напрямую, если мы собираемся вставлять элемент.
Тогда уж лучше increaseSpeed(double speed_meters_per_sec), ато ещё спросят как вы в миллисекундах скорость измеряете.
А вообще идея статьи взята из выступления Страуструпа на GoingNative2012 (но примеры и реализация как-то неудачно обрезаны), лучше посмотреть, если ещё не.
Он(майнкрафт) как чистый лист бумаги: если тебе есть что сказать — ты пишешь, если же нет, то сам по себе этот лист бумаги тебя не развеселит, в этом наверное и заключается главный минус данной игры.
Проблема парсинга C++ не столько в том, что его парсить долго, сколько в том, что его парсить много:
Там, где другие распарсили бы 2 строчки, компилятор C++ парсит почти 0.6 Мб.
Насчет сложных случаев не уверен, можно ли сочинить такой, что gcc решит это всё не инлайнить.
ISO IEC 14882-2003 §12.8 Copying class objects [class.copy]
Сноска:
ISO IEC 14882-2011 §12.8 Copying class objects [class.copy]
Т.е. шаблонный конструктор не считается за конструктор копирования как бы вы его не шаблонили, поэтому компилятор сделал свой и использует его когда он лучше подходит, чем шаблонный.
Т.е. нужно явно определять конструктор копирования, что вы в итоге и сделали, но это не «some magic cases», а так и задумано.
А copy-elision тут ни в чём не виновен.
Это единственный конструктор, предназначеный для копирования DReference?
svn.boost.org/trac/boost/wiki/BoostEvo
GCC 4.6.3
GCC 4.7.2
www.coursera.org/course/algo2
www.coursera.org/course/algs4partI
www.coursera.org/course/algs4partII
see.stanford.edu/see/lecturelist.aspx?coll=2d712634-2bf1-4b55-9a3a-ca9d470755ee
www.coursera.org/course/hardware
?
Также можно взглянуть на Boost.TypeErasure, который недавно приняли в состав.
Ещё на эту тему есть тут: http://www.youtube.com/watch?v=_BpMYeUFXv8.
%home%вместо$HOMEили~вас не смущает?Интервал будет полуоткрытый справа, т.е. [lower_bound, upper_bound) как и все используемые интервалы. В случае, если искомого элемента нет, интервал будет пустой и обе границы (у пустого интервала границы равны) будут указывать на «место для вставки».
Для определения как отсортирована последовательность используем компаратор.
Будем считать, что компаратор comp в нашей последовательности выполняет роль оператора < и элементы в ней отсортированы по возрастанию (возрастанию относительно компаратора).
Т.е. если у нас последовательность целых чисел отсортирована по убыванию, то компаратором в ней будет оператор >. Если у нас последовательность пар чисел, отсортированных по величине второго числа… ну вы поняли о чем я.
lower_bound — позиция первого элемента, который не меньше искомого.
upper_bound — позиция первого элемента, который больше искомого.
Я буду использовать не индексы, а итераторы т.к. считаю, что в данной постановке задачи они уместнее (а ещё потому, что я это буду делать на C++ «в стиле STL»).
Попробуем найти lower_bound:
upper_bound можно выразить через lower_bound:
У нас есть оператор <, а нам нужен ≤.
Выразим одно через другое:
a ≤ b ⇔ !(b < a)
Варианты для компаратора по умолчанию пишутся тривиально.
Ну и осталась обертка для проверки входит ли элемент в последовательность и на какой позиции.
Последняя обертка, не даёт информацию о месте вставки, если элемент не нашелся, однако никто не запрещает воспользоваться lower_bound напрямую, если мы собираемся вставлять элемент.
За исключеним нескольких нюансов, мы практически переизобрели соответствующие алгоритмы из STL:
lower_bound
upper_bound
binary_search
equal_range
Тщательно не тестировал, но вроде работает.
Linux 32bit, gcc 4.6.3, Qt 4.8.1
А вообще идея статьи взята из выступления Страуструпа на GoingNative2012 (но примеры и реализация как-то неудачно обрезаны), лучше посмотреть, если ещё не.