Ordered indices

Упорядоченные индексы сортируют элементы в<multi_index_container>в соответствии с заданным ключом и связанным с ним сравнительным предикатом. Эти индексы можно рассматривать как аналоги стандартного контейнера<std::set>, и на самом деле они воспроизводят его интерфейс, хотя и с некоторыми незначительными различиями, продиктованными общими ограничениями Boost. MultiIndex.

Unique and non-unique variants

Упорядоченные индексы классифицируются науникальные, которые запрещают двум элементам иметь одинаковое ключевое значение, инеуникальныеиндексы, которые допускают дубликаты. Еще раз рассмотрим определение

typedef multi_index_container<
  employee,
  indexed_by<
    ordered_unique<identity<employee> >,
    ordered_non_unique<member<employee,std::string,&employee::name> >
  > 
> employee_set;

В этом случае<multi_index_container>первый индекс должен рассматриваться как уникальный (поскольку идентификаторы являются эксклюзивными для каждого сотрудника) и, таким образом, объявляется с использованием<ordered_unique>, тогда как второй индекс не является уникальным (поскольку существует возможность, что два Джона Смита наняты в одной и той же компании), что определяется использованием<ordered_non_unique>.

Классификация упорядоченных индексов в уникальном и неуникальном оказывает влияние на то, какие элементы разрешено вставлять в данный<multi_index_container>; кратко говоря, уникальные упорядоченные индексы имитируют поведение<std::set>с, в то время как неуникальные упорядоченные индексы аналогичны<std::multiset>с. Например,<employee_set>может удерживать объекты<employee(0,"George Brown")>и<employee(1,"George Brown")>, но не принимает вставку<employee>объекта, идентификатор которого совпадает с идентификатором некоторого ранее вставленного сотрудника.

Можно указать более одного уникального индекса. Например, если мы добавим<employee>, чтобы включить дополнительный член для номера социального страхования, который разумно рассматривается как уникальный, следующее улавливает этот дизайн:

struct employee
{
  int         id;
  std::string name;
  int         ssnumber;
  employee(int id,const std::string& name,int ssnumber):
    id(id),name(name),ssnumber(ssnumber){}
  bool operator<(const employee& e)const{return id<e.id;}
};
typedef multi_index_container<
  employee,
  indexed_by<
    // sort by employee::operator<
    ordered_unique<identity<employee> >,
    
    // sort by less<string> on name
    ordered_non_unique<member<employee,std::string,&employee::name> >,
    
    // sort by less<int> on ssnumber
    ordered_unique<member<employee,int,&employee::ssnumber> >
  >
> employee_set;

Specification

Упорядоченные указатели индексов в<indexed_by>должны соответствовать одному из следующих синтаксисов:

(ordered_unique | ordered_non_unique)
  <[(tag)[,(key extractor)[,(comparison predicate)]]]>
(ordered_unique | ordered_non_unique)
  <[(key extractor)[,(comparison predicate)]]>

Первый необязательный аргумент используется, еслиметкисвязаны с индексом. Теперь перейдем к краткому обсуждению оставшихся аргументов упорядоченного указателя индекса.

Key extraction

Первый параметр шаблона (или второй, если теги поставляются) в спецификации упорядоченного индекса обеспечиваетизвлечение ключапредиката. Этот предикат берет целый элемент (в нашем примере ссылку на<employee>объект) и возвращает часть информации, с помощью которой выполняется сортировка. В большинстве случаев возникает одна из следующих двух ситуаций:

• < [85] >,< [85] >,< [85] >,< [85] >.< [86] >< [86] >< [86] >< [86] >< [86] >< [86] >< [86] >< [86] >]< [86] >< [86] >< [86] >< [86] >< [86] >] [< [86] >] [< [86] >] []] [< [86] >] [< [86] >] []] [< [86] >]] [< [86] >] [< [86] >]] [< [86] >] [< [86] >]] [< [86] >] [< [86] >]] [< [86] >] [< [86] >]] [< [86] >] [< [86] >]] [< [86] >] [< [86] >]] [[< [86] >]] [< [86] >]] [< [86] >]] [< [86] >]] [< [86] >]] [< [86] >]] [< [86] >] [< [86] >]] [< [86] >]] [[< [86] >]] [[[]]] [[[]]] [[[]]] [[[]]] [[]]] [[[]]] [[[]]] [[[]]]
• Сравнительно с тем, что он находится на грани, а также с тем, что он находится на грани банкротства. Boost.MultiIndex exte< [93] >, , , , , , , , .

