STXXL  1.4-dev
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
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
beginobject of model of ext_random_access_iterator concept
endobject of model of ext_random_access_iterator concept
valuevalue that is equality comparable to the ExtIterator's value type
nbuffersnumber 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 $ N/DB $ I/Os (read-only).

Example

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;