Main Page | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members | File Members
datastructures » vector

set_difference.hpp File Reference

#include "common/debug.hpp"

Include dependency graph for set_difference.hpp:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Defines

#define __SET_DIFFERENCE__   t

Functions

template<class InputIterator1, class InputIterator2, class OutputIterator>
void set_difference_fast (InputIterator1 &xiter, const InputIterator1 &xend, InputIterator2 &yiter, const InputIterator2 &yend, OutputIterator &resultIter)
 Compute set difference of two vectors interpreted as ascending sorted lists of values, represented by input iterators.
template<class InputIterator1, class InputIterator2, class OutputIterator>
bool set_difference_upper_size_bound (InputIterator1 &xiter, const InputIterator1 &xend, InputIterator2 &yiter, const InputIterator2 &yend, OutputIterator &resultIter, const int upperSizeBound)
 Compute set difference of two vectors interpreted as ascending sorted lists of values, represented by input iterators.
template<class InputIterator1, class InputIterator2, class OutputIterator>
bool set_difference_lower_size_bound (InputIterator1 &xiter, InputIterator1 &xend, InputIterator2 &yiter, const InputIterator2 &yend, OutputIterator &resultIter, const int lowerSizeBound)
 Compute set difference of two vectors interpreted as ascending sorted lists of values, represented by input iterators.
template<class InputIterator1, class InputIterator2>
int size_of_set_difference (InputIterator1 &xiter, const InputIterator1 &xend, InputIterator2 &yiter, const InputIterator2 &yend)
 Compute the size of the set difference of two vectors interpreted as ascending sorted lists of values, represented by input iterators.
template<class InputIterator1, class InputIterator2>
int size_of_set_difference_upper_size_bound (InputIterator1 &xiter, const InputIterator1 &xend, InputIterator2 &yiter, const InputIterator2 &yend, int upperSizeBound)
 Compute the size of the set difference of two vectors interpreted as ascending sorted lists of values, represented by input iterators.
template<class InputIterator1, class InputIterator2>
int size_of_set_difference_lower_size_bound (InputIterator1 &xiter, InputIterator1 &xend, InputIterator2 &yiter, const InputIterator2 &yend, const int lowerSizeBound)
 Compute the isze of the set difference of two vectors interpreted as ascending sorted lists of values, represented by input iterators.
template<class InputContainer1, class InputContainer2, class OutputContainer>
void set_difference (const InputContainer1 &x, const InputContainer2 &y, OutputContainer &result)
 Compute set difference of two containers interpreted as ascending sorted lists of values, i.e.
template<class InputContainer1, class InputContainer2, class OutputContainer>
bool set_difference_upper_size_bound (const InputContainer1 &x, const InputContainer2 &y, OutputContainer &result, const int upperSizeBound)
 Compute set difference of two containers interpreted as ascending sorted lists of values, i.e.
template<class InputContainer1, class InputContainer2, class OutputContainer>
bool set_difference_lower_size_bound (const InputContainer1 &x, const InputContainer2 &y, OutputContainer &result, const int lowerSizeBound)
 Compute set difference of two containers interpreted as ascending sorted lists of values, i.e.
template<class InputContainer1, class InputContainer2>
int size_of_set_difference (const InputContainer1 &x, const InputContainer2 &y)
 Compute the size of the set difference of two containers interpreted as ascending sorted lists of values, i.e.
template<class InputContainer1, class InputContainer2>
int size_of_set_difference_upper_size_bound (const InputContainer1 &x, const InputContainer2 &y, const int upperSizeBound)
 Compute the size of the set difference of two containers interpreted as ascending sorted lists of values, i.e.
template<class InputContainer1, class InputContainer2>
int size_of_set_difference_lower_size_bound (const InputContainer1 &x, const InputContainer2 &y, const int lowerSizeBound)
 Compute the size of the set difference of two containers interpreted as ascending sorted lists of values, i.e.

Define Documentation

#define __SET_DIFFERENCE__   t
 

Definition at line 9 of file set_difference.hpp.

Function Documentation

template<class InputContainer1, class InputContainer2, class OutputContainer>
void set_difference (  const InputContainer1 &  x,
const InputContainer2 &  y,
OutputContainer &  result
)  [inline]
 

Compute set difference of two containers interpreted as ascending sorted lists of values, i.e.

, compute $x \setminus y$ .

Parameters:
x container to subtract from. REQ: x.size() > 0 and sorted in ascending order.
y container to subtract. REQ: x.size() > 0 and sorted in ascending order.
result output container to fill setdifference into. REQ: result != x,y and result.capacity() >= x.size().

Definition at line 332 of file set_difference.hpp.

References set_difference_fast().

Referenced by main().

template<class InputIterator1, class InputIterator2, class OutputIterator>
void set_difference_fast (  InputIterator1 &  xiter,
const InputIterator1 &  xend,
InputIterator2 &  yiter,
const InputIterator2 &  yend,
OutputIterator &  resultIter
)  [inline]
 