ordered_unique<identity<employee> >

С помощью<identity>указывается, что<element>сами объекты служат ключом к этому индексу. С другой стороны, во втором индексе:

ordered_non_unique<member<employee,std::string,&employee::name> >

Мы используем<member>для извлечения<name>части<employee>объекта. Ключевым типом индекса является<std::string>.

Помимо<identity>и<member>, Boost.MultiIndex предоставляет несколько других предопределенных ключевых экстракторов и мощные способы их объединения. Ключевые экстракторы также могут быть определены пользователем. Проконсультируйтесь с ключевым разделомизвлеченияучебника для более подробного изложения этой темы.

Comparison predicates

Последней частью спецификации упорядоченного индекса является ассоциированныйсравнительный предикат, который должен заказать ключи менее чем по моде. Эти сравнительные предикаты не отличаются от тех, которые используются контейнерами STL, такими как<std::set>. По умолчанию (т.е. при отсутствии сравнительного предиката) индекс с ключами типа<key_type>сортирует элементы по<std::less<key_type>>. Если необходимы другие критерии сравнения, они могут быть указаны в качестве дополнительного параметра в индексной декларации:

// define a multiply indexed set with indices by id and by name
// in reverse alphabetical order
typedef multi_index_container<
  employee,
  indexed_by<
    ordered_unique<identity<employee> >, // as usual
    ordered_non_unique<
      member<employee,std::string,&employee::name>,
      std::greater<std::string>  // default would be std::less<std::string>
    >
  >
> employee_set;

Special lookup operations

Указанный упорядоченный индекс позволяет искать в зависимости от его ключевого типа, а не всего элемента. Например, чтобы найти Веронику Круз в<employee_set>, нужно написать:

employee_set es;
...
typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name::iterator it=es.get<name>().find("Veronica Cruz");

В качестве плюса, Буст. MultiIndex предоставляет операции поиска, принимающие ключи поиска, отличные от<key_type>индекса, который является особенно полезным объектом, когда<key_type>объекты дороги для создания. Заказанные контейнеры STL не обеспечивают эту функциональность, что часто приводит к неэлегантным обходным путям: рассмотрим, например, проблему определения сотрудников, чьи идентификаторы попадают в диапазон [0,100]. Учитывая, что ключом<employee_set>индекса #0 является сам<employee>, при первом подходе можно было бы написать следующее:

employee_set::iterator p0=es.lower_bound(employee(0,""));
employee_set::iterator p1=es.upper_bound(employee(100,""));

Обратите внимание, однако, что<std::less<employee>>на самом деле зависит только от идентификаторов сотрудников, поэтому было бы удобнее избегать создания целых<employee>объектов только ради их идентификаторов. Повышаю. MultiIndex позволяет: определить подходящий предикат сравнения

struct comp_id
{
  // compare an ID and an employee
  bool operator()(int x,const employee& e2)const{return x<e2.id;}
  // compare an employee and an ID
  bool operator()(const employee& e1,int x)const{return e1.id<x;}
};

Напишите поиск как

employee_set::iterator p0=es.lower_bound(0,comp_id());
employee_set::iterator p1=es.upper_bound(100,comp_id());

Здесь мы не только передаем идентификаторы вместо<employee>объектов: передается и альтернативный сравнительный предикат. В целом операции поиска упорядоченных индексов перегружены для принятиясовместимых критериев сортировки. Определение совместимости в этом контексте дано в ссылке, но грубо говоря, мы говорим, что предикат сравнения<C1>совместим с<C2>, если любая последовательность, отсортированная по<C2>, также отсортирована по отношению к<C1>. Ниже показано более интересное использование совместимых предикатов:

