stxxl::find

Author

Roman Dementiev (2006)

The semantics of the algorithm is equivalent to the STL std::find.

Prototype

template < typename ExtIterator, typename EqualityComparable >
ExtIterator find ( ExtIterator               first,
                   ExtIterator               last,
                   const EqualityComparable& value,
                   int_type                  nbuffers
                 )

Description

Returns the first iterator i in the range [first, last) such that *i == value. Returns last if no such iterator exists. To overlap I/O and computation nbuffers are used (a value at least D is recommended). The size of the buffers is derived from the container that is pointed by the iterators.

Remarks

The implementation exploits STXXL buffered streams (computation and I/O overlapped).

Parameters

begin	object of model of ext_random_access_iterator concept
end	object of model of ext_random_access_iterator concept
value	value that is equality comparable to the ExtIterator's value type
nbuffers	number of buffers (blocks) for internal use (should be at least 2*D)

Returns

first iterator i in the range [begin,end) such that *( i ) == value, if no such exists then end

Requirements on types

• EqualityComparable is a model of STL EqualityComparable concept.
• ExtIterator is a model of External Random Access Iterator.
• Equality is defined between objects of type EqualityComparable and objects of ExtIterator's value type.

Preconditions

[first, last) is a valid range.

Complexity

• Internal work is linear.
• External work: close to I/Os (read-only).

Example

typedef stxxl::VECTOR_GENERATOR<int>::result vector_type;

vector_type V;
// fill the vector ...

// find 7 in V
vector_type::iterator result = find(V.begin(), V.end(), 7);
if(result != V.end())
    std::cout << "Found at position " << (result - V.begin()) << std::endl;
else
    std::cout << "Not found" << std::endl;