Compute set difference of two vectors interpreted as ascending sorted lists of values, represented by input iterators.

i.e., compute $x \setminus y$ .

This is an alternative implementation of the STL method set-difference that hopefully is maginally faster.

Contrary to the STL implementation, this function

  • returns the modified iterator through its result iterator argument (and not as return value).
  • does not make copies of the xiter and yiter iterators, but modifies them.
These deviations from STL may be changed later if they do not have any impact on performance.

Parameters:
xiter input iterator of vector to subtract from.
xend end of input iterator of a vector to subtract from.
yiter input iterator of vector to subtract.
yend end of input iterator of vector to subtract.
resultIter output iterator of vector to fill setdifference into.

Definition at line 36 of file set_difference.hpp.

Referenced by set_difference().

template<class InputContainer1, class InputContainer2, class OutputContainer>
bool set_difference_lower_size_bound (  const InputContainer1 &  x,
const InputContainer2 &  y,
OutputContainer &  result,
const int  lowerSizeBound
)  [inline]
 

Compute set difference of two containers interpreted as ascending sorted lists of values, i.e.

, compute $x \setminus y$ . Exit operation if the result size does not exceed a given lower bound.

Parameters:
x container to subtract from. REQ: x.size() > 0 and sorted in ascending order.
y container to subtract. REQ: y.size() > 0 and sorted in ascending order.
result output container to fill setdifference into. REQ: result != x,y and result.capacity() >= min(x.size(), upperSizeBound)
lowerSizeBound minimum size of result. REQ: upperSizeBound < x.size()
Returns:
true if the result size is at least a given lower bound.

Definition at line 401 of file set_difference.hpp.

References set_difference_lower_size_bound().

template<class InputIterator1, class InputIterator2, class OutputIterator>
bool set_difference_lower_size_bound (  InputIterator1 &  xiter,
InputIterator1 &  xend,
InputIterator2 &  yiter,
const InputIterator2 &  yend,
OutputIterator &  resultIter,
const int  lowerSizeBound
)  [inline]
 

Compute set difference of two vectors interpreted as ascending sorted lists of values, represented by input iterators.

i.e., compute $x \setminus y$ . Exit operation if the result does not have a given minimal number of elements.

Parameters:
xiter input iterator of vector to subtract from.
xend end of input iterator of a vector to subtract from.
yiter input iterator of vector to subtract.
yend end of input iterator of vector to subtract.
resultIter output iterator of vector to fill setdifference into.
lowerSizeBound minimal size of result. REQ: 2 <= lowerSizeBound <= xend-xiter. (There are no improvements for lowerSizeBound = 0 or 1.)
Returns:
true if the result size is at least lowerSizeBound.

Definition at line 134 of file set_difference.hpp.

Referenced by main(), and set_difference_lower_size_bound().

template<class InputContainer1, class InputContainer2, class OutputContainer>
bool set_difference_upper_size_bound (  const InputContainer1 &  x,
const InputContainer2 &  y,
OutputContainer &  result,
const int  upperSizeBound
)  [inline]
 

Compute set difference of two containers interpreted as ascending sorted lists of values, i.e.

, compute $x \setminus y$ . Exit operation if the result exceeds a given maximal size (EARLY_FILTERING).

Parameters:
x container to subtract from. REQ: x.size() > 0 and sorted in ascending order.
y container to subtract. REQ: y.size() > 0 and sorted in ascending order.
result output container to fill setdifference into. REQ: result != x,y and result.capacity() >= min(x.size(), upperSizeBound)
upperSizeBound maximal size of result. REQ: upperSizeBound < x.size()
Returns:
true if the result has at most maximalLength elements.

Definition at line 364 of file set_difference.hpp.

References set_difference_upper_size_bound().

template<class InputIterator1, class InputIterator2, class OutputIterator>
bool set_difference_upper_size_bound (  InputIterator1 &  xiter,
const InputIterator1 &  xend,
InputIterator2 &  yiter,
const InputIterator2 &  yend,
OutputIterator &  resultIter,
const int  upperSizeBound
)  [inline]
 

Compute set difference of two vectors interpreted as ascending sorted lists of values, represented by input iterators.

i.e., compute $x \setminus y$ . Exit operation if the result size does exceed a given upper bound (EARLY_FILTERING).

Parameters:
xiter input iterator of vector to subtract from.
xend end of input iterator of a vector to subtract from.
yiter input iterator of vector to subtract.
yend end of input iterator of vector to subtract.
resultIter output iterator of vector to fill setdifference into.
upperSizeBound maximal size of result. REQ: 0 <= lowerSizeBound <= xend-xiter
Returns:
true if the result size does not exceed upperSizeBound.

Definition at line 81 of file set_difference.hpp.

Referenced by main(), and set_difference_upper_size_bound().

template<class InputContainer1, class InputContainer2>
int size_of_set_difference (  const InputContainer1 &  x,
const InputContainer2 &  y
)  [inline]
 

Compute the size of the set difference of two containers interpreted as ascending sorted lists of values, i.e.