// sorting by name's initial
struct comp_initial
{
  bool operator()(char ch,const std::string& s)const{
    if(s.empty())return false;
    return ch<s[0];
  }
  bool operator()(const std::string& s,char ch)const{
    if(s.empty())return true;
    return s[0]<ch;
  }
};
// obtain first employee whose name begins with 'J' (ordered by name)
typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>(); 
employee_set_by_name::const_iterator it=
  name_index.lower_bound('J',comp_initial());

Retrieval of ranges

Поиск диапазона, т.е. поиск всех элементов в заданном интервале, является очень частой операцией, к которой можно прибегнуть стандартом<lower_bound>и<upper_bound>. Например, следующий код извлекает элементы<multi_index_container<double>>в интервале [100,200]:

typedef multi_index_container<double> double_set;
// note: default template parameters resolve to
// multi_index_container<double,indexed_by<unique<identity<double> > > >.
double_set s;
...
double_set::iterator it0=s.lower_bound(100.0);
double_set::iterator it1=s.upper_bound(200.0);
// range [it0,it1) contains the elements in [100,200]

Тонкие изменения в коде необходимы при рассмотрении строгих неравенств. Для извлечения элементовбольше, чем 100 именьше, чем 200, код должен быть переписан как

double_set::iterator it0=s.upper_bound(100.0);
double_set::iterator it1=s.lower_bound(200.0);
// range [it0,it1) contains the elements in (100,200)

Чтобы добавить к этой сложности, осторожный программист должен учитывать, что нижняя и верхняя границы искомого интервала совместимы: например, если нижняя граница 200 и верхняя граница 100, итераторы<it0>и<it1>, произведенные кодом выше, будут в обратном порядке, с возможно катастрофическими результатами, если будет испытан переход от<it0>к<it1>. Все эти детали делают поиск диапазона утомительной и подверженной ошибкам задачей.

Функция члена<range>, часто в сочетании с выражениямиBoost.Lambda, может значительно помочь облегчить эту ситуацию:

using namespace boost::lambda;
typedef multi_index_container<double> double_set;
double_set s;
...
std::pair<double_set::iterator,double_set::iterator> p=
  s.range(100.0<=_1,_1<=200); // 100<= x <=200
...
p=s.range(100.0<_1,_1<200);   // 100<  x < 200
...
p=s.range(100.0<=_1,_1<200);  // 100<= x < 200

<range>просто принимает предикаты, указывающие нижнюю и верхнюю границы искомого интервала. Пожалуйста, обратитесь к ссылке для подробного объяснения допустимых предикатов, переданных<range>.

Одна или обе границы могут быть опущены специальным маркером<unbounded>:

p=s.range(100.0<=_1,unbounded); // 100 <= x
p=s.range(unbounded,_1<200.0);  //   x <  200
p=s.range(unbounded,unbounded); // equiv. to std::make_pair(s.begin(),s.end())

Updating

Функция<replace>элемента выполняет замену данного элемента на месте, как показано в следующем примере:

typedef index<employee_set,name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>();
employee_set_by_name::iterator it=name_index.find("Anna Jones");
employee anna=*it;
anna.name="Anna Smith";      // she just got married to Calvin Smith
name_index.replace(it,anna); // update her record

<replace>выполняет эту замену таким образом, что:

• Сложность — это постоянное время, если изменённый элемент сохраняет свой первоначальный порядок относительно всех индексов; в противном случае он логарифмический.
• Итератор и эталонная валидность сохраняются.
• Операция полностью безопасна для исключения, т.е.<multi_index_container>остается неизменной, если выкинуто какое-либо исключение (происходящее от системы или типов данных пользователя).

Наблюдательный читатель мог заметить, что удобство<replace>стоит дорого: а именно, весь элемент должен быть скопировандважды, чтобы сделать обновление (при извлечении его и внутри<replace>). Если элементы дороги для копирования, это может быть довольно вычислительной стоимостью для модификации только крошечной части объекта. Чтобы справиться с этой ситуацией, Бут. MultiIndex предоставляет альтернативный механизм обновления, называемый<modify>:

