# Boost.MultiIndex Compiler specifics

Key extraction
Index
Performance

Boost.MultiIndex has been tried in different compilers, with various degrees of success. We list the limitations encountered, along with suitable workarounds when available.

## Contents

- Borland C++ Builder 6.4 and later
- Comeau C/C++ 4.3.3 for Windows (VC++ 7.0/7.1 backend)
- Compaq C++ 6.5-042 for Tru64 UNIX and later
- GNU GCC 3.2 and later
  - GNU GCC for Tru64 UNIX
  - Darwin GCC 4.0
- HP aC++ A.06.12 for HP-UX
- IBM VisualAge C++ V6.0 for AIX
- Intel C++ Compiler for Linux 9.0 and later
- Intel C++ Compiler for Windows 32-bit 7.0/7.1
- Intel C++ Compiler for Windows 32-bit 8.0 and later
- Intel C++ Compiler Extended Memory 64 Technology 9.1 for Windows
- Metrowerks CodeWarrior 8.3
- Metrowerks CodeWarrior 9 and later
- Microsoft Visual C++ 6.0 Service Pack 5
  - Microsoft Visual C++ 6.0 Service Pack 5 + STLport 4.5.3 and later
- Microsoft Visual C++ 7.0
  - Microsoft Visual C++ 7.0 + STLport 5.0.1
- Microsoft Visual C++ 7.1
  - Microsoft Visual C++ 7.1 + STLport 4.6.2
- Microsoft Visual C++ 8.0
  - Microsoft Visual C++ 8.0 + STLport 5.0.1
- Microsoft Visual C++ 8.0 x64 cross-compiler
- Sun Studio 11 for Solaris
- Portability techniques
  - Use of `member_offset`
  - Use of `const_mem_fun_explicit` and `mem_fun_explicit`
  - `composite_key` in compilers without partial template specialization
  - Reduction of symbol name lengths
    - Limitation of maximum number of arguments
    - Type hiding

## Borland C++ Builder 6.4 and later

Currently, Boost.MultiIndex cannot be used with any of BCB 6.4 up to BCB 2006. The number of problems encountered during the tests makes it unlikely that future versions of the library can be made to work under these compilers.

## Comeau C/C++ 4.3.3 for Windows (VC++ 7.0/7.1 backend)

No problems have been detected with this compiler. The library fails to compile, however, when Microsoft Visual C++ 6.0 is used as the backend.

## Compaq C++ 6.5-042 for Tru64 UNIX and later

No problems have been detected with this compiler. Versions 6.5-042, 7.1-005 and 7.1-006 have been tested.

## GNU GCC 3.2 and later

No problems have been detected with several versions of this compiler starting from 3.2. The following versions have been explicitly tested:

- GCC 3.2 20020927 (prerelease) under Cygwin 1.5.7,
- GCC 3.2.3 under Linux,
- GCC 3.3.5 (qnx-nto) under QNX 6.3.0 and QNX 6.3.2,
- GCC 3.3.6 under Linux,
- GCC 3.4.2 (mingw-special) under Win32, (mingw-special) + STLport 5.0.1 under Win32,
- GCC 3.4.3 under Solaris,
- GCC 3.4.4 under Linux and Tru64 (see below),
- GCC 3.4.5 under Linux and Linux x86-64, (mingw-special) under Win32, (mingw-special) + STLport 5.0.1 under Win32, (mingw-special) + STLport 5.1.0 under Win32,
- GCC 4.0.1 (Apple build 5250) under Mac OS,
- GCC 4.0.3 under Linux and Tru64 (see below),
- GCC 4.1.0 under Linux and Linux x86-64,
- GCC 4.1.1 (OpenPKG-2-STABLE) under Solaris.

Boost.MultiIndex does not work with versions 3.1 and prior of GCC.

### GNU GCC for Tru64 UNIX

