На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: Qraizer, Hsilgos
  
> TR1. Technical Report on C++ Library Extensions. , Расширение стандартной библиотеки С++.
    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)

    ExpandedWrap disabled
      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()(...).
      Предполагаемое применение.
    • Там, где вывод(deduce) типа шаблонного аргумента приведёт к нессылочному типу(когда желаемым является ссылочный тип).
      ExpandedWrap disabled
        void f(int & r)
        {
            ++r;
        }
         
        template<class F, class T> void g(F f, T t) { f(t); }
         
        int main()
        {
            int i = 0;
            g(f, i);
            cout << i << endl; // 0
            g(f, ref(i));
            cout << i << endl; // 1
         
            int i1(5), i2(10);
         
            function<MyClass()> f1 = bind(std::plus(), i1, i2); // создасться функтор в котором i1 и i2 будут сохранены по значению
            function<MyClass()> f2 = bind(std::plus(), cref(obj1), cref(obj2)); // создасться функтор в котором будут сохранены ссылки на i1 и i2.
         
            i1 *= 2;
         
            int i3 = f1(); // будет использовано старое значение i1 т.е. результат 15.
            int i4 = f2(); // будет использовано текущее значение i1 т.к. рузультат 20.
        }
    • Там, где использование ссылок недопустимо(в контейнерах, к примеру).
      ExpandedWrap disabled
        std::list<int> numbers;
        std::vector<reference_wrapper<int> > number_refs;
        for(int i = 0; i < 100; ++i)
        {
            numbers.push_back(4*i*i^2 - 10*i + 3);
            number_refs.push_back(ref(numbers.back()));
        }
         
        std::sort(number_refs.begin(), number_refs.end());
    • В биндерах(и вообще там, где используются функторы). Если обёртка хранит функтор(указатель на ф-цию или любую другую вызываемую сущность), то её экземпляр тоже становится вызываемой сущностью.
      ExpandedWrap disabled
        struct counting_less
        {
            typedef bool result_type;
         
            template<typename T> bool operator()(const T& x, const T& y)
            {
                ++count;
                return x < y;
            }
         
            int count;
        };
         
        // ...
         
        vector<int> elements;
        // fill elements
        counting_less cl;
        sort(elements.begin(), elements.end(), ref(cl));
        std::cout << cl.count << " comparisons in sort\n";




    Smart Pointers(n1450)

    ExpandedWrap disabled
      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 имеет такое название не случайно :). Shared(англ. общий) относится к стратегие владения: в отличии от auto_ptr со стратегией "единственного владельца", у shared_ptr стратегия разделения владения объектом т.е. владельцев может быть много(shared ownership).

    Также предлагается т.н. 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 возможно применение почти везде, где возможно применение указателя.
      Характерное применение auto_ptr(только для сравнения).
    • Когда время жизни объекта ограничивается одной ф-цией(блоком кода, объектом), но использование объекта с автоматическим временем жизни по каким-то причинам невозможно(нежелательно).
      ExpandedWrap disabled
        void f()
        {
            std::auto_ptr< ProductA > pa(Factory::instance().createProductA());
         
            // ...
         
            // здесь произойдёт деструкция pa и динамический объект удалится.
        }
         
        class MyWrapper
        {
            std::auto_ptr< MyBigObject > obj;
        public:
            MyWrapper()
                : obj(new MyBigObject())
            { }
        };
    • Там, где нужно явно показать, что передаваемый как аргумент указатель должен указывать на объект с динамическим временем жизни и этот объект(как и контроль времени его жизни) переходит во владение этой ф-ции(она может передать владение куда-то ещё).
      ExpandedWrap disabled
        struct Interface
        {
            virtual void foo() = 0;
            // ...
         
            virtual ~Interface() { }
        };
         
        class MyClass
        {
            std::auto_ptr< Interface > impl_;
        public:
            explicit MyClass(std::auto_ptr< Interface > impl)
                : impl_(impl)
            {
            }
        };
         
        template < class T >
        class Implementation
            : public Interface
        {
            // ...
        };
         
        std::auto_ptr< Interface > impl1 (new Implementation< int >());
        std::auto_ptr< Interface > impl2 (new Implementation< double >());
         
        MyClass obj1(impl1);
        MyClass obj2(impl2);
    • Там, где нужно явно показать, что возвращаемый ф-цией указатель указывает на объект с динамическим временем жизни и этот объект(как и контроль времени его жизни) переходит во владение вызывавшей ф-ции(она может передать владение куда-то ещё).
      ExpandedWrap disabled
        class MyClass
        {
            MyClass() { }
            MyClass(const MyClass &);
        public:
            static std::auto_ptr< MyClass > createInstance()
            {
                return std::auto_ptr< MyClass >(new MyClass());
            }
        };
         
        std::auto_ptr< MyClass > instance = MyClass::createInstance();
        MyClass::createInstance(); // утечки памяти не будет

    Характерное применение shared_ptr - везде, где динамическим объектом владеют несколько объектов/потоков/ф-ций и т.п.
    ExpandedWrap disabled
      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 позволяет решить вышеозвученную проблему, а именно, узнать тип возвращаемого ф-цией значения.

    ExpandedWrap disabled
      template <class FunctionCallTypes> // F(T1, T2, ..., TN)
      class result_of
      {
      public:
          typedef unspecified type;
      };


    Предполагаемое применение.

    Лично я, кроме как в реализации своего биндера, пользы не вижу. Но у меня очень мал опыт разработки и реализации обобщённого кода. Уверен, что, раз эту штуку ввели, то достаточно часто возникает эта проблема. Т.о. предполагаемое применение - в любом обобщённом коде.

    ExpandedWrap disabled
      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 :D).
    ExpandedWrap disabled
      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);

    Имеем две ф-ции. Вторая отличается от первой только тем, что можно явно указать желаемый тип возвращаемого значения и избавить биндер от необходимости вычислять возвращаемый тип тем более, что это не всегда возможно(насколько мне известно)... если явно указанный тип не совпадает с типом возвращаемого значения, то произойдёт преобразование(которое должно существовать - чудес не бывает :)).

    Используются очень просто:
    ExpandedWrap disabled
      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)

    ExpandedWrap disabled
      class bad_function_call; // исключение, которое можно получить при неправильном использовании function
       
      template<class Function> class function; // сама обёртка
      // Function == R (T1, T2, ..., TN)


    Как вы могли заметить, упомянутый выше биндер возвращает значение типа "unspecified"... Это означает, что стандарт не оговаривает, какой тип должен возвращать биндер, главное, чтобы тип и само значение соответствовали определённым требованиям. Т.о. в чистом виде биндер можно использовать только с шаблонными ф-циями и сохранить значение, возвращённое биндером вне шаблона не получится...
    ExpandedWrap disabled
      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 менять на другой?).

    Итак, предлагается обёртка, которая может хранить в себе любую вызываемую сущность, подходящую под заданную сигнатуру(тип возвращаемого значения + количество и типы аргументов). Замечу, что она сама является вызываемой сущностью. Правда, за её универсальностью скрывается коварный минус: она полиморфна откуда следует, что будет дополнительный расход процессорного времени из-за полиморфного оверхэда.

    ExpandedWrap disabled
      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)

    ExpandedWrap disabled
      // 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.
      Представляет из себя функтор, каждый вызов которого возвращает очередное (псевдо)случайное число.
    • Pseudo-random number engine.
      Расщирение концепции Uniform random number generator для того, чтобы генератор можно было создавать, копировать и управлять им(seed, etc.).
        Шаблонные классы, отвечающие концепции
      • linear_congruential
      • mersenne_twister
      • subtract_with_carry
      • subtract_with_carry_01
      • discard_block

        Специализации шаблонных классов, отвечающих концепции
      • minstd_rand0
      • minstd_rand
      • mt19937
      • ranlux_base_01
      • ranlux64_base_01
      • ranlux3
      • ranlux4
      • ranlux3_01
      • ranlux4_01
    • Random distribution.
      Имеет смысл распределения.
      Представляет из себя функтор, который на вход берёт объект, отвечающий концепции Uniform random number generator, на выход даёт распределение.
      Включённых в TR1 распределений(отвечающих концепции) много, список приводить смысла, думаю, не имеет.




    Специальные математические функции(n1542)

    Теперь <cmath> обзавёлся специальными математическими ф-циями. Теперь, возможно, проще будет писать программы, занимающимися научными расчётами.
    Описывать этот пункт более подробно, думаю, смысла нету, тем более, что в высшей математике я смыслю мало :).




    Tuple(n1403)

    ExpandedWrap disabled
      // 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)

    ExpandedWrap disabled
      // 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);


    Представляет из себя обёртку для массивов фиксированной длины.
      Преимуществ много:
    • Как и обычные T[N] их можно инициализировать array<int, 2> = {1, 2}, использовать оператор[] и т.д.
    • Является STL-совместимым контейнером.(Sequence container).
      • В отличии от обычных T[N]
      • array<T, N> можно передавать в ф-ции(происходит копирование).
      • у array<T, N> можно легко узнать его размер.
      • проще использовать в STL-алгоритмах(из-за его STL-совместимости).




    Unordered associative containers(n1456)

    Элементы в обычных ассоциативных контейнерах из C++03(map, set, multimap, multiset) упорядочены по ключу.
    Далее речь пойдёт о неупорядоченных ассоциативных контейнерах(unordered_map, unordered_*). Принцип их работы заключается в том, что их ключи хэшируются и хранятся по принципу хэш таблицы.

    ExpandedWrap disabled
      // 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, реализующая ф-циональность регулярных выражений достаточно обширны и нет возможности описать их здесь полностью. Описывать частично смысла не имеет. Могу лишь привести пример:

    ExpandedWrap disabled
      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 в следующий раз :).

    И напоследок: не изобретайте велосипедов©, по возможности используйте уже стандартизованные средства.




    Обсуждение, дополнения и коррективы приветствуются. Всем спасибо за внимание.
      Цитата archimed7592 @
      Возьмём ключ типа string - в случае поиска в обычном контейнере произойдёт log2N сравнений. А если строки по 50 мб? Накладно.

      А вычислять hash не накладно? :D
      Неравные строки заканчивают сравниваться, как только находится первое несовпадение соответствующих символов. А сколько ты будешь вычислять hash своей длинной строки?
      Сообщение отредактировано: Unreal Man -
        Цитата Unreal Man @
        Строки заканчивают сравниваться, как только находится первое несовпадение соответствующих символов. А сколько ты будешь вычислять hash своей длинной строки?

        :yes: :yes: Както проводил сравнение.. давно еще... имеет смысл только если строки очень длинные и при этом крайне похожие, но разные ;)
          Цитата Unreal Man @
          Неравные строки заканчивают сравниваться, как только находится первое несовпадение соответствующих символов. А сколько ты будешь вычислять hash своей длинной строки?

          А сохранять хэш не судьба? :huh:


          Цитата LuckLess @
          Както проводил сравнение.. давно еще... имеет смысл только если строки очень длинные и при этом крайне похожие, но разные ;)
          Ну это, имхо, от реализации сильно зависит :)
            Цитата archimed7592 @
            А сохранять хэш не судьба?

            Во-первых, иногда в этом в принципе нет смысла, т.к. поиск по конкретно взятой строке однократный. Во-вторых, будет ли метод find, который принимает именно hash вместо самого ключа?
              Цитата Unreal Man @
              Во-первых, иногда в этом в принципе нет смысла, т.к. поиск по конкретно взятой строке однократный

              Я имею ввиду сохранить хэш для хранимых в контейнере элементов.


              Цитата Unreal Man @
              Во-вторых, будет ли метод find, который принимает именно hash вместо самого ключа?

              Зачем? Принимает значение. Вычисляем хэш для этого значения. Ищем хэш, в сохранённых, равный этому. Если находим, то сравниваем строки уже функтором equal_to.
              В принципе, нужно посмотреть требования к контейнерам с точки зрения complexity - тогда всё встанет на свои места :).
                Цитата archimed7592 @
                Я имею ввиду сохранить хэш для хранимых в контейнере элементов.

                В смысле хэши? А разве можно как-то иначе? :blink:

                Цитата archimed7592 @
                Зачем? Принимает значение. Вычисляем хэш для этого значения.

                Вот на это-то у тебя и уйдёт много времени, если значение – это большая строка. Представь, что строка состоит из сотни символов. Хэш обычно вычисляется с учётом всех символов. А для сравнения двух строк обычно требуется 1 – 3 посимвольных сравнений. Даже с учётом логарифмической сложности получается не так уж и много. Только совпадающие строки при сравнении тратят много времени. В итоге или получается вровень, или хэшированный контейнер показывает незначительное преимущество, IMHO, не оправдывающее всей этой возни с хэшами (по крайней мере, так у меня выходило).
                1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                0 пользователей:


                Рейтинг@Mail.ru
                [ Script execution time: 0,0737 ]   [ 15 queries used ]   [ Generated: 3.07.25, 09:53 GMT ]