Boost C++ Libraries

...one of the most highly regarded and expertly designed C++ library projects in the world. Herb Sutter and Andrei Alexandrescu, C++ Coding Standards

Click here to view the latest version of this page.
PrevUpHomeNext

Sets and Maps

A Set Concept

On the fundamental aspect all interval_sets are models of a concept Set. The Set concept of the Interval Template Library refers to the mathematical notion of a set.

Function

Variant

implemented as

empty set

Set::Set()

subset relation

bool Set::within(const Set& s1, const Set& s2)const

equality

bool is_element_equal(const Set& s1, const Set& s2)

set union

inplace

Set& operator += (Set& s1, const Set& s2)

Set operator + (const Set& s1, const Set& s2)

set difference

inplace

Set& operator -= (Set& s1, const Set& s2)

Set operator - (const Set& s1, const Set& s2)

set intersection

inplace

Set& operator &= (Set& s1, const Set& s2)

Set operator & (const Set& s1, const Set& s2)

Equality on Sets is not implemented as operator ==, because operator == is used for the stronger lexicographical equality on segments, that takes the segmentation of elements into account.

Being models of concept Set, std::set and all interval_sets implement these operations and obey the associated laws on Sets. See e.g. an algebra of sets here.

Making intervals complete

An interval is considered to be a set of elements as well. With respect to the Set concept presented above interval implements the concept only partially. The reason for that is that addition and subtraction can not be defined on intervals. Two intervals [1,2] and [4,5] are not addable to a single new interval. In other words intervals are incomplete w.r.t. union and difference. Interval_sets can be defined as the completion of intervals for the union and difference operations.

When we claim that addition or subtraction can not be defined on intervals, we are not considering things like e.g. interval arithmetics, where these operations can be defined, but with a different semantics.

A Map Concept

On the fundamental aspect icl::map and all interval_maps are models of a concept Map. Since a map is a set of pairs, we try to design the Map concept in accordance to the Set concept above.

Function

Variant

implemented as

empty map

Map::Map()

subset relation

bool within(const Map& s2, const Map& s2)const

equality

bool is_element_equal(const Map& s1, const Map& s2)

map union

inplace

Map& operator += (Map& s1, const Map& s2)

Map operator + (const Map& s1, const Map& s2)

map difference

inplace

Map& operator -= (Map& s1, const Map& s2)

Map operator - (const Map& s1, const Map& s2)

map intersection

inplace

Map& operator &= (Map& s1, const Map& s2)

Map operator & (const Map& s1, const Map& s2)

As one can see, on the abstract kernel the signatures of the icl's Set and Map concepts are identical, except for the typename. While signatures are identical The sets of valid laws are different, which will be described in more detail in the sections on the semantics of icl Sets and Maps. These semantic differences are mainly based on the implementation of the pivotal member functions add and subtract for elements and intervals that again serve for implementing operator += and operator -=.


PrevUpHomeNext