Topic: first implementation of overloaded algorithms
Author: "THORSTEN OTTOSEN" <nesotto@cs.auc.dk>
Date: Thu, 22 Aug 2002 20:01:46 GMT Raw View
Aloha,
A while back there was a discussion about new overloads of the standard
algorithms:
http://groups.google.com/groups?q=Thorsten+Ottosen+group:comp.*+for_each&hl=
en&lr=&ie=UTF-8&selm=aeap92%24d2d%241%40sunsite.dk&rnum=1
I have taken the liberty to implement a trial version of non-mutating
algorithms and would like
any kind of feedback on errors, improvements etc.
I personally think the new algorithms can give these benefits:
1) much less typing
2) function return values can be passes directly to algorithms
3) extra concept checks can (perhaps) be added to avoid less efficient
algorithms of in favor of member functions
In the end of this mesage is the entire header and a small test file. I'm
currently using g++ 2.95.3-9 and had some
problems with code:
A) For some algorithms like 'find_first_of()' I have added 4 new overloads,
but the compiler complains about
ambiguity with two of them. This ambiguity only happens with certain
arguments, as far as I know pointers.
The two algorithms are
--------------------------------------------------------------------
// #1
template< typename Container, typename Forward_iterator >
typename Container::iterator
find_first_of( Container& search_for, Forward_iterator first2,
Forward_iterator last2 )
{
using namespace boost;
boost::function_requires< ContainerConcept<Container> >();
boost::function_requires< ForwardIteratorConcept<Forward_iterator> >();
return std::find_first_of( search_for.begin(), search_for.end(),
first2, last2 );
}
// #2
template< typename Container, typename Forward_container,
typename Binary_predicate >
typename Container::iterator
find_first_of( Container& search_for, Forward_container& search_in,
Binary_predicate binary_pred )
{
using namespace boost;
boost::function_requires< ContainerConcept<Container> >();
boost::function_requires< ForwardContainerConcept<Forward_container>
>();
boost::function_requires< BinaryPredicateConcept<Binary_predicate,
typename Container::value_type,
typename Forward_container::value_type> >();
return std::find_first_of( search_for.begin(), search_for.end(),
search_in.begin(), searc_in.end(),
binary_pred );
}
----------------------------------------------------------------------------
---------------
If I feed them with the following code
----------------------------------------------------------------------------
---------------
const char* WS = "\t\n ";
const int n_WS = strlen(WS);
string wss = "\t\n ";
ext::find_first_of( s1, wss.begin(), wss.end() ); // works always
ext::find_first_of( s1, WS, WS + n_WS ); // gives ambiguity
----------------------------------------------------------------------------
----------------
the compiler complains with this error message:
----------------------------------------------------------------------------
----------------
../ext/algorithm_test.cpp:127: call of overloaded `find_first_of
(_STL::string &, const char *&, const char *)' is ambiguous
../ext/algorithm.hpp:205: candidates are: char *
ext::find_first_of<_STL::string, const char *>(_STL::string &, const char *,
const char *)
../ext/algorithm.hpp:257: char *
ext::find_first_of<_STL::string, const char *, const char *>(_STL::string &,
const char *&, const char *)
----------------------------------------------------------------------------
-----------------
Is the compiler right? If so, the last overload should be abandoned.
B) I wanted to optimize parameter passing by using boost's call_traits. Eg.
in 'find()':
----------------------------------------------------------------------------
--
template< typename Container, typename Equality_comparable >
typename Container::iterator
find( Container& c,
//typename boost::call_traits<Equality_comparable>::param_type
value )
const Equality_comparable& value )
{
using namespace boost;
boost::function_requires< ContainerConcept<Container> >();
boost::function_requires< EqualityComparableConcept<Equality_comparable>
>();
return std::find( c.begin(), c.end(), value );
}
----------------------------------------------------------------------------
---------
If I enable the uncommented line instead, I get this compiler error:
----------------------------------------------------------------------------
----------
../ext/algorithm_test.cpp:95: no matching function for call to `find
(_STL::list<int,_STL::allocator<int> > &, int)'
// the code reads: list<int>::iterator result = ext::find( L, 7 );
----------------------------------------------------------------------------
------------
Is the compiler right about this? I suspect it is not.
C) One could consider to put more concept cheks into the code for eg.
'find()' above to ensure
that associative containers would be rejected. The problem is that one
needs to specify that
the container must _not_ be an associative container. The opposite
should be trivial with boost
concept cheks:
------------------------------
using namespace boost;
boost::function_requires< AssociativeContainerConcept<Container> >();
------------------------------
Does anybody knows how to achive the reverse? Is it worth it?
Ok, here's all the code (I'm sorry the code gets so messy when I copy it
into this window .( )
Thanks in advance
Thorsten, Aalborg University
----------------------------------------------------------------------------
-----------------
algorithm.hpp
----------------------------------------------------------------------------
------------------
/**
* @file: algorithm.hpp
*
* @short: replacement for <algorithm> header which add
* overloaded versions of all algortihms. Each overload
* simply replaces the two first arguments with a single:
* instead of two iterators one can supply a standard compliant
* container object that supports functions '.begin()' and
'.end()'.
* Let 'c' and 'd' be standard compliant container objects and
* let '...' denote either nothing, predicates, objects etc. Then,
* for any std-algorithm
*
* algorithm( Iterator first, Iterator last, ... ) #1
*
* used as
*
* algorithm( c.begin(), c.end(), ... ) #1
*
* this header supplies
*
* algorithm( c, ... ) #1
*
* For any std-algorithm
*
* algorithm( Iterator first1, Iterator last1,
* Iterator first2, ... ) #2
*
* used as
*
* algorithm( c.begin(), c.end(), first2, ... ) #2
*
* this header supplies
*
* algorithm( c, first2, ... ) #2
*
* For any std-algorithm
*
* algorithm( Iterator first1, Iterator last1,
* Iterator first2, Iterator last2, ... ) #3
*
* used as
*
* algorithm( c.begin(), c.end(), first2, last2, ... ) #3
* algorithm( c.begin(), c.end(), d.begin(), d.end(), ... ) #3
*
* this header supplies
*
* algorithm( c, first1, first2, ... ) #3
* algorithm( c, d, ... ) #3
*
*
* @rationale: All standard algorithms take a range
* specified by two iterators. Often the
* algorithm traverses the entire range,
* that is, [c.begin(), c.end()) for some
* STL compliant container 'c'. Because
* this happens frequently, one has to type
* a lot of extra chars. With the new algorithms
* (which merely wraps the old ones) one can
* just supply the container object 'c'.
*
* Moreover,
* the new overload makes it possible to pass function
* return values to algorithms - this was tedious before
* because one needed to make a temporary.
*
* A third advantage
* is the use of concept checks to reject wrong uses
* of the algorithm when a better member function
* is available. That way the user will be forced to
* use the most efficient algorithm. This is especially
* true for std::set/multiset and std::map/multimap. See
* Scott Meyers "Effective STL" items 44 and 45.
*
* The overloaded versions must not (by the C++ standard)
* be placed in the 'std' namespace and are therefore put
* in namespace 'ext'.
*
* @translation of concepts: The following table shows how iterator
* types maps to equivalent containers, that is,
* the least restrictive containers that support
* a given iterator type:
*
* container -> input iterator
* forward container -> forward iterator
* reversible cont. -> bidirectional iterator
* random access con. -> random access iterator
*
* Note that it is not necessary to check for
* the equality comparable concept of container
* elements since it follows from the container
* concept.
*
*
* @alternative: The simplest alternative must be a macro. One could
* define 'ALL' like this:
*
* #define ALL( C ) C.begin(), C.end()
*
* and then use it like this:
*
* vector<T> foo() const;
* ...
* vector<T> v = ...
* for_each( ALL( v ), ... );
* for_each( ALL( foo() ), ... );
*
* This has several drawbacks. It is not as terse
* the overloaded algorithms, that is, not as
* transparent. The function return
* value does not work good enough because the function
* will be called twice. For functions that are not
idempotent,
* that behavior would be misleading/wrong.
*/
#ifndef ALGORITHM_EXT_HPP
#define ALGORITHM_EXT_HPP
#include <algorithm>
#include <iterator>
#include <boost/concept_check.hpp>
#include <boost/call_traits.hpp>
namespace ext
{
////////////////////////////////////////////////////////////////////////////
/
// Non-mutating algorithms
////////////////////////////////////////////////////////////////////////////
/
template< typename Container, typename Unary_function >
Unary_function
for_each( Container& c, Unary_function f )
{
using namespace boost;
boost::function_requires< ContainerConcept<Container> >();
//
// not applicable because of arbitrary return value:
// boost::function_requires< UnaryFunctionConcept<Unary_function> >();
//
return std::for_each( c.begin(), c.end(), f );
}
template< typename Container, typename Equality_comparable >
typename Container::iterator
find( Container& c,
typename boost::call_traits<Equality_comparable>::param_type value )
//const Equality_comparable& value )
{
using namespace boost;
boost::function_requires< ContainerConcept<Container> >();
boost::function_requires< EqualityComparableConcept<Equality_comparable>
>();
return std::find( c.begin(), c.end(), value );
}
template< typename Container, typename Unary_predicate >
typename Container::iterator
find_if( Container& c, Unary_predicate pred )
{
using namespace boost;
boost::function_requires< ContainerConcept<Container> >();
boost::function_requires< UnaryPredicateConcept<Unary_predicate,
typename Container::value_type> >();
return std::find_if( c.begin(), c.end(), pred );
}
template< typename Forward_container >
typename Forward_container::iterator
adjacent_find( Forward_container& c )
{
using namespace boost;
boost::function_requires< ForwardContainerConcept<Forward_container>
>();
return std::adjacent_find( c.begin(), c.end() );
}
template< typename Forward_container, typename Binary_predicate >
typename Forward_container::iterator
adjacent_find( Forward_container& c, Binary_predicate binary_pred )
{
using namespace boost;
boost::function_requires< ForwardContainerConcept<Forward_container>
>();
typedef typename Forward_container::value_type value_type;
boost::function_requires< BinaryPredicateConcept<Binary_predicate,
value_type, value_type > >();
return std::adjacent_find( c.begin(), c.end(), binary_pred );
}
template< typename Container, typename Forward_iterator >
typename Container::iterator
find_first_of( Container& search_for, Forward_iterator first2,
Forward_iterator last2 )
{
using namespace boost;
boost::function_requires< ContainerConcept<Container> >();
boost::function_requires< ForwardIteratorConcept<Forward_iterator> >();
return std::find_first_of( search_for.begin(), search_for.end(),
first2, last2 );
}
template< typename Container, typename Forward_container >
typename Container::iterator
find_first_of( Container& search_for, Forward_container& search_in )
{
using namespace boost;
boost::function_requires< ContainerConcept<Container> >();
boost::function_requires< ForwardContainerConcept<Forward_container>
>();
return std::find_first_of( search_for.begin(), search_for.end(),
search_in.begin(), search_in.end() );
}
template< typename Container, typename Forward_iterator,
typename Binary_predicate >
typename Container::iterator
find_first_of( Container& search_for, Forward_iterator first2,
Forward_iterator last2, Binary_predicate binary_pred )
{
using namespace boost;
boost::function_requires< ContainerConcept<Container> >();
boost::function_requires< ForwardIteratorConcept<Forward_iterator> >();
boost::function_requires< BinaryPredicateConcept<Binary_predicate,
typename Container::value_type,
typename std::iterator_traits<Forward_iterator>::value_type> >();
return std::find_first_of( search_for.begin(), search_for.end(),
first2, last2, binary_pred );
}
/**
* @note: leads to ambiguity when using gcc 2.95.3-9. The compiler is most
* likely right
template< typename Container, typename Forward_container,
typename Binary_predicate >
typename Container::iterator
find_first_of( Container& search_for, Forward_container& search_in,
Binary_predicate binary_pred )
{
using namespace boost;
boost::function_requires< ContainerConcept<Container> >();
boost::function_requires< ForwardContainerConcept<Forward_container>
>();
boost::function_requires< BinaryPredicateConcept<Binary_predicate,
typename Container::value_type,
typename Forward_container::value_type> >();
return std::find_first_of( search_for.begin(), search_for.end(),
search_in.begin(), searc_in.end(),
binary_pred );
}
*/
/**
* @note: depricated version of <code>count</code> is not overloaded.
*/
template< typename Container, typename Equality_comparable >
typename std::iterator_traits<typename
Container::iterator>::difference_type
count( Container& c,
//typename boost::call_traits<Equality_comparable>::param_type
value )
const Equality_comparable& value )
{
using namespace boost;
boost::function_requires< ContainerConcept<Container> >();
boost::function_requires< EqualityComparableConcept<Equality_comparable>
>();
return std::count( c.begin(), c.end(), value );
}
/**
* @note: depricated version of <code>count_if</code> is not overloaded.
*/
template< typename Container, typename Unary_predicate >
typename std::iterator_traits<typename
Container::iterator>::difference_type
count_if( Container& c, Unary_predicate pred )
{
using namespace boost;
boost::function_requires< ContainerConcept<Container> >();
boost::function_requires< UnaryPredicateConcept<Unary_predicate,
typename Container::value_type> >();
return std::count_if( c.begin(), c.end(), pred );
}
template< typename Container, typename Input_iterator >
typename std::pair<typename Container::iterator, Input_iterator>
mismatch( Container& c, Input_iterator first2 )
{
using namespace boost;
boost::function_requires< ContainerConcept<Container> >();
boost::function_requires< InputIteratorConcept<Input_iterator> >();
return std::mismatch( c.begin(), c.end(), first2 );
}
template< typename Container, typename Input_iterator,
typename Binary_predicate >
typename std::pair<typename Container::iterator, Input_iterator>
mismatch( Container& c, Input_iterator first2, Binary_predicate
binary_pred )
{
using namespace boost;
boost::function_requires< ContainerConcept<Container> >();
boost::function_requires< InputIteratorConcept<Input_iterator> >();
boost::function_requires< BinaryPredicateConcept<Binary_predicate,
typename Container::value_type,
typename std::iterator_traits<Input_iterator>::value_type> >();
return std::mismatch( c.begin(), c.end(), first2, binary_pred );
}
template< typename Container, typename Input_iterator >
bool equal( Container& c, Input_iterator first2 )
{
using namespace boost;
boost::function_requires< ContainerConcept<Container> >();
boost::function_requires< InputIteratorConcept<Input_iterator> >();
return std::equal( c.begin(), c.end(), first2 );
}
template< typename Container, typename Input_iterator,
typename Binary_predicate >
bool equal( Container& c, Input_iterator first2,
Binary_predicate binary_pred )
{
using namespace boost;
boost::function_requires< ContainerConcept<Container> >();
boost::function_requires< InputIteratorConcept<Input_iterator> >();
boost::function_requires< BinaryPredicateConcept<Binary_predicate,
typename Container::value_type,
typename std::iterator_traits<Input_iterator>::value_type> >();
return std::equal( c.begin(), c.end(), first2, binary_pred );
}
template< typename Forward_container, typename Forward_iterator >
typename Forward_container::iterator
search( Forward_container& search_in, Forward_iterator first2,
Forward_iterator last2 )
{
using namespace boost;
boost::function_requires< ForwardContainerConcept<Forward_container> >();
boost::function_requires< ForwardIteratorConcept<Forward_iterator> >();
return std::search( search_in.begin(), search_in.end(), first2, last2 );
}
template< typename Forward_container1, typename Forward_container2 >
typename Forward_container1::iterator
search( Forward_container1& search_in, Forward_container2& search_for )
{
using namespace boost;
boost::function_requires< ForwardContainerConcept<Forward_container1> >();
boost::function_requires< ForwardContainerConcept<Forward_container2> >();
return std::search( search_in.begin(), search_in.end(),
search_for.begin(), search_for.end());
}
template< typename Forward_container, typename Forward_iterator,
typename Binary_predicate >
typename Forward_container::iterator
search( Forward_container& search_in, Forward_iterator first2,
Forward_iterator last2, Binary_predicate binary_pred )
{
using namespace boost;
boost::function_requires< ForwardContainerConcept<Forward_container> >();
boost::function_requires< ForwardIteratorConcept<Forward_iterator> >();
boost::function_requires< BinaryPredicateConcept<Binary_predicate,
typename Forward_container::value_type,
typename std::iterator_traits<Forward_iterator>::value_type> >();
return std::search( search_in.begin(), search_in.end(),
first2, last2, binary_pred );
}
template< typename Forward_container1, typename Forward_container2,
typename Binary_predicate >
typename Forward_container1::iterator
search( Forward_container1& search_in, Forward_container2& search_for,
Binary_predicate binary_pred )
{
using namespace boost;
boost::function_requires< ForwardContainerConcept<Forward_container1>
>();
boost::function_requires< ForwardContainerConcept<Forward_container2> >();
boost::function_requires< BinaryPredicateConcept<Binary_predicate,
typename Forward_container1::value_type,
typename Forward_container2::value_type> >();
return std::search( search_in.begin(), search_in.end(),
search_for.begin(), search_for.end(), binary_pred );
}
template< typename Forward_container, typename Integer,
typename Equality_comparable >
typename Forward_container::iterator
search_n( Forward_container& c, Integer count,
//typename boost::call_traits<Equality_comparable>::param_type
value )
const Equality_comparable& value )
{
using namespace boost;
boost::function_requires< ForwardContainerConcept<Forward_container> >();
boost::function_requires< IntegerConcept<Integer> >();
boost::function_requires< EqualityComparableConcept<Equality_comparable>
>();
return std::search_n( c.begin(), c.end(), count, value );
}
template< typename Forward_container, typename Integer,
typename Equality_comparable, typename Binary_predicate >
typename Forward_container::iterator
search_n( Forward_container& c, Integer count,
//typename boost::call_traits<Equality_comparable>::param_type
value,
const Equality_comparable& value, Binary_predicate binary_pred )
{
using namespace boost;
boost::function_requires< ForwardContainerConcept<Forward_container> >();
boost::function_requires< IntegerConcept<Integer> >();
boost::function_requires< EqualityComparableConcept<Equality_comparable>
>();
typedef typename Forward_container::value_type value_type;
boost::function_requires< BinaryPredicateConcept<Binary_predicate,
value_type,
value_type> >();
return std::search_n( c.begin(), c.end(), count, value, binary_pred );
}
template< typename Forward_container, typename Forward_iterator >
typename Forward_container::iterator
find_end( Forward_container& search_in, Forward_iterator first2,
Forward_iterator last2 )
{
using namespace boost;
boost::function_requires< ForwardContainerConcept<Forward_container> >();
boost::function_requires< ForwardIteratorConcept<Forward_iterator> >();
return std::find_end( search_in.begin(), search_in.end(), first2, last2 );
}
template< typename Forward_container1, typename Forward_container2 >
typename Forward_container1::iterator
find_end( Forward_container1& search_in, Forward_container2& search_for )
{
using namespace boost;
boost::function_requires< ForwardContainerConcept<Forward_container1> >();
boost::function_requires< ForwardContainerConcept<Forward_container2> >();
return std::find_end( search_in.begin(), search_in.end(),
search_for.begin(), search_for.end());
}
template< typename Forward_container, typename Forward_iterator,
typename Binary_predicate >
typename Forward_container::iterator
find_end( Forward_container& search_in, Forward_iterator first2,
Forward_iterator last2, Binary_predicate binary_pred )
{
using namespace boost;
boost::function_requires< ForwardContainerConcept<Forward_container> >();
boost::function_requires< ForwardIteratorConcept<Forward_iterator> >();
boost::function_requires< BinaryPredicateConcept<Binary_predicate,
typename Forward_container::value_type,
typename std::iterator_traits<Forward_iterator>::value_type> >();
return std::find_end( search_in.begin(), search_in.end(),
first2, last2, binary_pred );
}
template< typename Forward_container1, typename Forward_container2,
typename Binary_predicate >
typename Forward_container1::iterator
find_end( Forward_container1& search_in, Forward_container2& search_for,
Binary_predicate binary_pred )
{
using namespace boost;
boost::function_requires< ForwardContainerConcept<Forward_container1>
>();
boost::function_requires< ForwardContainerConcept<Forward_container2> >();
boost::function_requires< BinaryPredicateConcept<Binary_predicate,
typename Forward_container1::value_type,
typename Forward_container2::value_type> >();
return std::find_end( search_in.begin(), search_in.end(),
search_for.begin(), search_for.end(), binary_pred );
}
////////////////////////////////////////////////////////////////////////////
/
// Mutating algorithms
////////////////////////////////////////////////////////////////////////////
/
////////////////////////////////////////////////////////////////////////////
/
// Sorting algorithms
////////////////////////////////////////////////////////////////////////////
/
} // namespace 'ext'
#endif
--------------------------------------------------
test.cpp
--------------------------------------------------
#include <functional>
#include <cassert>
#include <list>
#include <iostream>
#include <string>
#include <vector>
#include "algorithm.hpp"
using namespace std;
template<class T> struct print : public unary_function<T, void>
{
print(ostream& out) : os(out), count(0)
{
}
void operator() (T x)
{
os << x << ' '; ++count;
}
ostream& os;
int count;
};
bool eq_nosign(int x, int y)
{
return abs(x) == abs(y);
}
void lookup(int* first, int* last, size_t count, int val)
{
cout << "Searching for a sequence of "
<< count
<< " '" << val << "'"
<< (count != 1 ? "s: " : ": ");
vector<int> v( first, last );
int* result = search_n( first, last, count, val);
int* result2 = ext::search_n( v, count, val );
if( result == last )
cout << "Not found" << endl;
else
{
assert( *result == *result2 );
cout << "Index = " << result - first << endl;
}
}
void lookup_nosign(int* first, int* last, size_t count, int val)
{
cout << "Searching for a (sign-insensitive) sequence of "
<< count
<< " '" << val << "'"
<< (count != 1 ? "s: " : ": ");
vector<int> v( first, last );
int* result = search_n(first, last, count, val,eq_nosign);
int* result2 = ext::search_n( v, count, val, eq_nosign );
if( result == last )
cout << "Not found" << endl;
else
{
assert( *result == *result2 );
cout << "Index = " << result - first << endl;
}
}
int main()
{
using namespace std;
int A[] = {1, 4, 2, 8, 5, 7};
int A2[] = {1, 2, 3, 4, 6, 5, 7, 8};
const int N = sizeof(A) / sizeof(int);
const int N2 = sizeof(A2) / sizeof(int);
vector<int> v( A, A + N ),
v2( A2, A2 + N2 );
// foreach
{
print<int> P = ext::for_each( v, print<int>(cout) );
cout << endl << P.count << " objects printed." << endl;
// find
list<int> L;
L.push_back(3);
L.push_back(1);
L.push_back(7);
list<int>::iterator result = ext::find( L, 7 );
assert(result == L.end() || *result == 7);
// find_if
L.clear();
L.push_back(-3);
L.push_back(0);
L.push_back(3);
L.push_back(-2);
result = ext::find_if( L, bind2nd( greater<int>(), 0 ) );
assert(result == L.end() || *result > 0);
}
{
// adjecent_find
const int* p = ext::adjacent_find( v2, greater<int>());
cout << "Element " << p - v2.begin() << " is out of order: "
<< *p << " > " << *(p + 1) << "." << endl;
}
const char* WS = "\t\n ";
const int n_WS = strlen(WS);
string wss = "\t\n ";
{
// find_first_of
string s1 = "This sentence contains five words.";
string s2 = "OneWord";
char* end1 = ext::find_first_of( s1, WS, WS + n_WS );
char* end2 = ext::find_first_of( s2, WS, WS + n_WS );
char* end11 = ext::find_first_of( s1, wss );
char* end22 = ext::find_first_of( s2, wss );
assert( end1 == end11 && end2 == end22 );
assert( end11 == ext::find_first_of( s1, wss.begin(), wss.end() ) );
printf("First word of s1: %.*s\n", end1 - s1.c_str(), s1.c_str() );
printf("First word of s2: %.*s\n", end2 - s2.c_str(), s2.c_str() );
}
{
// count
int A[] = { 2, 0, 4, 6, 0, 3, 1, -7};
const int N = sizeof(A) / sizeof(int);
vector<int> v( A, A + N );
cout << "Number of zeros: "
<< ext::count( v, 0)
<< endl;
// count_if
cout << "Number of even elements: "
<< ext::count_if( v, compose1( bind2nd(equal_to<int>(), 0),
bind2nd(modulus<int>(), 2)))
<< endl;
}
{
// mismatch
int A1[] = { 3, 1, 4, 1, 5, 9, 3};
int A2[] = { 3, 1, 4, 2, 8, 5, 7};
const int N = sizeof(A1) / sizeof(int);
vector<int> v1( A1, A1 + N ),
v2( A2, A2 + N );
pair<int*, int*> result = mismatch(A1, A1 + N, A2);
pair<int*, int*> result2 = ext::mismatch( v1, v2.begin() );
assert( *result.first == *result2.first &&
*result.second == *result2.second );
cout << "The first mismatch is in position " << result.first - A1 << endl;
cout << "Values are: " << *(result.first) << ", " << *(result.second) <<
endl;
}
{
// equal
int A1[] = { 3, 1, 4, 1, 5, 9, 3};
int A2[] = { 3, 1, 4, 2, 8, 5, 7};
const int N = sizeof(A1) / sizeof(int);
vector<int> v( A1, A1 + N );
list<int> l( A2, A2 + N );
assert( equal( A1, A1 + N, A2 ) == ext::equal( v, l.begin() ) );
cout << "Result of comparison: " << equal(A1, A1 + N, A2) << endl;
}
{
// search
string s1 = "Hello, world!";
string s2 = "world";
const char* p = search(s1.begin(), s1.end(), s2.begin(), s2.end() );
const char* p2 = ext::search( s1, s2 );
assert( p == p2 && p == ext::search( s1, s2.begin(), s2.end() ) );
printf("Found subsequence \"%s\" at character %d of sequence \"%s\".\n",
s2.begin(), p - s1.begin(), s1.begin() );
}
{
// search_n
const int N = 10;
int A[N] = {1, 2, 1, 1, 3, -3, 1, 1, 1, 1};
lookup(A, A+N, 1, 4);
lookup(A, A+N, 0, 4);
lookup(A, A+N, 1, 1);
lookup(A, A+N, 2, 1);
lookup(A, A+N, 3, 1);
lookup(A, A+N, 4, 1);
lookup(A, A+N, 1, 3);
lookup(A, A+N, 2, 3);
lookup_nosign(A, A+N, 1, 3);
lookup_nosign(A, A+N, 2, 3);
}
{
// find_end
char* s = "executable.exe";
char* suffix = "exe";
string ss = "executable.exe";
string ssuffix = "exe";
const int N = strlen(s);
const int N_suf = strlen(suffix);
char* location = find_end(s, s + N, suffix, suffix + N_suf);
char* location2 = ext::find_end( ss, ssuffix );
char* location3 = ext::find_end( ss, ssuffix.begin(),
ssuffix.end() );
assert( location3 == location2 );
assert( *location2 == *location );
if( location != s + N )
{
cout << "Found a match for " << suffix << " within " << s << endl;
cout << s << endl;
int i;
for( i = 0; i < (location - s); ++i )
cout << ' ';
for( i = 0; i < N_suf; ++i )
cout << '^';
cout << endl;
}
else
cout << "No match for " << suffix << " within " << s << endl;
}
} // 'main()'
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]