
![]() |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[216.73.216.67] |
![]() |
|
![]() |
![]() |
|
TR1. Technical Report on C++ Library Extensions
Введение. В мае 2001 комитет по стандартизации языка С++ объявил(n1314) о приёме предложений и пожеланий для расширения функциональности Стандартной Библиотеки С++. Комитет озвучил некоторый список того, чего он желал бы видеть в качестве пожеланий. Также, комитет немного формализовал способ заявления о своём пожелании. Пожелание должно содержать следующие пункты: мотивация(зачем нужно нововведение; описание проблемы), влияние на стандарт(нужны ли для нововведения изменения в текущем стандарте - как в синтаксисе, так и в библиотечной его части), принятые решения(описание предлагаемого решения проблемы) и примерный текст для включения в стандарт(необязательно). Таким образом, каждый желающий мог поучаствовать в усовершенствовании любимого языка, а точнее - его библиотеки. Так, уже в октябре 2001 был составлен начальный список пожеланий(n1325), который включал в себя только пожелания перенести некоторую функциональность из Boost. В дальнейшем список начал пополняться не только библиотеками из Boost. И тем не менее, первый, опубликованный в сентябре 2003, черновик TR1 почти полностью состоял из формализованной документации Boost. TR1 - это Technical Report. Документы этого класса не являются нормативными(в отличии от IS - International Standard) и делаются специально на скорость, опуская много долгих и нудных формальностей. Здесь будет более-менее подробно рассмотрен последний черновик TR1, опубликованный в июле 2005. Все сущности из TR1 находятся в пространстве имён std::tr1. Знать содержимое TR1 нужно. Точно так же, как нужно знать содержимое STL - без этого, эффективно программировать на С++ невозможно. Несмотря на то, что оффициально TR1 имеет лишь рекомендательный характер, в реальности он уже включён в рабочий черновик следующего стандарта(C++09) и начиная с 2009 года(возможно чуть позже), программирование с использованием TR1 будет считаться таким же обыкновенным явлением, как и программирование с использованием STL(он будет частью STL). Т.к. за один день с такой объёмной библиотекой не освоишься(нужно разобраться, попрактиковаться, "набить шишки" и т.д.), то рекомендую людям, проффессионально занимающимся(или планирующим проффесионально заняться) программированием на С++ ознакомится с TR1(если ещё не знакомы) и начать его эксплуатацию(уже есть реализация от Boost). Ну и последний аргумент в пользу TR1: не нужно изобретать велосипедов ![]() Reference wrapper(n1453) ![]() ![]() template <class T> class reference_wrapper; // сама обёртка // ф-ции помощники(аля std::make_pair для std::pair) template <class T> reference_wrapper<T> ref(T&); template <class T> reference_wrapper<const T> cref(const T&); template <class T> reference_wrapper<T> ref(reference_wrapper<T>); template <class T> reference_wrapper<const T> cref(reference_wrapper<T>); Обёртка для работы со ссылками. Представляет из себя объект, хранящий ссылку типа T, неявно конвертируемый к типу T &, с перегруженным оператором operator()(...). Smart Pointers(n1450) ![]() ![]() class bad_weak_ptr; template<class T> class shared_ptr; // shared_ptr comparisons template<class T, class U> bool operator==(shared_ptr<T> const& a, shared_ptr<U> const& b); template<class T, class U> bool operator!=(shared_ptr<T> const& a, shared_ptr<U> const& b); template<class T, class U> bool operator<(shared_ptr<T> const& a, shared_ptr<U> const& b); // shared_ptr casts template<class T, class U> shared_ptr<T> static_pointer_cast(shared_ptr<U> const& r); template<class T, class U> shared_ptr<T> dynamic_pointer_cast(shared_ptr<U> const& r); template<class T, class U> shared_ptr<T> const_pointer_cast(shared_ptr<U> const& r); // shared_ptr I/O template<class E, class T, class Y> basic_ostream<E, T>& operator<< (basic_ostream<E, T>& os, shared_ptr<Y> const& p); // shared_ptr get_deleter template<class D, class T> D* get_deleter(shared_ptr<T> const& p); // ----------------------------------------------------------------------------- template<class T> class weak_ptr; // weak_ptr comparison template<class T, class U> bool operator<(weak_ptr<T> const& a, weak_ptr<U> const& b); Умные указатели - это специальные обёртки для обычных указателей(plain pointer, dumb pointer), которые так или иначе позволяют обезопасить себя от неприятнотей, которые встречаются при работе с обычными указателями. Но, тем не менее, они сами, как правило, имеют свои грабли и неприятные стороны ![]() Основное предназначение умных указателей - это автоматический контроль времени жизни динамических объектов, но бывают и другие предназначения. Умные указатели бывают разными. В STL ещё с 98 года есть std::auto_ptr. Его проблема в том, что объекты auto_ptr владеют объектом и при копировании(присваивании) у источника копирования(присваивания) хранимый указатель обнуляется. Т.е. на некоторый данный объект принципиально не может ссылаться более одного объекта auto_ptr. Реально, добиться того, чтобы на данный объект указывало несколько auto_ptr можно, но это UB(каждый из них выполнит delete ptr, чего делать несколько раз для одного и того же указателя нельзя). Предлагаемый умный указатель shared_ptr имеет такое название не случайно ![]() Также предлагается т.н. observer(наблюдатель) weak_ptr. Имея shared_ptr можно создать weak_ptr, из которого потом можно будет опять создать shared_ptr но только при том условии, что объект ещё "жив". Т.е weak_ptr не владеет объектом, он только "наблюдает" и если все shared_ptr уже "умерли", то weak_ptr обнулится и при попытке создать из него shared_ptr бросится исключение bad_weak_ptr. Предполагаемое применение. Если вы раньше не использовали умных указателей, то перед "употреблением" советую почитать Мейрса, Александреску, Саттера и других на эту тему т.к. не зная best practices использовать умные укзатели немного проблематично(можно нагородить такого, что лучше бы их и не использовали ![]() Если у старого доброго auto_ptr все области его применения очень хорошо известны и их очень мало, то у shared_ptr возможно применение почти везде, где возможно применение указателя. Характерное применение shared_ptr - везде, где динамическим объектом владеют несколько объектов/потоков/ф-ций и т.п. ![]() ![]() struct Interface { virtual void doSmallAction1() = 0; virtual void doSmallAction2() = 0; virtual void doSmallAction3() = 0; // ... virtual ~Interface() { } }; class Factory; class StaticInterface { friend class Factory; shared_ptr< Interface > impl; public: void doAction1() { impl->doSmallAction1(); impl->doSmallAction3(); } void doAction2() { impl->doSmallAction2(); if (someCondition) impl->doSmallAction3(); else impl->doSmallAction1(); } // ... }; class Factory { // ... public: StaticInterface getInstaneById(size_t id) { StaticInterface result; // ... result.impl = std::shared_ptr< Interface >(new SomeImplementation(/* ... */)); return result; } // ... }; result_of(n1454) В стандартной библиотеке C++98/C++03 присутствуют алгоритмы. Большинство из них как один из аргументов берут вызываемую сущность. Т.е. указатель на ф-цию или функтор. Все, кто пользовался ими не раз испытывали нужду в том, чтобы, к примеру, зафиксировать первый аргумент вызываемой ф-ции и т.о. получить ф-цию, которой нужно передать на один аргумент меньше. Бывает, что нужно зафиксировать 3-й и 4-й аргументы, в пятый передать по ссылке и т.п. Бывают разные ситуации. Больше всего убивает, когда пытаешься реализовать более-менее сложную "махинацию" стандартными средствами библиотеки. А именно ptr_fun, mem_fun, bind1st, bind2nd и иже с ними. Вот зачем, к примеру, нужен ptr_fun? А затем, что для биндеров bind1st/2nd нужны специально оформленные функторы, а не "какой-то голый указатель на ф-цию". Короче говоря, возможности по работе с обобщёнными функторами в стандартной библиотеке C++98/03 просто ужасают(особенно после того, как попробовать boost::bind). Любой, кто пытался реализовать ф-циональность похожую на boost::bind с нуля(я пытался под порывом вдохновения после прочтения одного из творений Александреску), практически сразу наступают на такую граблю: не существует стандартных средств, чтобы узнать какой тип будет у возвращённого произвольной ф-цией значения, вызванной с произвольным набором аргументов(с произвольными типами аргументов). Приходится изобретать колесо. А колёса мы не любим ![]() Итак, шаблон result_of позволяет решить вышеозвученную проблему, а именно, узнать тип возвращаемого ф-цией значения. ![]() ![]() template <class FunctionCallTypes> // F(T1, T2, ..., TN) class result_of { public: typedef unspecified type; }; Предполагаемое применение. Лично я, кроме как в реализации своего биндера, пользы не вижу. Но у меня очень мал опыт разработки и реализации обобщённого кода. Уверен, что, раз эту штуку ввели, то достаточно часто возникает эта проблема. Т.о. предполагаемое применение - в любом обобщённом коде. ![]() ![]() template<typename F> struct forwardN { template<typename Args> struct result; template<typename T, typename T1, typename T2, ..., typename TN> struct result<T(T1, T2, ..., TN)> { typedef typename result_of<F(T1, T2, ..., TN)>::type type; }; template<typename T, typename T1, typename T2, ..., typename TN> struct result<const T(T1, T2, ..., TN)> { typedef typename result_of<const F(T1, T2, ..., TN)>::type type; }; template<typename T1, typename T2, ..., typename TN> typename result<forwardN(T1, T2, ..., TN)>::type operator()(T1& t1, T2& t2, ..., TN& tN) { return f(t1, t2, ..., tN); } template<typename T1, typename T2, ..., typename TN> typename result<const forwardN(T1, T2, ..., TN)>::type operator()(T1& t1, T2& t2, ..., TN& tN) const { return f(t1, t2, ..., tN); } F f; }; Function object binders(n1455) Как уже было сказано чуть выше, стандартная библиотека C++98/03 не содержит человеческих средств для связывания функторов. Предлагается добавить человеческий биндер(из Boost ![]() ![]() ![]() template<class F, class T1, class T2, ...., class TN> unspecified bind(F f, T1 t1, T2 t2, ..., TN tN); template<class R, class F, class T1, class T2, ...., class TN> unspecified bind(F f, T1 t1, T2 t2, ..., TN tN); Имеем две ф-ции. Вторая отличается от первой только тем, что можно явно указать желаемый тип возвращаемого значения и избавить биндер от необходимости вычислять возвращаемый тип тем более, что это не всегда возможно(насколько мне известно)... если явно указанный тип не совпадает с типом возвращаемого значения, то произойдёт преобразование(которое должно существовать - чудес не бывает ![]() Используются очень просто: ![]() ![]() class Employee { public: // ... int number() const; }; std::vector<Employee> v; // sort by employee ID number std::sort( v.begin(), v.end(), bind( std::less<int>(), bind(&Employee::number, _1), bind(&Employee::number, _2))); Function object wrappers(n1402) ![]() ![]() class bad_function_call; // исключение, которое можно получить при неправильном использовании function template<class Function> class function; // сама обёртка // Function == R (T1, T2, ..., TN) Как вы могли заметить, упомянутый выше биндер возвращает значение типа "unspecified"... Это означает, что стандарт не оговаривает, какой тип должен возвращать биндер, главное, чтобы тип и само значение соответствовали определённым требованиям. Т.о. в чистом виде биндер можно использовать только с шаблонными ф-циями и сохранить значение, возвращённое биндером вне шаблона не получится... ![]() ![]() sdt::transform(a.begin(), a.end(), b.begin(), a.begin(), bind(std::plus(), _1, _2)); // Имеет смысл. int x = bind(std::plus(), _1, _2)(10, 20); // x = 30. Проще написать x = 10 + 20, чем такое. Очень часто возникает необходимость сохранить функтор, возвращённый биндером и при этом, использовать шаблоны не получается из-за архитектурных особенностей. К примеру, события - они хранятся в классе обычной кнопки. Никакой специализации кнопки для того, чтобы добавить обработчик события делать никто не будет(да и что, если обработчик нужно в run-time менять на другой?). Итак, предлагается обёртка, которая может хранить в себе любую вызываемую сущность, подходящую под заданную сигнатуру(тип возвращаемого значения + количество и типы аргументов). Замечу, что она сама является вызываемой сущностью. Правда, за её универсальностью скрывается коварный минус: она полиморфна откуда следует, что будет дополнительный расход процессорного времени из-за полиморфного оверхэда. ![]() ![]() function<int(int,int) f = bind(std::plus(), _1, _2); // сохраняем функтор sdt::transform(a.begin(), a.end(), b.begin(), a.begin(), bind(std::plus(), _1, _2)); // получаем производительную трансформацию. sdt::transform(a.begin(), a.end(), b.begin(), a.begin(), f); // получаем overhead из-за полиморфизма. // зато, есть и большие плюсы - обёртку можно хранить в обычном объекте как обработчик события, к примеру class { std::deque< function< bool(int, int) > > events; protected: // ... void raiseOnClickEvent(int x, int y) { for (...) if ((*i)(x, y)) // call handler break; } public: // ... void connectHandler(const function< bool(int, int) > &handler, bool connectToEnd = true) { if (connectToEnd) events.push_back(handler); else events.push_front(handler); } }; Type traits(n1424) ![]() ![]() // primary type categories: template <class T> struct is_void; template <class T> struct is_integral; template <class T> struct is_floating_point; template <class T> struct is_array; template <class T> struct is_pointer; template <class T> struct is_reference; template <class T> struct is_member_object_pointer; template <class T> struct is_member_function_pointer; template <class T> struct is_enum; template <class T> struct is_union; template <class T> struct is_class; template <class T> struct is_function; // composite type categories: template <class T> struct is_arithmetic; template <class T> struct is_fundamental; template <class T> struct is_object; template <class T> struct is_scalar; template <class T> struct is_compound; template <class T> struct is_member_pointer; // type properties: template <class T> struct is_const; template <class T> struct is_volatile; template <class T> struct is_pod; template <class T> struct is_empty; template <class T> struct is_polymorphic; template <class T> struct is_abstract; template <class T> struct has_trivial_constructor; template <class T> struct has_trivial_copy; template <class T> struct has_trivial_assign; template <class T> struct has_trivial_destructor; template <class T> struct has_nothrow_constructor; template <class T> struct has_nothrow_copy; template <class T> struct has_nothrow_assign; template <class T> struct has_virtual_destructor; template <class T> struct is_signed; template <class T> struct is_unsigned; template <class T> struct alignment_of; template <class T> struct rank; template <class T, unsigned I = 0> struct extent; // type relations: template <class T, class U> struct is_same; template <class Base, class Derived> struct is_base_of; template <class From, class To> struct is_convertible; // const-volatile modifications: template <class T> struct remove_const; template <class T> struct remove_volatile; template <class T> struct remove_cv; template <class T> struct add_const; template <class T> struct add_volatile; template <class T> struct add_cv; // reference modifications: template <class T> struct remove_reference; template <class T> struct add_reference; // array modifications: template <class T> struct remove_extent; template <class T> struct remove_all_extents; // pointer modifications: template <class T> struct remove_pointer; template <class T> struct add_pointer; // other transformations: template <std::size_t Len, std::size_t Align> struct aligned_storage; Характеристики типов - это такие шаблоны, которые позволяют узнать кое-что о типе T. Имеют широкое применение в шаблонном программировании. Random Number Generation(n1452) Старый добрый rand заменит целая библиотека. Это разумно т.к. используя rand случайных чисел добится сложно, а применяются они много где(игры, моделирование, тестирование, криптография и компьютерная безопасность). Имеет смысл распределения. Представляет из себя функтор, который на вход берёт объект, отвечающий концепции Uniform random number generator, на выход даёт распределение. Включённых в TR1 распределений(отвечающих концепции) много, список приводить смысла, думаю, не имеет. Специальные математические функции(n1542) Теперь <cmath> обзавёлся специальными математическими ф-циями. Теперь, возможно, проще будет писать программы, занимающимися научными расчётами. Описывать этот пункт более подробно, думаю, смысла нету, тем более, что в высшей математике я смыслю мало ![]() Tuple(n1403) ![]() ![]() // Header <tuple> synopsis // Class template tuple template < class T1 = unspecified , class T2 = unspecified , ..., class TM = unspecified > class tuple; // Tuple creation functions const unspecified ignore; template<class T1, class T2, ..., class TN> tuple<V1, V2, ..., VN> make_tuple(const T1&, const T2& , ..., const TN&); template<class T1, class T2, ..., class TN> tuple<T1&, T2&, ..., TN&> tie(T1&, T2& , ..., TN&); // Tuple helper classes template <class T> class tuple_size; template <int I, class T> class tuple_element; // Element access template <int I, class T1, class T2, ..., class TN> RJ get(tuple<T1, T2, ..., TN>&); template <int I, class T1, class T2, ..., class TN> PJ get(const tuple<T1, T2, ..., TN>&); // relational operators template<class T1, class T2, ..., class TM, class U1, class U2, ..., class UM> bool operator==(const tuple<T1, T2, ..., TM>&, const tuple<U1, U2, ..., UM>&); template<class T1, class T2, ..., class TM, class U1, class U2, ..., class UM> bool operator<(const tuple<T1, T2, ..., TM>&, const tuple<U1, U2, ..., UM>&); template<class T1, class T2, ..., class TM, class U1, class U2, ..., class UM> bool operator!=(const tuple<T1, T2, ..., TM>&, const tuple<U1, U2, ..., UM>&); template<class T1, class T2, ..., class TM, class U1, class U2, ..., class UM> bool operator>(const tuple<T1, T2, ..., TM>&, const tuple<U1, U2, ..., UM>&); template<class T1, class T2, ..., class TM, class U1, class U2, ..., class UM> bool operator<=(const tuple<T1, T2, ..., TM>&, const tuple<U1, U2, ..., UM>&); template<class T1, class T2, ..., class TM, class U1, class U2, ..., class UM> bool operator>=(const tuple<T1, T2, ..., TM>&, const tuple<U1, U2, ..., UM>&); Tuple(англ. кортеж) - это std::pair только на произвольное количество элементов. Есть ф-ции make_tuple(аналог make_pair) и tie(аналог make_tuple, только все типы оборачиваются в reference_wrapper). Есть шаблоны для узнавания размера кортежа(tuple_size< SomeTuple >::value) и для узнавания N-ого типа в кортеже(tuple_element< N, SomeTuple >::type). Есть ф-ции для вытягивания N-ого элемента из кортежа(get< N >(someTupleInstance)). Есть ф-ции сравнения которые эквиваленты логическому И между результатами поэлементного сравнения. Кортежы CopyConstructible и Assignable, причём справа может стоять кортеж другого типа - главное, чтобы были соответствующие copy constructor(copy assignment operator) позволяющие поэлементно сконструировать копии(приравнять). У tuple есть конструктор копии и оператор присваивания от std::pair(только если tuple_size<Tuple>::value == 2). Также, шаблоны tuple_size, tuple_element и ф-ции get перегружены для случая с std::pair и std::array(см. ниже). std::array считаеться как кортеж из N элементов одинакового типа. Замечу, что применения tuple, в отличии от std::pair не оганичиваются только аггрегированием нескольких объектов в один - их ещё можно использовать как списки типов(вместе с шаблонами tuple_size и tuple_element). Fixed Size Array(n1548) ![]() ![]() // Class template array template <class T, size_t N > struct array; // Array comparisons template <class T, size_t N> bool operator== (const array<T,N>& x, const array<T,N>& y); template <class T, size_t N> bool operator!= (const array<T,N>& x, const array<T,N>& y); template <class T, size_t N> bool operator< (const array<T,N>& x, const array<T,N>& y); template <class T, size_t N> bool operator> (const array<T,N>& x, const array<T,N>& y); template <class T, size_t N> bool operator<= (const array<T,N>& x, const array<T,N>& y); template <class T, size_t N> bool operator>= (const array<T,N>& x, const array<T,N>& y); Представляет из себя обёртку для массивов фиксированной длины. Unordered associative containers(n1456) Элементы в обычных ассоциативных контейнерах из C++03(map, set, multimap, multiset) упорядочены по ключу. Далее речь пойдёт о неупорядоченных ассоциативных контейнерах(unordered_map, unordered_*). Принцип их работы заключается в том, что их ключи хэшируются и хранятся по принципу хэш таблицы. ![]() ![]() // Hash function base template template <class T> struct hash : public std::unary_function<T, std::size_t> { std::size_t operator()(T val) const; }; // Class template unordered_set template < class Value, class Hash = hash<Value>, class Pred = std::equal_to<Value>, class Alloc = std::allocator<Value> > class unordered_set; // Class template unordered_multiset template < class Value, class Hash = hash<Value>, class Pred = std::equal_to<Value>, class Alloc = std::allocator<Value> > class unordered_multiset; // Class template unordered_map template < class Key, class T, class Hash = hash<Key>, class Pred = std::equal_to<Key>, class Alloc = std::allocator<std::pair<const Key, T> > > class unordered_map; // Class template unordered_multimap template < class Key, class T, class Hash = hash<Key>, class Pred = std::equal_to<Key>, class Alloc = std::allocator<std::pair<const Key, T> > > class unordered_multimap; Итак. Основой для хэширования является функтор hash. В TR1 определены специализации этого шаблона для всех cv-unqualified арифметических типов, для любых указателей(T *) и для string/wstring. В неупорядоченных ассоциативных контейнерах всё работает почти точно так же как и у соответствующих контейнеров без префикса unordered. Зачем они нужны? Да затем же, зачем хэш-таблицы - для скорости. Возьмём ключ типа string - в случае поиска в обычном контейнере произойдёт log2N сравнений. А если строки по 50 мб? Накладно. Развею ваши иллюзии(если таковые появились) - в худшем случае в хэш-контейнер пройзойдёт не меньше сравнений. Но для худшего случая нужно постараться, а в общем же случае - 1/2/3/мало сравнений при любом N ![]() Regular expressions(n1429) Регулярные выражения - это удобный, мощный и лаконичный способ работы со строками(поиск/выделение фрагментов/замены фрагментов и т.п.). Они присутствуют во многих языках и стали чуть ли не промышленным стандартом(??) в этой области. Как сами регулярные выражения, так и часть из TR1, реализующая ф-циональность регулярных выражений достаточно обширны и нет возможности описать их здесь полностью. Описывать частично смысла не имеет. Могу лишь привести пример: ![]() ![]() regex e("(\\d{3,4})[- ]?(\\d{4})[- ]?(\\d{4})[- ]?(\\d{4})"); bool is_possible_card_number(const std::string& input) { // // return false for partial match, true for full match, or throw for // impossible match based on what we have so far... match_results<std::string::const_iterator> what; if(0 == boost::regex_match(input, what, e, match_default | match_partial)) { // the input so far could not possibly be valid so reject it: throw std::runtime_error("Invalid data entered - this could not possibly be a valid card number"); } // OK so far so good, but have we finished? if(what[0].matched) { // excellent, we have a result: return true; } // what we have so far is only a partial match... return false; } Что мы имеем в итоге? Стандартизация TR1 была начата в 2001 году, ещё до выхода С++03. В силу ли этой причины или в силу того, что комитет не собирался добавлять ни в язык ни в библиотеку ничего кардинально нового, но TR1 по содержанию своему очень жалок на первый взгляд(учитывая то, что реализация всего содержимого TR1 на момент его выпуска уже давно была в том же Boost). С другой стороны, все элементы TR1 можно реализовать с помощью стандартного С++ и никаких системно-специфичных вещей там нету, что, несомненно плюс. Ещё не могу не заметить, что не смотря на скудность своего содержания, TR1 представляет из себя 198 страниц формализованного текста, а это больше чем четверть того, что было в существовавшем на тот момент стандарте С++98. TR2 в сравнении с TR1 будет просто несравненно огромен. Чего там только не будет. Про TR2 в следующий раз ![]() И напоследок: не изобретайте велосипедов©, по возможности используйте уже стандартизованные средства. Обсуждение, дополнения и коррективы приветствуются. Всем спасибо за внимание. |
Сообщ.
#2
,
|
|
|
Цитата archimed7592 @ Возьмём ключ типа string - в случае поиска в обычном контейнере произойдёт log2N сравнений. А если строки по 50 мб? Накладно. А вычислять hash не накладно? ![]() Неравные строки заканчивают сравниваться, как только находится первое несовпадение соответствующих символов. А сколько ты будешь вычислять hash своей длинной строки? |
Сообщ.
#3
,
|
|
|
Цитата Unreal Man @ Строки заканчивают сравниваться, как только находится первое несовпадение соответствующих символов. А сколько ты будешь вычислять hash своей длинной строки? ![]() ![]() ![]() |
![]() |
Сообщ.
#4
,
|
|
Цитата Unreal Man @ Неравные строки заканчивают сравниваться, как только находится первое несовпадение соответствующих символов. А сколько ты будешь вычислять hash своей длинной строки? А сохранять хэш не судьба? ![]() Цитата LuckLess @ Ну это, имхо, от реализации сильно зависит Както проводил сравнение.. давно еще... имеет смысл только если строки очень длинные и при этом крайне похожие, но разные ![]() ![]() |
Сообщ.
#5
,
|
|
|
Цитата archimed7592 @ А сохранять хэш не судьба? Во-первых, иногда в этом в принципе нет смысла, т.к. поиск по конкретно взятой строке однократный. Во-вторых, будет ли метод find, который принимает именно hash вместо самого ключа? |
![]() |
Сообщ.
#6
,
|
|
Цитата Unreal Man @ Во-первых, иногда в этом в принципе нет смысла, т.к. поиск по конкретно взятой строке однократный Я имею ввиду сохранить хэш для хранимых в контейнере элементов. Цитата Unreal Man @ Во-вторых, будет ли метод find, который принимает именно hash вместо самого ключа? Зачем? Принимает значение. Вычисляем хэш для этого значения. Ищем хэш, в сохранённых, равный этому. Если находим, то сравниваем строки уже функтором equal_to. В принципе, нужно посмотреть требования к контейнерам с точки зрения complexity - тогда всё встанет на свои места ![]() |
Сообщ.
#7
,
|
|
|
Цитата archimed7592 @ Я имею ввиду сохранить хэш для хранимых в контейнере элементов. В смысле хэши? А разве можно как-то иначе? ![]() Цитата archimed7592 @ Зачем? Принимает значение. Вычисляем хэш для этого значения. Вот на это-то у тебя и уйдёт много времени, если значение – это большая строка. Представь, что строка состоит из сотни символов. Хэш обычно вычисляется с учётом всех символов. А для сравнения двух строк обычно требуется 1 – 3 посимвольных сравнений. Даже с учётом логарифмической сложности получается не так уж и много. Только совпадающие строки при сравнении тратят много времени. В итоге или получается вровень, или хэшированный контейнер показывает незначительное преимущество, IMHO, не оправдывающее всей этой возни с хэшами (по крайней мере, так у меня выходило). |