What is a bimap?

Бимап представляет собой структуру данных, которая представляет двунаправленные отношения между элементами двух коллекций. Контейнер предназначен для работы в виде двух противоположных карт STL. Бимап между коллекцией<X>и коллекцией<Y>может рассматриваться как карта от<X>до<Y>(этот вид будет называтьсялевый вид карты) или как карта от<Y>до<X>(известный какправый вид карты). Кроме того, бимап также можно рассматривать как набор отношений между<X>и<Y>(названныйсборником взглядов на отношения).

Следующий код создает пустой контейнер:

typedef bimap<X,Y> bm_type;
bm_type bm;

Вы можете увидеть, как бимап-контейнер предлагает три вида на одну и ту же коллекцию двунаправленных отношений.

Если у нас есть какая-либо общая функция, которая работает с картами

template< class MapType >
void print_map(const MapType & m)
{
    typedef typename MapType::const_iterator const_iterator;
    for( const_iterator iter = m.begin(), iend = m.end(); iter != iend; ++iter )
    {
        std::cout << iter->first << "-->" << iter->second << std::endl;
    }
}

Мы можем использоватьлевый вид картыиправый вид картыс ним.

bimap< int, std::string > bm;
...
print_map( bm.left  );
print_map( bm.right );

И результат будет

1 --> one
2 --> two
...
one --> 1
two --> 2
...

Layout of the relation and the pairs of a bimap

Класс<relation>представляет два связанных элемента. Эти два значения называются слева и справа, чтобы выразить симметрию этого типа. Классы бимап-пар совместимы с<std::pairs>.

Step by step

Удобный заголовок доступен в каталоге boost:

#include <boost/bimap.hpp>

Определим двунаправленную карту между целыми числами и строками:

typedef boost::bimap< int, std::string > bm_type;
bm_type bm;

The collection of relations view

Помните, что только<bm>можно использовать как набор отношений. Мы можем вставлять элементы или повторять их, используя этот вид.

bm.insert( bm_type::value_type(1, "one" ) );
bm.insert( bm_type::value_type(2, "two" ) );
std::cout << "There are " << bm.size() << "relations" << std::endl;
for( bm_type::const_iterator iter = bm.begin(), iend = bm.end();
    iter != iend; ++iter )
{
    // iter->left  : data : int
    // iter->right : data : std::string
    std::cout << iter->left << " <--> " << iter->right << std::endl;
}

The left map view

<bm.left>работает как<std::map< int,std::string >>. Мы используем его так же, как используем стандартную карту.

typedef bm_type::left_map::const_iterator left_const_iterator;
for( left_const_iterator left_iter = bm.left.begin(), iend = bm.left.end();
     left_iter != iend; ++left_iter )
{
    // left_iter->first  : key  : int
    // left_iter->second : data : std::string
    std::cout << left_iter->first << " --> " << left_iter->second << std::endl;
}
bm_type::left_const_iterator left_iter = bm.left.find(2);
assert( left_iter->second ==  "two" );
bm.left.insert( bm_type::left_value_type( 3, "three" ) );

The right map view

<bm.right>работает как<std::map< std::string,int>>. Важно отметить, что ключ — это первый тип, а данные — второй, как и в стандартных картах.

bm_type::right_const_iterator right_iter = bm.right.find("two");
// right_iter->first  : key  : std::string
// right_iter->second : data : int
assert( right_iter->second ==  2 );
assert( bm.right.at("one") == 1 );
bm.right.erase("two");
bm.right.insert( bm_type::right_value_type( "four", 4 ) );

Differences with std::map

Основное различие между представлениями бимапа и их аналогами в стандартных контейнерах заключается в том, что из-за двунаправленного характера бимапа значения, хранящиеся в нем, не могут быть изменены непосредственно с помощью итераторов. Например, когда<std::map<X,Y>>итератор удален, тип возврата<std::pair<constX, Y>>, поэтому действителен следующий код:<m.begin()->second=new_value;>. Однако отсылка к<bimap<X,Y>::left_iterator>возвращает тип, которыйсовместим с подписьюс<std::pair<constX,constY>>.

bm.left.find(1)->second = "1"; // Compilation error

Если вы вставите<(1,"one")>и<(1,"1")>в<std::map<int,std::string>>, вторая вставка не будет иметь никакого эффекта. В<bimap<X,Y>>оба ключа должны оставаться уникальными. Вставка также может потерпеть неудачу в других ситуациях. Давайте посмотрим пример

bm.clear();
bm.insert( bm_type::value_type( 1, "one" ) );
bm.insert( bm_type::value_type( 1, "1"   ) ); // No effect!
bm.insert( bm_type::value_type( 2, "one" ) ); // No effect!
assert( bm.size() == 1 );

A simple example

Посмотрите, как вы можете повторно использовать код, который предназначен для использования с std::maps, как функция print_map в этом примере.

#include <string>
#include <iostream>
#include <boost/bimap.hpp>
template< class MapType >
void print_map(const MapType & map,
               const std::string & separator,
               std::ostream & os )
{
    typedef typename MapType::const_iterator const_iterator;
    for( const_iterator i = map.begin(), iend = map.end(); i != iend; ++i )
    {
        os << i->first << separator << i->second << std::endl;
    }
}
int main()
{
    // Soccer World cup
    typedef boost::bimap< std::string, int > results_bimap;
    typedef results_bimap::value_type position;
    results_bimap results;
    results.insert( position("Argentina"    ,1) );
    results.insert( position("Spain"        ,2) );
    results.insert( position("Germany"      ,3) );
    results.insert( position("France"       ,4) );
    std::cout << "The number of countries is " << results.size()
              << std::endl;
    std::cout << "The winner is " << results.right.at(1)
              << std::endl
              << std::endl;
    std::cout << "Countries names ordered by their final position:"
              << std::endl;
    // results.right works like a std::map< int, std::string >
    print_map( results.right, ") ", std::cout );
    std::cout << std::endl
              << "Countries names ordered alphabetically along with"
                    "their final position:"
              << std::endl;
    // results.left works like a std::map< std::string, int >
    print_map( results.left, " ends in position ", std::cout );
    return 0;
}

Результатом этой программы будет следующее:

The number of countries is 4
The winner is Argentina
Countries names ordered by their final position:
1) Argentina
2) Spain
3) Germany
4) France
Countries names ordered alphabetically along with their final position:
Argentina ends in position 1
France ends in position 4
Germany ends in position 3
Spain ends in position 2

Continuing the journey

Информацию о подписях функций см. в любой стандартной библиотечной документации или в разделессылкиэтой документации.

Caution

Имейте в виду, что двунаправленная карта совместима только со стандартными контейнерами. Некоторые функции могут давать разные результаты, например, в случае вставки пары в левую карту, где второе значение конфликтует с сохраненным отношением в контейнере. Функции могут быть медленнее в бимапе из-за дублированных ограничений. Настоятельно рекомендуется читать. Полное руководство, если вы намерены использовать бимап в серьезном проекте.