, compute $|x \setminus y|$ .

Parameters:
x container to subtract from. REQ: x.size() > 0 and sorted in ascending order.
y container to subtract. REQ: y.size() > 0 and sorted in ascending order.
Returns:
size of the setdifference of x by y.

Definition at line 435 of file set_difference.hpp.

References size_of_set_difference().

template<class InputIterator1, class InputIterator2>
int size_of_set_difference (  InputIterator1 &  xiter,
const InputIterator1 &  xend,
InputIterator2 &  yiter,
const InputIterator2 &  yend
)  [inline]
 

Compute the size of the set difference of two vectors interpreted as ascending sorted lists of values, represented by input iterators.

i.e., compute $|x \setminus y|$ .

Parameters:
xiter input iterator of vector to subtract from.
xend end of input iterator of a vector to subtract from.
yiter input iterator of vector to subtract.
yend end of input iterator of vector to subtract.
Returns:
size of the setdifference of x by y.

Definition at line 187 of file set_difference.hpp.

Referenced by main(), and size_of_set_difference().

template<class InputContainer1, class InputContainer2>
int size_of_set_difference_lower_size_bound (  const InputContainer1 &  x,
const InputContainer2 &  y,
const int  lowerSizeBound
)  [inline]
 

Compute the size of the set difference of two containers interpreted as ascending sorted lists of values, i.e.

, compute $|x \setminus y|$ . Exit operation if the result does not exceed a given minimum size (EARLY_FILTERING).

Parameters:
x container to subtract from. REQ: x.size() > 0 and sorted in ascending order.
y container to subtract. REQ: y.size() > 0 and sorted in ascending order.
lowerSizeBound minimum size of result. REQ: 2 <= lowerSizeBound <= x.size()
Returns:
size of the setdifference of x by y, if it is at least lowerSizeBound, or 0 if it is smaller.

Definition at line 480 of file set_difference.hpp.

References size_of_set_difference_lower_size_bound().

template<class InputIterator1, class InputIterator2>
int size_of_set_difference_lower_size_bound (  InputIterator1 &  xiter,
InputIterator1 &  xend,
InputIterator2 &  yiter,
const InputIterator2 &  yend,
const int  lowerSizeBound
)  [inline]
 

Compute the isze of the set difference of two vectors interpreted as ascending sorted lists of values, represented by input iterators.

i.e., compute $|x \setminus y|$ . Exit operation if the result does not have a given minimal number of elements.

Parameters:
xiter input iterator of vector to subtract from.
xend end of input iterator of a vector to subtract from.
yiter input iterator of vector to subtract.
yend end of input iterator of vector to subtract.
lowerSizeBound minimal size of result. REQ: 2 <= lowerSizeBound <= xend-xiter. (There are no improvements for lowerSizeBound = 0 or 1.)
Returns:
result size if it is at least lowerSizeBound, 0 otherwise.

Definition at line 280 of file set_difference.hpp.

Referenced by main(), and size_of_set_difference_lower_size_bound().

template<class InputContainer1, class InputContainer2>
int size_of_set_difference_upper_size_bound (  const InputContainer1 &  x,
const InputContainer2 &  y,
const int  upperSizeBound
)  [inline]
 

Compute the size of the set difference of two containers interpreted as ascending sorted lists of values, i.e.

, compute $|x \setminus y|$ . Exit operation if the result exceeds a given maximal size (EARLY_FILTERING).

Parameters:
x container to subtract from. REQ: x.size() > 0 and sorted in ascending order.
y container to subtract. REQ: y.size() > 0 and sorted in ascending order.
upperSizeBound maximal size of result. REQ: upperSizeBound < x.size()
Returns:
size of the setdifference of x by y, if it is at most upperSizeBound, or upperSizeBound+1 if it is larger.

Definition at line 457 of file set_difference.hpp.

References size_of_set_difference_upper_size_bound().

template<class InputIterator1, class InputIterator2>
int size_of_set_difference_upper_size_bound (  InputIterator1 &  xiter,
const InputIterator1 &  xend,
InputIterator2 &  yiter,
const InputIterator2 &  yend,
int  upperSizeBound
)  [inline]
 

Compute the size of the set difference of two vectors interpreted as ascending sorted lists of values, represented by input iterators.

i.e., compute $|x \setminus y|$ . Exit operation if the size of the result exceeds a given upper bound (EARLY_FILTERING).

Parameters:
xiter input iterator of vector to subtract from.
xend end of input iterator of a vector to subtract from.
yiter input iterator of vector to subtract.
yend end of input iterator of vector to subtract.
upperSizeBound maximal size of result. REQ: upperSizeBound < x.size()
Returns:
size of the setdifference of x by y, if it is at most upperSizeBound, or upperSizeBound+1 if it is larger.

Definition at line 232 of file set_difference.hpp.

Referenced by main(), and size_of_set_difference_upper_size_bound().

Generated on Sun Sep 17 17:54:01 2006 for FIM environment by  doxygen 1.4.4