7 August 2004

Indexed containers from Boost

This month's C/C++ Users Journal came in, and it has an article describing the Boost Multi-index Containers Library. This library provides a container template that can be defined with zero or more unique and non-unique indexes. This is genius. Imagine having immediate access to separate, ordered views for your data without having to resort or, worse, provide multiple containers.

The multi_index_container<> template mimics the std::set<> template's interface with minor, necessary removals and some major enhancements. The article provided a simple example using a data structure representing an employee then created a container with three indexes:

// Define the employee structure.
struct employee
    int id;
    std::string name;
    int age;
    bool operator<(const employee& e) const
    {return id < e.id;}

// Define an indexed container called company.
using namespace boost::multi_index;
typedef multi_index_container<
        ordered_unique<identity<employee> >,
        ordered_non_unique<member<employee, std::string, &employee::name> >,
        ordered_non_unique<member<employee, int, &employee::age> >
> company;

Here, a container of employees is defined (as a company) with a unique index based on the employee class's operator < and two non-unique indexes based on name and age. What this container gives us is a mechanism that can define data tables almost as elegantly as SQL. Compare to an equivalent SQL statement:

/* Define an employee and company table. */
CREATE TABLE company (
    id INT,
    name CHAR(50),
    age INT);

/* Define indexes. */
CREATE INDEX ON company (name ASC);
CREATE INDEX ON company (age ASC);

The multi-index container provides a container interface for each of the indexes through get<>() member template functions. The container itself will automatically act as a container for the first index defined, so the get<>() function can be elided for the most common access. This makes it almost seamlessly interchangeable with std::set<>.

// Print all emplyees, sorted by name, to the standard output stream.
company cmp;

There are many more benefits:

  • Create unordered, sequenced indices based on std::list<>,
  • Replace unique elements in one call without invalidating iterators,
  • Query using index values and not container elements (as with std::set<>::find()),
  • Provide alternate comparison functions when specifying indexes

Pretty neat.

Boost finally has the multi-index container documentation up along with a few other libraries hinted at in the next version. The main site lists version 1.3?.?, so I'll assume I caught them in mid-update. Currently dead link to a String Algorithms Library. I'll have to check that out when it's available.

[ posted by sstrader on 7 August 2004 at 1:43:52 PM in Programming ]