PART 2 : Why do I need a Forward Iterator to implement my customized std::search
Don't think its necessary to read part one, but I'l include the link just incase: why does std::search need forward iters
.....almost there with iterator catagories(I think) ..I looked around to find an easy all-in-1 table, that shows the functionality available from the various types of iterators ..couldn't find one so I'v tried to expand stroustrup's table to include things like: the ability to pass over a range more than once etc...let me know if I'v missed or misunderstood anything? ..or if there's a better table kicking about
*1++ must be (de)referenced between incrementions
*n++ can be incremented more than once without being (de)referenced
*n_save range can be passed over more than once and also saved/copied
------------------------------------------------------------------------------
- Iterator Operations and Categories
------------------------------------------------------------------------------
Category: output input forward bidirectional random-access
Abbreviation: Out In For Bi Ran
------------------------------------------------------------------------------
Read(*1++): =*p
Read(*n++): =*p =*p =*p
Read(*n_save): =*p =*p =*p
Write(*1++): *p=
Write(*n++): *p= *p= *p=
Write(*n_save): *p= *p= *p=
Access: -> -> -> ->[]
Iteration: ++ ++ ++ ++-- ++ -- + - += -=
Comparison: == != == != == != == != < > >= <=
------------------------------------------------------------------------------
Write(*n_save) ...wasn't sure if copying/saving an iter is read or write ..so I added it to both? ..Im guessing if you can read-pass a range more than once..you might also want to write-pass a range more than once?
I now understand why std::search needs forward iterators, but unsure why 开发者_Python百科it needs 4 ..would 2 For & 2 In suffice?
while ( begin != end ) {
if( begin2 == end2 ) { return found ; }
}
..is it because end and end2 are refd more than once( every time the while loops)..?
template <class For, class In>
For search( For begin, In end, For begin2, In end2 )
{
For found ;
For pattern_begin = begin2 ; //refd
int flag = 0 ;
// search content for pattern
while ( begin != end ) { //refd
if ( *begin != *begin2 ) { //de-refd
begin2 = pattern_begin ; //store/copy
flag = 0 ;
begin++ ; //inc
} else {
if ( flag == 0 ) {
found = begin ;
flag = 1 ;
}
begin++ ;
begin2++ ;
}
if( begin2 == end2 ) { return found ; } //refd
}
return begin ;
}
I think you've pulled the "must be incremented between dereferencing" out of thin air.
Input and output operator implement those, so that they could be used by a function that doesn't expect them in particular, but essentially incrementing may well be a no-op with them.
That search function needs four iterators, because otherwise there would simply be no way to tell where either range ends. An iterator by itself does not (necessarily) know whether it is at the end of the range or not.
A range in SC++L is represented by a pair of iterators of the same type. Technically the algorithms could accept iterators of different type for a single range, but that would hardly have any practical use and just make the code more error-prone. As it is, at least one kind of errors can be detected at compile-time:
void foo(container& a, const container& b, const container& c) {
std::search(a.begin(), b.end(), c.begin(), c.end());
}
The error here is passing iterators into different containers for the first two arguments. But in this case this would be caught at compile-time, because fortunately a
and b
happen to have different constness, so a.begin()
returns container::iterator
and b.end()
returns a different type container::const_iterator
. If all four arguments were allowed to be of different types, then this error will lead to undefined behavior at runtime.
精彩评论