Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

Containedness

Containedness

interval

interval
sets

interval
maps

itl::set

itl::map

void T::clear()

1

1

1

1

1

bool T::empty()const

1

1

1

1

1

bool T::contains(const P&)const

e i

e i S

e i S b p M

e s

b m

bool T::contained_in(const P&)const

i

S

M

1

1

This group of functions refers to containedness which should be fundamental to containers. The function contains is overloaded. It covers different kinds of containedness: Containedness of elements, segments, and sub containers.

Containedness

O(...)

Description

void T::clear()

O(n)

All content is removed from the container.

bool T::empty()const

O(1)

Returns true, if the container is empty, false otherwise.

bool T::contains(const P& sub)const

see below

Returns true, if *this container contains object sub.

bool T::contained_in(const P& super)const

O(m log n)

Returns true, if *this is contained in object super.

where

n = this->iterative_size()

m = super.iterative_size()

// overload tables for 
bool T::contains(const P& src)

element containers:     interval containers:  
contains| e b s m       contains| e i b p S M    
--------+--------       --------+------------    
  s     | 1   1           S     | 1 1     1       
  m     | 1 1 1 1         M     | 1 1 1 1 1 1    

The overloads of bool T::contains(const P& src) cover various kinds of containedness. We can group them into a part (1) that checks if an element, a segment or a container of same kinds is contained in an element or interval container

// (1) containedness of elements, segments or containers of same kind
contains| e b s m       contains| e i b p S M    
--------+--------       --------+------------    
  s     | 1   1           S     | 1 1     1       
  m     |   1   1         M     |     1 1   1    

and another part (2) that checks the containedness of key objects, which can be elements an intervals or a sets.

// (2) containedness of key objects.
contains| e b s m       contains| e i b p S M    
--------+--------       --------+------------    
  s     | 1   1           S     | 1 1     1       
  m     | 1   1           M     | 1 1     1      

For type m = itl::map, a key element (m::domain_type) and an itl::set (m::set_type) can be a key object.

For an interval map type M, a key element (M::domain_type), an interval (M::interval_type) and an interval set, can be key objects.

Complexity characteristics for function bool T::contains(const P& sub)const are given by the next tables where

n = this->iterative_size();
m = sub.iterative_size(); //if P is a container type

Table1.16.Time Complexity for function contains on element containers

bool T::contains(const P& sub)const

domain
type

domain
mapping
type

interval
sets

interval
maps

itl::set

O(log n)

O(m log n)

itl::map

O(log n)

O(log n)

O(m log n)

O(m log n)


Table1.17.Time Complexity for function contains on interval containers

bool T::contains(const P& sub)const

domain
type

interval
type

domain
mapping
type

interval
mapping
type

interval
sets

interval
maps

interval_sets

interval_set

O(log n)

O(log n)

O(m log n)

separate_interval_set
split_interval_set

O(log n)

O(n)

O(m log n)

interval_maps

interval_map

O(log n)

O(log n)

O(log n)

O(log n)

O(m log n)

O(m log n)

split_interval_map

O(log n)

O(n)

O(log n)

O(n)

O(m log n)

O(m log n)


All tests of containedness of containers in containers

bool T::contains(const P& sub_container)const
bool T::contained_in(const P& super_container)const

are of loglinear time: O(m log n). If both containers have same iterative_sizes so that m = n we have the worst case ( O(n log n) ). There is an alternative implementation that has a linear complexity of O(n+m). The loglinear implementation has been chosen, because it can be faster, if the container argument is small. In this case the loglinear implementation approaches logarithmic behavior, whereas the linear implementation stays linear.

Back to section . . .

Function Synopsis

Interface


PrevUpHomeNext