On this platform, GCC is not able to handle debug symbol names whose length exceeds 32,768 bytes, resulting in the error `mips-tfile, ... string too big`. You may encounter this issue with heavily templatized code like Boost.MultiIndex, which typically produces long symbol names. The problem can be overcome by omitting the compiler option `-g` (generate debugging information.) Alternatively, consult the section on reduction of symbol name lengths for various applicable workarounds.

### Darwin GCC 4.0

Build 4061 of GCC 4.0, shipped with Darwin 8.2 and prior (Mac OS X 10.4.2 and prior), corresponds to a prerelease version of GNU GCC 4.0.0 which introduces a regression bug related to binding of references to temporary objects. This bug precludes the usage of Boost.MultiIndex invariant-checking mode; other than this, Boost.MultiIndex works correctly. The bug is corrected in GCC 4.0 Apple build 5026, which is in sync with the official release of GNU GCC 4.0.0, so the invariant-checking mode is available from this upgrade.

## HP aC++ A.06.12 for HP-UX

No problems have been detected with this compiler.

## IBM VisualAge C++ V6.0 for AIX

Note: This information was last checked for Boost 1.33.1. There is a possibility that changes in Boost since that release have caused problems with this platform.

`member` not supported, refer to the section on use of `member_offset` for workarounds. `member_offset` causes the compiler to emit warnings about the use of `offsetof` with non-POD types: these warnings can be suppressed by setting the compiler option `-qsuppress=1540-1281`, or, alternatively, by inserting the following preprocessor directive:

>     #pragma info(nolan)

This latter pragma, however, may also eliminate other warnings not related to the use of `offsetof`.

Serialization capabilities are not available as Boost.Serialization is not supported on this platform.

## Intel C++ Compiler for Linux 9.0 and later

No problems have been detected with this compilers from version 9.0.

## Intel C++ Compiler for Windows 32-bit 7.0/7.1

`member` not supported, refer to the section on use of `member_offset` for workarounds.

When used on top of MSVC++ 7.0 or prior, argument dependent lookup is disabled by default. This will cause problems with many Boost libraries, and in particular with the serialization part of Boost.MultiIndex. Argument dependent lookup is enabled by adding `/Qoption,c,--arg_dep_lookup` to the project options.

## Intel C++ Compiler for Windows 32-bit 8.0 and later

When used on top of MSVC++ 7.0 or prior, argument dependent lookup is disabled by default. This will cause problems with many Boost libraries, and in particular with the serialization part of Boost.MultiIndex. Argument dependent lookup is enabled by adding `/Qoption,c,--arg_dep_lookup` to the project options. Other than this, Boost.MultiIndex works without problems. Compiler versions from 8.0 to 9.1 have been tested.

## Intel C++ Compiler Extended Memory 64 Technology 9.1 for Windows

No problems have been detected with this compiler.

## Metrowerks CodeWarrior 8.3

Predefined key extractors instantiated on a given type do not accept objects of derived types. For instance:

>     struct base{};
>     struct derived:public base{};
>     ...

>     identity<base> key_extractor;
>     derived        x;

>     // not accepted by this compiler: an explicit cast to base is required
>     key_extractor(x);

Other than this, Boost.MultiIndex works without problems under the two operating systems tested: Mac OS and Windows.

## Metrowerks CodeWarrior 9 and later

Boost.MultiIndex works correctly with versions of this compiler from 9.0 to 9.5, under the two operating systems tested: Mac OS and Windows.

## Microsoft Visual C++ 6.0 Service Pack 5

`member` not supported, refer to the section on use of `member_offset` for workarounds.

`const_mem_fun` and `mem_fun` not supported, refer to the section on use of `const_mem_fun_explicit` and `mem_fun_explicit` for workarounds.

No support for index retrieval and projection nested types and member functions:

- `nth_index`,
- `index`,
- `nth_index_iterator`,
- `nth_index_const_iterator`,
- `index_iterator`,
- `index_const_iterator`,
- `get`,
- `project`.

You can use instead their global equivalents. Also, this compiler does not implement argument dependent lookup, so you might need to explicitly qualify these global names with `::boost::multi_index`.

