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<
employee,
indexed_by<
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 UNIQUE INDEX ON company (id ASC);
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;
std::copy(
cmp.get<1>().begin(),
cmp.get<1>().end(),
std::osream_iterator<employee>(std::cout));
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.
- Techniques after using Swift for a month posted by sstrader on 26 August 2015 at 11:41:51 PM
- Some thoughts on Ruby after finishing a week (minus one day) of training posted by sstrader on 15 December 2011 at 8:59:30 PM
- Links on the singleton pattern posted by sstrader on 9 December 2011 at 9:19:50 AM
- Phonebot posted by sstrader on 29 October 2011 at 6:37:05 PM
- The labeled break in Java posted by sstrader on 4 September 2011 at 11:27:56 AM