struct change_name
{
  change_name(const std::string& new_name):new_name(new_name){}
  void operator()(employee& e)
  {
    e.name=new_name;
  }
private:
  std::string new_name;
};
...
typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>();
employee_set_by_name::iterator it=name_index.find("Anna Jones");
name_index.modify(it,change_name("Anna Smith"));

<modify>принимает функтор (или указатель на функцию), который передается со ссылкой на изменяемый элемент, тем самым устраняя необходимость в ложных копиях. Как и<replace>,<modify>сохраняет внутренние упорядочения всех индексов<multi_index_container>. Однако семантика<modify>не полностью эквивалентна<replace>. Рассмотрим, что происходит, если столкновение происходит в результате модификации элемента, то есть модифицированный элемент сталкивается с другим по отношению к некоторому уникальному упорядоченному индексу. В случае<replace>первоначальное значение сохраняется, и способ возвращается без изменения контейнера, но<modify>не может позволить себе такой подход, поскольку модифицирующий функтор не оставляет следов предыдущего значения элемента. Таким образом, ограничения целостности приводят к следующей политике: когда в процессе вызова происходит столкновение<modify>, элемент стирается и метод возвращается<false>. Существует еще одна версия<modify>, которая принимаетоткатфунктора, чтобы отменить изменения в случае столкновения:

struct change_id
{
  change_id(int new_id):new_id(new_id){}
  void operator()(employee& e)
  {
    e.id=new_id;
  }
private:
  int new_id;
};
...
employee_set::iterator it=...
int old_id=it->id; // keep the original id
// try to modify the id, restore it in case of collisions
es.modify(it,change_id(321),change_id(old_id));

В примере<change_id(old_id)>используется для восстановления исходных условий, когда модификация приводит к столкновениям с каким-либо другим элементом. Различия в поведении между<replace>,<modify>и<modify>с откатом должны рассматриваться программистом на индивидуальной основе для определения наилучшего механизма обновления.

Также представлены версии<modify>, названные<modify_key>. В этом случае модифицирующие функторы передают ссылку на<key_type>часть элемента вместо всего объекта.

struct change_str
{
  change_str(const std::string& new_str):new_str(new_str){}
  // note this is passed a string, not an employee
  void operator()(std::string& str)
  {
    str=new_str;
  }
private:
  std::string new_str;
};
...
typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>();
employee_set_by_name::iterator it=name_index.find("Anna Jones");
name_index.modify_key(it,change_str("Anna Smith"));

Как и<modify>, есть версии<modify_key>с откатом и без него.<modify>и<modify_key>особенно хорошо подходят для использования совместно сBoost.Lambdaдля определения модифицирующих функторов:

using namespace boost::lambda;
typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>();
employee_set_by_name::iterator it=name_index.find("Anna Jones");
name_index.modify_key(it,_1="Anna Smith");

<modify_key>требует, чтобы ключ-экстрактор был специального типа, называемогоread/write: Это обычно, но не всегда так.

Sequenced indices

В отличие от упорядоченных индексов, секвенированные индексы не накладывают на элементы фиксированный порядок: вместо этого они могут быть расположены в любом положении на последовательности, так же, как это позволяет<std::list>. Интерфейс секвенированных индексов, таким образом, разработан на основе<std::list>; почти каждая операция, представленная в стандартном контейнере, воспроизводится здесь, иногда с изменениями синтаксиса и/или семантики, чтобы справиться с ограничениями, налагаемыми Boost. MultiIndex. Важным отличием, комментируемымвыше, является тот факт, что значения, на которые указывают итераторы секвенированных индексов, рассматриваются какконстанта:

multi_index_container<
  int,
  indexed_by<sequenced<> >
> s;            // list-like container
s.push_front(0);
*(s.begin())=1; // ERROR: the element cannot be changed

Как и в случае с любым другим типом индекса, модификация элементов может быть выполнена посредством операций обновления.