`boost::multi_index::multi_index_container` is imported to `namespace boost` by means of a `using` declaration. MSVC++ 6.0, however, does not properly handle this import. So, instead of writing:

>     boost::multi_index_container<...>

use the following:

>     boost::multi_index::multi_index_container<...>

or else resort to a directive `using namespace boost::multi_index`.

The lack of partial template specialization support in MSVC++ 6.0 results in some inconveniences when using `composite_key` that can be remedied as explained in "`composite_key` in compilers without partial template specialization".

Due to problems with function template ordering support, `composite_key_compare` and related classes do not accept the notational variations of `operator()` where one of the operands is treated as if included into a tuple of length 1. As a result, the user cannot ever omit tuple enclosing when specifying the arguments of lookup operations involving composite keys.

Predefined key extractors instantiated on a given type do not accept objects of derived types. For instance:

>     struct base{};
>     struct derived:public base{};
>     ...

>     identity<base> key_extractor;
>     derived        x;

>     // not accepted by this compiler: an explicit cast to base is required
>     key_extractor(x);

MSVC++ 6.0 presents serious limitations for the maximum length of symbol names generated by the compiler, which might result in the linker error `LNK1179: invalid or corrupt file: duplicate comdat comdat`. To overcome this problem, consult the section on reduction of symbol name lengths for various applicable workarounds.

Under some circumstances, the compiler emits the error `C2587``: '_U' : illegal use of local variable as default parameter`, inside the MSVC internal header `<xlocnum>`. This problem is a recurrent bug of the compiler, and has been reported in other unrelated libraries, like the Boost Graph Library, Boost.MultiArray, Boost.Regex, CGAL and MySQL++. The error is triggered, though not in a systematic manner, by the use of `multi_index_container` iterator constructor. Two workarounds exist: the first consists of avoiding this constructor and replacing code like:

>     multi_index_container<...> s(c.begin(),c.end());

with equivalent operations:

>     multi_index_container<...> s;
>     s.insert(c.begin(),c.end());

The second workaround has not been confirmed by the author, but it is given on the Internet in connection with this error appearing in other libraries. Replace line 84 of `<xlocnum>`

>      #define _VIRTUAL	virtual

with the following:

>      #define _VIRTUAL

Warning: it is not known whether this replacement can result in unexpected side effects in code implicitly using `<xlocnum>`.

In general, the extensive use of templates by Boost.MultiIndex puts this compiler under severe stress, so that several internal limitations may be reached. The following measures can help alleviate these problems:

- Set the compiler option `/Zm` (Specify Memory Allocation Limit) to increase the amount of memory available for compilation. Usual values for this option range from 300 to 800.
- If in debug mode, try switching from `/ZI` (Program Database for Edit and Continue) to a less demanding type of debugging information (`/Zi`, `/Z7` or `/Zd`.)
- Play with the precompiled headers options. Usually, turning this feature off yields the best results.
- If the compiler emits the error `C1055``: compiler limit : out of keys`, try disabling the option `/Gm` (Enable Minimal Rebuild.) In these cases, it is also beneficial to split the project into smaller subprojects.

### Microsoft Visual C++ 6.0 Service Pack 5 + STLport 4.5.3 and later

Boost.MultiIndex works for this configuration. The same limitations apply as in MSVC++ 6.0 with its original Dinkumware standard library. STLport 4.6.2 and 5.0.1 has also been confirmed to work correctly.

It is not possible to use the serialization capabilities of Boost.MultiIndex along with the dynamic version of STLport, as some linking errors result. Use instead the static version of STLport. This bug is fixed in STLport 5.0.

## Microsoft Visual C++ 7.0

`member` not supported, refer to the section on use of `member_offset` for workarounds.

No support for index retrieval and projection nested types and member functions:

- `nth_index`,
- `index`,
- `nth_index_iterator`,
- `nth_index_const_iterator`,
- `index_iterator`,
- `index_const_iterator`,
- `get`,
- `project`.

You can use instead their global equivalents. Also, this compiler does not implement argument dependent lookup, so you might need to explicitly qualify these global names with `::boost::multi_index`.

