Boost C++ 库

……是世界上最受推崇、设计最精良的 C++ 库项目之一。 Herb SutterAndrei Alexandrescu《C++ 编码标准》

聚会 - Boost C++ 函数库
PrevUpHomeNext

示例 party 演示了区间映射 (interval_mapsplit_interval_map) 的可能性。 interval_map 将区间映射到一个给定的内容。在本例中,内容是以姓名字符串表示的聚会客人集合。

随着时间的推移,一群人加入聚会,然后在晚上离开。因此,我们为每个群体(一起来,一起走)的出席情况,向 interval_map 添加一个时间区间和一个姓名集合。在区间的所有重叠处,相应的姓名集合会被累加。在重叠点,区间会被分割。内容的累加是通过一个 += 操作符完成的,这个操作符必须为 interval_map 的内容参数实现。最后,interval_map 包含了出席的历史记录以及聚会客人分组发生变化的所有时间点。

Party 演示了一个我们称之为 重叠聚合 的原理:在插入时,与区间相关联的值会与 interval_map 中与插入值重叠的那些值进行聚合。 重叠聚合 有两个行为方面:分解行为累加行为

  • 分解行为 在 interval_map 的 时间 维度 上分割区间,以便在相关值发生变化时对区间进行分割。
  • 累加行为 在插入值与相关值重叠时,累加相关值。

聚合函数默认为 +=。如果需要,也可以使用不同的聚合函数。

// The next line includes <boost/date_time/posix_time/posix_time.hpp>
// and a few lines of adapter code.
#include <boost/icl/ptime.hpp>
#include <iostream>
#include <boost/icl/interval_map.hpp>

using namespace std;
using namespace boost::posix_time;
using namespace boost::icl;

// Type set<string> collects the names of party guests. Since std::set is
// a model of the itl's set concept, the concept provides an operator += 
// that performs a set union on overlap of intervals.
typedef std::set<string> GuestSetT;

void boost_party()
{
    GuestSetT mary_harry;
    mary_harry.insert("Mary");
    mary_harry.insert("Harry");

    GuestSetT diana_susan;
    diana_susan.insert("Diana");
    diana_susan.insert("Susan");

    GuestSetT peter;
    peter.insert("Peter");

    // A party is an interval map that maps time intervals to sets of guests
    interval_map<ptime, GuestSetT> party;

    party.add( // add and element
      make_pair(
        interval<ptime>::right_open(
          time_from_string("2008-05-20 19:30"),
          time_from_string("2008-05-20 23:00")),
        mary_harry));

    party += // element addition can also be done via operator +=
      make_pair(
        interval<ptime>::right_open(
          time_from_string("2008-05-20 20:10"),
          time_from_string("2008-05-21 00:00")),
        diana_susan);

    party +=
      make_pair(
        interval<ptime>::right_open(
          time_from_string("2008-05-20 22:15"),
          time_from_string("2008-05-21 00:30")),
        peter);


    interval_map<ptime, GuestSetT>::iterator it = party.begin();
    cout << "----- History of party guests -------------------------\n";
    while(it != party.end())
    {
        interval<ptime>::type when = it->first;
        // Who is at the party within the time interval 'when' ?
        GuestSetT who = (*it++).second;
        cout << when << ": " << who << endl;
    }

}


int main()
{
    cout << ">>Interval Container Library: Sample boost_party.cpp <<\n";
    cout << "-------------------------------------------------------\n";
    boost_party();
    return 0;
}

// Program output:
/*-----------------------------------------------------------------------------
>>Interval Container Library: Sample boost_party.cpp <<
-------------------------------------------------------
----- History of party guests -------------------------
[2008-May-20 19:30:00, 2008-May-20 20:10:00): Harry Mary
[2008-May-20 20:10:00, 2008-May-20 22:15:00): Diana Harry Mary Susan
[2008-May-20 22:15:00, 2008-May-20 23:00:00): Diana Harry Mary Peter Susan
[2008-May-20 23:00:00, 2008-May-21 00:00:00): Diana Peter Susan
[2008-May-21 00:00:00, 2008-May-21 00:30:00): Peter
-----------------------------------------------------------------------------*/

[Caution] 注意

我们引入 interval_maps,使用 区间映射 字符串集合,是因为其教学上的优势。Party 示例用于立即掌握区间映射和 重叠聚合 的基本思想。对于实际应用,不一定推荐使用 interval_map 的集合。它存在与 std::map 集合相同的效率问题。但是,使用数值和其他高效数据类型作为相关值的 interval_maps 存在广阔的应用空间。


PrevUpHomeNext