bdlc_packedintarray

Detailed Description

Outline

• Purpose
• Classes
• Description
  • Usage
    • Example 1: Temperature Map

Purpose

Provide an extensible, packed array of integral values.

Classes

• bdlc::PackedIntArray: packed array of integral values
• bdlc::PackedIntArrayConstIterator: bidirectional const_iterator

Description

This component provides a space-efficient value-semantic array class template, bdlc::PackedIntArray, and an associated iterator, bdlc::PackedIntArrayConstIterator, that provides non-modifiable access to its elements. The interface of this class provides the user with functionality similar to a bsl::vector<int>. The implementation is designed to reduce dynamic memory usage by storing its contents differently according to the magnitude of values placed within it. The user need not be concerned with the internal representation of the data. The array supports primitive operations (e.g., insertion, look-up, removal) as well as a complete set of value-semantic operations; however, direct reference to individual elements is not available. Users can access the value of individual elements by calling the indexing operator or via iterators. Note that iterators are not invalidated if an array object reallocates memory.

Usage

This section illustrates intended use of this component.

Example 1: Temperature Map

There exist many applications in which the range of int data that a container will hold is not known at design time. This means in order to build a robust component one must default to bsl::vector<int>, which for many applications is excessive in its usage of space.

Suppose we are creating a map of temperatures for every city in the United States for every day. This represents a large body of data, most of which is easily representable in a signed char, and in only rare situations is a short required.

To be able to represent all possible values for all areas and times, including extremes like Death Valley, a traditional implementation would require use of a vector<short> for each day for each area. This is excessive for all but the most extreme values, and therefore wasteful for this map as a whole.

We can use bdlc::PackedIntArray to efficiently store this data.

First, we declare and define a my_Date class. This class is very similar to bdlt::Date, and therefore is elided for the sake of compactness.

                            // =======
                            // my_Date
                            // =======
class my_Date {
    // A (value-semantic) attribute class that provides a very simple date.
    signed char d_day;    // the day
    signed char d_month;  // the month
    int         d_year;   // the year
 
    // FRIENDS
    friend bool operator<(const my_Date&, const my_Date&);
 
  public:
    // CREATORS
    explicit my_Date(int         year  = 1,
                     signed char month = 1,
                     signed char day   = 1);
        // Create a 'my_Date' object having the optionally specified 'day',
        // 'month', and 'year'.  Each, if unspecified, will default to 1.
};
 
bool operator<(const my_Date& lhs, const my_Date& rhs);
    // Return 'true' if the specified 'lhs' represents an earlier date than
    // the specified 'rhs' object, and 'false' otherwise.
 
                        // -------
                        // my_Date
                        // -------
// CREATORS
inline
my_Date::my_Date(int year, signed char month , signed char day)
: d_day(day)
, d_month(month)
, d_year(year)
{
}
 
bool operator<(const my_Date& lhs, const my_Date& rhs)
{
    return 10000 * lhs.d_year + 100 * lhs.d_month + lhs.d_day <
           10000 * rhs.d_year + 100 * rhs.d_month + rhs.d_day;
}

Then, we create our temperatureMap, which is a map of dates to a map of zip codes to a PackedIntArray of temperatures. Each PackedIntArray has entries for each temperature from 12 A.M, to 11 P.M for each city in each zip code. Notice that we use a PackedIntArray to hold the data compactly.

bsl::map<my_Date, bsl::map<bsl::string, bdlc::PackedIntArray<int> > >
                                                            temperatureMap;

Next, we add data to the map (provided by the National Weather Service) for a normal case, and the extreme.

bdlc::PackedIntArray<int>& nyc
                       = temperatureMap[my_Date(2013, 9,  6)]["10023"];
bdlc::PackedIntArray<int>& dValley
                       = temperatureMap[my_Date(1913, 7, 10)]["92328"];
bdlc::PackedIntArray<int>& boston
                       = temperatureMap[my_Date(2013, 9,  6)]["02202"];
 
int nycTemperatures[24]  = { 60,  58, 57,  56,  55,  54,  54,  55,
                             56,  59, 61,  64,  66,  67,  69,  69,
                             70,  70, 68,  67,  65,  63,  61,  60};
 
int deathValleyTemps[24] = { 65,  55, 50,  47,  62,  75,  77,  89,
                             91,  92, 95, 110, 113, 121, 134, 126,
                            113,  99, 96,  84,  79,  81,  73,  69};
 
int bostonTemps[24]      = { 55,  53, 52,  51,  50,  49,  49,  50,
                             51,  54, 56,  59,  61,  62,  64,  64,
                             65,  65, 63,  62,  60,  58,  56,  55};

Then, since the size of the data set is known at design time, as well as extreme values for the areas, we can use the reserveCapacity() method to give the container hints about the data to come.

nyc.reserveCapacity    (24, 54,  70);
dValley.reserveCapacity(24, 47, 134);
boston.reserveCapacity (24, 49,  65);

Now we add the data to the respective containers.

for (bsl::size_t i= 0; i < 24; ++i) {
    nyc.append(nycTemperatures[i]);
    dValley.append(deathValleyTemps[i]);
    boston.append(bostonTemps[i]);
}

Finally, notice that in order to represent these values in a PackedIntArray, it required 24 * sizeof(signed char) bytes (24 on most systems) of dynamic memory for nyc, which represents the normal case for this data. A vector<short> would require 24 * sizeof(short) bytes (48 on most systems) of dynamic memory to represent the same data.

assert(static_cast<int>(sizeof(signed char)) == nyc.bytesPerElement());
assert(                                   24 == nyc.length());