`boost::multi_index::multi_index_container` is imported to `namespace boost` by means of a `using` declaration. MSVC++ 7.0, however, does not properly handle this import. So, instead of writing:

>     boost::multi_index_container<...>

use the following:

>     boost::multi_index::multi_index_container<...>

or else resort to a directive `using namespace boost::multi_index`.

The lack of partial template specialization support in MSVC++ 7.0 results in some inconveniences when using `composite_key` that can be remedied as explained in "`composite_key` in compilers without partial template specialization".

Due to problems with function template ordering support, `composite_key_compare` and related classes do not accept the notational variations of `operator()` where one of the operands is treated as if included into a tuple of length 1. As a result, the user cannot ever omit tuple enclosing when specifying the arguments of lookup operations involving composite keys.

Predefined key extractors instantiated on a given type do not accept objects of derived types. For instance:

>     struct base{};
>     struct derived:public base{};
>     ...

>     identity<base> key_extractor;
>     derived        x;

>     // not accepted by this compiler: an explicit cast to base is required
>     key_extractor(x);

### Microsoft Visual C++ 7.0 + STLport 5.0.1

Boost.MultiIndex works for this configuration. The same issues apply as in MSVC++ 7.0 with its original Dinkumware standard library.

## Microsoft Visual C++ 7.1

Problems have been reported when compiling the library with the `/Gm` option (Enable Minimal Rebuild.) Seemingly, this is due to an internal defect of the compiler (see for instance this mention of a similar issue in the Boost Users mailing list.) If `/Gm` is turned off, Boost.MultiIndex compiles and runs without further problems.

### Microsoft Visual C++ 7.1 + STLport 4.6.2

Boost.MultiIndex works for this configuration. The same issues apply as in MSVC++ 7.1 with its original Dinkumware standard library.

## Microsoft Visual C++ 8.0

No problems have been detected with this compiler.

### Microsoft Visual C++ 8.0 + STLport 5.0.1

No problems have been detected with this configuration.

## Microsoft Visual C++ 8.0 x64 cross-compiler

No problems have been detected with this compiler.

## Sun Studio 11 for Solaris

No problems have been detected with this platform. The exact compiler version tested was Sun C++ 5.8 Patch 121017-03 2006/07/19. The option `-library=stlport4` was used to replace the default standard library with STLport.

## Portability techniques

### Use of `member_offset`

The `member` key extractor poses some problems in compilers that do not properly support pointers to members as non-type template arguments, as indicated by the Boost Configuration Library defect macro `BOOST_NO_POINTER_TO_MEMBER_TEMPLATE_PARAMETERS`. The following compilers have been confirmed not to work correctly with `member`:

- MSVC++ 6.0/7.0,
- Intel C++ 7.0/7.1 for Windows,
- VisualAge 6.0 for AIX.

This program can help determine if your compiler properly supports pointers to members as non-type template parameters:

>     #include <iostream>

>     struct pair
>     {
>       int x,y;

>       pair(int x_,int y_):x(x_),y(y_){}
>     };

>     template<int pair::* PtrToPairMember>
>     struct foo
>     {
>       int bar(pair& p){return p.*PtrToPairMember;}
>     };

>     int main()
>     {
>       pair p(0,1);
>       foo<&pair::x> fx;
>       foo<&pair::y> fy;

>       if(fx.bar(p)!=0||fy.bar(p)!=1)std::cout<<"KO"<<std::endl;
>       else std::cout<<"OK"<<std::endl;

>       return 0;
>     }

If you find a compiler that does not pass the test, and for which `BOOST_NO_POINTER_TO_MEMBER_TEMPLATE_PARAMETERS` is not defined, please report to the Boost developers mailing list.

To overcome this defect, a replacement utility `member_offset` has been provided that does the work of `member` at the expense of less convenient notation and the possibility of non-conformance with the standard. Please consult the reference for further information on `member_offset`. As an example of use, given the class

