Boost logo

Boost Users :

Subject: Re: [Boost-users] multi-index:Q - Space and time efficiency
From: joaquin_at_[hidden]
Date: 2009-03-27 03:31:44

dhruva escribió:
> Hi,
> I have a struct with 2 members as follows:
> typedef struct time_series {
> time_t _time;
> double _value;
> } time_series_t;
> The data I get is sorted by time as it is a time series. I would like to maintain another index sorted by value. Since I need to keep removing the oldest records, I need the time based order and since I need to compute percentile, I need to sort it based on value. Would using multi-index save space (and time in insertion and removal) compared to having 2 vectors with different sort order?

The space taken per element by the Boost.MultiIndex-based solution
would be:


where p is the size of a pointer, 4 bytes in a typical 32-bit architecture.
(See for

As for having two vectors, one with the time_series_t objects
themselves, the
second with pointers to the elements of the first one, the space per
element is


where c is the capacity() to size() ratio for the vectors, which
oscillates (unless
explicitly controlled by the user) between 1 and some lib-specific upper
bound (2 or 1.5 in most cases). So, if we have for instance

  p=4, sizeof(time_series_t)=16, c=1.25

that would yield 40 bytes per element for scenario 1 and 25 bytes per
for scenario 2. Your mileage may vary depending on your particular

As for speed, this much depends on your usage patterns: how often you
sort the vectors, prune them, etc. In particular, take into account that
removing elements from a position in a vector other than the tail is
expensive, which might lead you to use (the more space-consuming)
std::queues instead. I guess your best option is to prototype both scenarios
and profile them.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at