Рассмотрим<multi_index_container>с двумя или более индексами, один из которых секвенированного типа. Если элемент вставляется через другой индекс, он автоматически добавляется к концу последовательности индекса. Пример поможет прояснить это:

multi_index_container<
  int,
  indexed_by<
    sequenced<>,           // sequenced type
    ordered_unique<identity<int> > // another index
  >
> s;
s.get<1>().insert(1); // insert 1 through index #1
s.get<1>().insert(0); // insert 0 through index #1
// list elements through sequenced index #0
std::copy(s.begin(),s.end(),std::ostream_iterator<int>(std::cout));
// result: 1 0

Таким образом, поведение секвенированных индексов, когда вставки не производятся через них, заключается в сохранении порядка вставки.

Specification

Последовательность индексов определяется конструкцией<sequenced>:

sequenced<[(tag)]>

Параметртегявляется необязательным.

List operations

Как упоминалось ранее, секвенированные индексы имитируют интерфейс<std::list>, и большинство исходных операций в нем также предоставляются. Однако семантика и сложность этих операций не всегда совпадают с операциями стандартного контейнера. Различия возникают главным образом из-за того, что вставки в секвенированный индекс не гарантируют успеха из-за возможного запрета другими индексами<multi_index_container>. Проконсультируйтесь сссылкойдля получения дополнительной информации.

Updating

Как и упорядоченные индексы, секвенированные индексы обеспечивают<replace>и.<modify>операций с идентичными функциональными возможностями. Однако аналога<modify_key>нет, поскольку секвенированные индексы не основаны на ключах.

Projection of iterators

Учитывая индексы<i1>и<i2>на одном и том же<multi_index_container>,<project>можно использовать для извлечения<i2>-итератора из<i1>-итератора, оба из которых указывают на один и тот же элемент контейнера. Эта функциональность позволяет программисту перемещаться между различными индексами одного и того же<multi_index_container>при выполнении сложных операций:

typedef employee_set::index<name>::type employee_set_by_name;
employee_set_by_name& name_index=es.get<name>();
// list employees by ID starting from Robert Brown's ID
employee_set_by_name::iterator it1=name_index.find("Robert Brown");
// obtain an iterator of index #0 from it1
employee_set::iterator it2=es.project<0>(it1); 
std::copy(it2,es.end(),std::ostream_iterator<employee>(std::cout));

Немного более интересный пример:

text_container tc;
// get a view to index #1 (ordered index on the words)
text_container::nth_index<1>::type& sorted_index=tc.get<1>();
// prepend "older" to all occurrences of "sister"
text_container::nth_index<1>::type::iterator it1=
  sorted_index.lower_bound("sister");
  
while(it1!=sorted_index.end()&&*it1=="sister"){
  // convert to an iterator to the sequenced index
  text_container::iterator it2=tc.project<0>(it1);
  tc.insert(it2,"older");
  ++it1;
}

При наличии<project>можно также использоватьметки.

Complexity and exception safety

<multi_index_container>обеспечивает ту же сложность и гарантии безопасности, что и эквивалентные контейнеры STL. Итератор и эталонная валидность сохраняются перед вставками даже для замены и изменения операций.

Соответствующие инстанциации<multi_index_container>могут фактически имитировать<std::set>,<std::multiset>и (с большими ограничениями)<std::list>, как показано в разделеметодов. Эти модели столь же эффективны, как и оригинальные контейнеры STL; обратитесь к ссылкедля получения дополнительной информации о гарантиях сложности и разделупроизводительностидля практических измерений эффективности.

Boost.MultiIndex Tutorial

Boost.MultiIndex tutorial

Index types

Пересмотрено 24 ноября 2015

© Copyright 2003-2015 Joaquín M López Muñoz. Распространяется под лицензией Boost Software License, версия 1.0. (См. сопроводительный файлLICENSE_1_0.txtили копию на) http://www.boost.org/LICENSE_1_0.txt

Статья Boost.MultiIndex Documentation - Tutorial - Basics раздела Boost.MultiIndex Documentation - Tutorial может быть полезна для разработчиков на c++ и boost.

:: Главная :: Boost.MultiIndex Documentation - Tutorial ::