>     class A
>     {
>       int x;
>     }

the instantiation `member<A,int,&A::x>` can be simulated then as `member_offset<A,int,offsetof(A,x)>`.

For those writing portable code, Boost.MultiIndex provides the ternary macro `BOOST_MULTI_INDEX_MEMBER`. Continuing with the example above, the expression

>     BOOST_MULTI_INDEX_MEMBER(A,int,x)

expands by default to

>     member<A,int,&A::x>

or alternatively to

>     member_offset<A,int,offsetof(A,x)>

if `BOOST_NO_POINTER_TO_MEMBER_TEMPLATE_PARAMETERS` is defined.

### Use of `const_mem_fun_explicit` and `mem_fun_explicit`

MSVC++ 6.0 has problems with `const` member functions as non-type template parameters, and thus does not accept the `const_mem_fun` key extractor. A simple workaround, fortunately, has been found, consisting in specifying the type of these pointers as an additional template parameter. The alternative `const_mem_fun_explicit` extractor adopts this solution; for instance, given the type

>     struct A
>     {
>       int f()const;
>     };

the extractor `const_mem_fun<A,int,&A::f>` can be replaced by `const_mem_fun_explicit<A,int,int (A::*)()const,&A::f>`. A similar `mem_fun_explicit` class template is provided for non-constant member functions.

If you are writing cross-platform code, the selection of either key extractor is transparently handled by the macro `BOOST_MULTI_INDEX_CONST_MEM_FUN`, so that

>     BOOST_MULTI_INDEX_CONST_MEM_FUN(A,int,f)

expands by default to

>     const_mem_fun<A,int,&A::f>

but resolves to

>     const_mem_fun_explicit<A,int,int (A::*)()const,&A::f>

in MSVC++ 6.0. Non-`const` member functions are covered by `mem_fun_explicit` and the macro `BOOST_MULTI_INDEX_MEM_FUN`.

### `composite_key` in compilers without partial template specialization

When using `composite_key`s, lookup is performed by passing tuples of values: this ability is achieved by suitably specializing the class templates `std::equal_to`, `std::less`, `std::greater` and `boost::hash` for `composite_key_result` instantiations so that they provide the appropriate overloads accepting tuples --and in the case of `std::less` and `std::greater`, also partial tuples where only the first components are specified.

In those compilers that do not support partial template specialization, these specializations cannot be provided, and so tuple-based lookup is not available by default. In this case, `multi_index_container` instantiations using composite keys will work as expected, both for ordered and hashed indices, except that lookup operations will not accept tuples as an argument. For ordered indices, the most obvious workaround to this deficiency involves explicitly specifying the comparison predicate with `composite_key_compare`; in the case of hashed indices we can use the analogous `composite_key_equal_to` and `composite_key_hash`. This substitution is tedious as the elementary components for all the constituent key extractors must be explicitly typed. For this reason, Boost.MultiIndex provides the following replacement class templates

- `composite_key_result_equal_to`,
- `composite_key_result_less`,
- `composite_key_result_greater` and
- `composite_key_result_hash`,

that act as the missing specializations of `std::equal_to`, `std::less`, `std::greater` and `boost::hash` for `composite_key_result`s. They can be used as follows:

>     typedef composite_key<
>       phonebook_entry,
>       member<phonebook_entry,std::string,&phonebook_entry::family_name>,
>       member<phonebook_entry,std::string,&phonebook_entry::given_name>
>     > ckey_t;

>     typedef multi_index_container<
>       phonebook_entry,
>       indexed_by<
>         ordered_non_unique<
>           ckey_t,
>           // composite_key_result_less plays the role of
>           // std::less<ckey_t::result_type>
>           composite_key_result_less<ckey_t::result_type>
>         >,
>         ordered_unique<
>           member<phonebook_entry,std::string,&phonebook_entry::phone_number>
>         >
>       >
>     > phonebook;

### Reduction of symbol name lengths

