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

PrevUpHomeNext

Insertion

Synopsis
Insertion
Setting values

Insertion

interval
sets

interval
maps

element
sets

element
maps

V T::insert(const P&)

e i

b p

e

b

V insert(T&, const P&)

e i

b p

e

b

J T::insert(J pos, const P&)

i

p

e

b

J insert(T&, J pos, const P&)

i

p

e

b

T& insert(T&, const P&)

e i S

b p M

e s

b m

T& T::set(const P&)

b p

1

T& set_at(T&, const P&)

b p

1

Insertion

The effects of insertion implemented by insert and addition implemented by add and operator += are identical for all Set-types of the icl.

For Map-types, insert provides the stl semantics of insertion in contrast to add and operator +=, that implement a generalized addition, that performs aggregations if key values collide or key intervals overlap. insert on Maps does not alter a maps content at the points, where the keys of the object to inserted overlap or collide with keys that are already in the map.

Setting values

Overwriting values using operator[] like in

my_map[key] = new_value;

is not provided for interval_maps because an operator[] is not implemented for them. As a substitute a function T& T::set(const P&) can be used to achieve the same effect:

my_map.set(make_pair(overwrite_this, new_value));

// overload table for functions      T\P| e i b p  
V T::insert(const P&)                ---+--------
V insert(T&, const P&)                s | s
                                      m |     m
                                      S |   S      
                                      M |       M  

Table 1.27. Time Complexity for member function insert on icl containers

T& T::insert(const P&)

domain
type

interval
type

domain
mapping
type

interval
mapping
type

std::set

O(log n)

icl::map

O(log n)

interval_set
separate_interval_set

O(log n)

amortized
O(log n)

split_interval_set

O(log n)

O(n)

interval_map
split_interval_map

O(log n)

O(n)


// overload tables for function      element containers:     interval containers:  
T& insert(T&, const P&)              T\P| e b s m            T\P| e i b p S M 
                                     ---+--------            ---+------------ 
                                      s | s   s               S | S S     S   
                                      m |   m   m             M |     M M   M    

Table 1.28. Time Complexity for inplace insertion on element containers

T& insert(T& y, const P& x)

domain
type

domain
mapping
type

interval
sets

interval
maps

std::set

O(log n)

O(m)

icl::map

O(log n)

O(m)


Time complexity characteristics of inplace insertion for interval containers is given by this table.

Table 1.29. Time Complexity for inplace insertion on interval containers

T& insert(T& y, const P& x)

domain
type

interval
type

domain
mapping
type

interval
mapping
type

interval
sets

interval
maps

interval_sets

interval_set
separate_interval_set

O(log n)

amortized
O(log n)

O(m log(n+m))

split_interval_set

O(log n)

O(n)

O(m log(n+m))

interval_maps

O(log n)

O(n)

O(m log(n+m))


Hinted insertion

Function J T::insert(J prior, const P& addend) allows for an insertion in constant time, if addend can be inserted right after iterator prior without collision. If this is not possible the complexity characteristics are as stated for the non hinted insertion above. Hinted insertion is available for these combinations of types:

// overload table for insertion with hint        T\P| e i b p  
J T::insert(J pos, const P&)                     ---+--------
J insert(T&, J pos, const P&)                     s | s
                                                  m |     m
                                                  S |   S     
                                                  M |       M 

// overload table for member function         T\P| b p 
T& T::set(const P&)                           ---+---- 
T& set_at(T&, const P&)                        m | m   
                                               M |   M 

Table 1.30. Time Complexity for member function `set`

T& set(T&, const P&)

domain_mapping_type

interval_mapping_type

icl::map

O(log n)

interval_maps

amortized
O(log n)


See also . . .

Erasure

Addition

Back to section . . .

Function Synopsis

Interface


PrevUpHomeNext