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: не нужно изобретать велосипедов .

---

Ссылки по теме
• Что такое стандарт:
  Что такое стандарт С++ и где его взять
• Немного о готовящемся стандарте С++09:
  Новый стандарт C++: C++09
• Оффициальные документы, описывающие TR1:
  Draft Technical Report on C++ Library Extensions(n1836)
  Library Extension Technical Report - Issues List(n1837)
• Реализация TR1 командой Boost:
  Boost.TR1
• Немного о TR2:
  тут будет ссылка(потом)

---

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()(...).

Предполагаемое применение.
• Там, где вывод(deduce) типа шаблонного аргумента приведёт к нессылочному типу(когда желаемым является ссылочный тип).
  
  

  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.
  }
• Там, где использование ссылок недопустимо(в контейнерах, к примеру).
  
  

  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());
• В биндерах(и вообще там, где используются функторы). Если обёртка хранит функтор(указатель на ф-цию или любую другую вызываемую сущность), то её экземпляр тоже становится вызываемой сущностью.
  
  

  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)

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(только для сравнения).
• Когда время жизни объекта ограничивается одной ф-цией(блоком кода, объектом), но использование объекта с автоматическим временем жизни по каким-то причинам невозможно(нежелательно).
  
  

  void f()
  {
      std::auto_ptr< ProductA > pa(Factory::instance().createProductA());
   
      // ...
   
      // здесь произойдёт деструкция pa и динамический объект удалится.
  }
   
  class MyWrapper
  {
      std::auto_ptr< MyBigObject > obj;
  public:
      MyWrapper()
          : obj(new MyBigObject())
      { }
  };
• Там, где нужно явно показать, что передаваемый как аргумент указатель должен указывать на объект с динамическим временем жизни и этот объект(как и контроль времени его жизни) переходит во владение этой ф-ции(она может передать владение куда-то ещё).
  
  

  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);
• Там, где нужно явно показать, что возвращаемый ф-цией указатель указывает на объект с динамическим временем жизни и этот объект(как и контроль времени его жизни) переходит во владение вызывавшей ф-ции(она может передать владение куда-то ещё).
  
  

  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 - везде, где динамическим объектом владеют несколько объектов/потоков/ф-ций и т.п.

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.
  Представляет из себя функтор, каждый вызов которого возвращает очередное (псевдо)случайное число.
• 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)

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

Представляет из себя обёртку для массивов фиксированной длины.

Преимуществ много:
• Как и обычные 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_*). Принцип их работы заключается в том, что их ключи хэшируются и хранятся по принципу хэш таблицы.

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

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

---

Обсуждение, дополнения и коррективы приветствуются. Всем спасибо за внимание.

Цитата archimed7592 @ 19.06.07, 00:44

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

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

Сообщение отредактировано: Unreal Man - 19.06.07, 11:16

Цитата Unreal Man @ 19.06.07, 10:54

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

Както проводил сравнение.. давно еще... имеет смысл только если строки очень длинные и при этом крайне похожие, но разные

Цитата Unreal Man @ 19.06.07, 10:54

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

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

Цитата LuckLess @ 19.06.07, 10:59

Както проводил сравнение.. давно еще... имеет смысл только если строки очень длинные и при этом крайне похожие, но разные

Ну это, имхо, от реализации сильно зависит

Цитата archimed7592 @ 19.06.07, 11:56

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

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

Цитата Unreal Man @ 19.06.07, 13:47

Во-первых, иногда в этом в принципе нет смысла, т.к. поиск по конкретно взятой строке однократный

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

Цитата Unreal Man @ 19.06.07, 13:47

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

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

Цитата archimed7592 @ 19.06.07, 14:05

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

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

Цитата archimed7592 @ 19.06.07, 14:05

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

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