The types generated on the instantiations of `multi_index_container`s typically produce very long symbol names, sometimes beyond the internal limits of some compilers. There are several techniques to shorten generated symbol names: these techniques have also the beneficial side effect that resulting error messages are more readable.

#### Limitation of maximum number of arguments

The class templates `indexed_by`, `tag` and `composite_key` accept a variable number of arguments whose maximum number is limited by internal macros. Even non-used arguments contribute to the final types, so manually adjusting the corresponding macros can result in a modest reduction of symbol names.

Limiting maximum number of arguments of some class templates of Boost.MultiIndex.
class template | limiting macro | default value | default value (MSVC++ 6.0)
--- | --- | --- | ---
`indexed_by` | `BOOST_MULTI_INDEX_LIMIT_INDEXED_BY_SIZE` | 20 | 5
`tag` | `BOOST_MULTI_INDEX_LIMIT_TAG_SIZE` | 20 | 3
`composite_key` | `BOOST_MULTI_INDEX_LIMIT_COMPOSITE_KEY_SIZE` | 10 | 5

#### Type hiding

Consider a typical instantiation of `multi_index_container`:

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

Then, for instance, the type `employee_set::nth_type<0>::type` resolves to the following in GCC:

>     boost::multi_index::detail::ordered_index<
>       boost::multi_index::identity<employee>,
>       std::less<employee>,
>       boost::multi_index::detail::nth_layer<
>         1, employee,
>         boost::multi_index::indexed_by<
>           boost::multi_index::ordered_unique<
>             boost::multi_index::identity<employee>, mpl_::na, mpl_::na
>           >,
>           boost::multi_index::ordered_non_unique<
>             boost::multi_index::member<employee, std::string, &employee::name>,
>             mpl_::na, mpl_::na
>           >,
>           boost::multi_index::ordered_unique<
>             boost::multi_index::member<employee, int, &employee::ssnumber>,
>             mpl_::na, mpl_::na
>           >,
>           mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na,
>           mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na,
>           mpl_::na, mpl_::na, mpl_::na, mpl_::na, mpl_::na
>         >,
>         std::allocator<employee>
>       >,
>       boost::mpl::vector0<mpl_::na>,
>       boost::multi_index::detail::ordered_unique_tag
>     >

It can be seen that a significant portion of the type name is contributed by the `indexed_by<...>` part, which is nothing but an expanded version of the index specifier list provided in the definition of `employee_set`. We can prevent this very long name from appearing in the final type by encapsulating it into another, shorter-named construct:

>     // reducing symbol names through type hiding
>     // type hide the index spexifier list within employee_set_indices

>     struct employee_set_indices:
>       indexed_by<
>         ordered_unique<identity<employee> >,
>         ordered_non_unique<member<employee,std::string,&employee::name> >,
>         ordered_unique<member<employee,int,&employee::ssnumber> >
>       >
>     {};

>     typedef multi_index_container<
>       employee,
>       employee_set_indices
>     > employee_set;

`employee_set_indices` works as a conventional `typedef` in all respects, save for a detail: its name does not explicitly include the information contained in the `indexed_by` instantiation. Applying this technique, `employee_set::nth_type<0>::type` now becomes:

>     boost::multi_index::detail::ordered_index<
>       boost::multi_index::identity<employee>,
>       std::less<employee>,
>       boost::multi_index::detail::nth_layer<
>         1, employee,
>         employee_set_indices,
>         std::allocator<employee>
>       >,
>       boost::mpl::vector0<mpl_::na>,
>       boost::multi_index::detail::ordered_unique_tag
>     >

which is considerably shorter than the original, and also more easily parsed by a human reader. Type hiding would not work if, instead of making `employee_set_indices` a derived `struct` of `indexed_by<...>`, we had defined it as a `typedef`: `typedef`s are syntactic aliases and usually get expanded by the compiler before doing any further type handling.

Type hiding techniques can also be applied to `composite_key` intantiations, which often contribute a great deal to symbol name lengths.

Key extraction
Index
Performance

Revised October 16th 2006

© Copyright 2003-2006 Joaquín M López Muñoz. Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)