These algorithms will be used later:
find.hpp
#include <iterator> template <class Iterator, class T> Iterator find(Iterator begin, Iterator end, const T& value) { while (begin != end && *begin != value) ++begin; return begin; } ///////////////////////////////////// // This is used in the third question template <class Iterator> Iterator find2(Iterator begin, Iterator end, typename std::iterator_traits<Iterator>::value_type value) { while (begin != end && *begin != value) ++begin; return begin; }
int_range_iterator
#include "find.hpp"
#include <iostream>
class int_range_iterator {
public:
int_range_iterator(int i = 0) : i_(i) {}
// implicit copy constructor, copy assignment and destructor
int operator* () const { return i_; }
int_range_iterator& operator++ () { ++i_; return *this; }
int_range_iterator operator++ (int) {
int_range_iterator tmp = *this; ++*this; return tmp; }
bool operator== (const int_range_iterator& other) const {
return i_ == other.i_;
}
bool operator!= (const int_range_iterator& other) const {
return i_ != other.i_;
}
private:
int i_;
};
int main()
{
int_range_iterator i;
i = find(int_range_iterator(0), int_range_iterator(10), 7);
std::cout << *i << std::endl;
return 0;
}
smooth_iterator
#include "find.hpp"
#include <iostream>
class smooth_iterator
: public std::iterator<std::output_iterator_tag, float>
{
public:
smooth_iterator(float* a, int s, int i) : array_(a), size_(s), i_(i) {}
// implicit copy constructor, copy assignment and destructor
float operator* ()
{
if (i_ == 0)
return (array_[i_] + array_[i_+1])/2;
else if (i_ == size_-1)
return (array_[i_-1] + array_[i_])/2;
else
return (array_[i_-1] + array_[i_] + array_[i_+1])/3;
}
smooth_iterator& operator++ () { ++i_; return *this; }
smooth_iterator operator++ (int) {
smooth_iterator tmp = *this; ++*this; return tmp; }
bool operator== (const smooth_iterator& other) const {
return array_ == other.array_
&& size_ == other.size_
&& i_ == other.i_;
}
bool operator!= (const smooth_iterator& other) const {
return ! (*this == other);
}
private:
float* array_;
int size_;
int i_;
};
int main()
{
float array[] = {1.0, 5.0, 3.0, 1.0};
const int size = sizeof(array)/sizeof(float);
smooth_iterator begin(array, size, 0);
smooth_iterator end(array, size, size);
// print all the values in the sequence [begin, end)
copy (begin, end, std::ostream_iterator<float>(std::cout, " "));
std::cout << std::endl;
// a non-algorithmic way of printing the sequence
// for (smooth_iterator i = begin; i != end; ++i)
// std::cout << *i << " ";
// std::cout << std::endl;
smooth_iterator i = ::find(begin, end, 2);
if (i == end)
std::cout << "Value not found\n";
else
std::cout << *i << std::endl;
return 0;
}
Even if type T is different than the type A of the values in the sequence, the algorithm still works if the operator!=(A, T) is defined. That is to say, we can compare objects of types A and T with each other. For example, it is allowed to do comparison between ints and floats, like this: 4 != 5.0.
We can use iterator traits to extract the true value type of the sequence. In question 2 this type was float. If this type is used as the third parameter, the call find(begin, end, 2); would still work. Even though the function find expects float as its third parameter, the integer 2 is ok since it is implicitly converted to a float.
If we try to use an illegal parameter, the two versions of find give different kind of error message. This is demonstrated by the following code.
#include "find.hpp"
#include <string>
class A{};
class my_char
{
public:
//explicit
my_char(char c) : c_(c) {}
friend
bool operator!=(char c1, my_char c2) { return c1 != c2.c_; }
bool operator!=(my_char c2) { return c_ != c2.c_; }
private:
char c_;
};
int main()
{
A a;
std::string text("abcd");
my_char c('b');
::find(text.begin(), text.end(), c); // this is ok, since operator!= defined
find2(text.begin(), text.end(), c); // error: cannot convert 'A' to 'char'
::find(text.begin(), text.end(), a); // error: no match for 'operator!='
find2(text.begin(), text.end(), a); // error: cannot convert 'A' to 'char'
my_char array[4] = {my_char('a'), my_char('b'), my_char('c'), my_char('d')};
// these work since the constructor of my_char was not specified
// explicit. Hence the compiler can use the constructor implicitly
// to convert char's to my_char's
::find(array, array+4, 'b');
find2(array, array+4, 'b');
return 0;
}
First version complains that the expression "*begin != value" is not valid. The second version complains that the type A is not the value type of the sequence (should be 'char').
In other words,
std::string::iterator i = ::find(text.begin(), text.end(), a);
works when
std::string::iterator i = text.begin(); while (*i != text.end() && *i != a) ++i;
works (in the sense that above is both syntactically and semantically correct).
But the second version is more restricted, in addition to the above it also requires that the type of a can be converted to (or is the same as) the value type of the sequence.
Also note the qualified name ::find. Otherwise there would be ambiguity in choosing between the find I provided and the find algorithm of the STL (which probably comes from the <string> header). This ambiguity is due to Koenig lookup.
#include<iostream>
#include<string>
template <typename Iter1, typename Iter2>
int
count_equal(Iter1 begin, Iter1 end, Iter2 begin2)
{
int count = 0;
Iter2 j = begin2;
for (Iter1 i = begin; i != end; ++i, ++j)
if (*i == *j)
++count;
return count;
}
int main()
{
std::string a("acbacbaccacba");
std::string b("abcacbabbcbaa");
std::cout << count_equal(a.begin(), a.end(), b.begin()) << std::endl;
return 0;
}
If we assume that the two sequences have the same length, we only need to compare when we are at the end of one of the sequences. This is a bit more efficient.
Note that we can implement the four iterators version in terms of the three iterators version. We can also do this vice versa, but then we would lose the possibility of optimisation.
The STL algorithm copy uses three iterators instead of four. (Actually, copy cannot be implemented in general with four iterators, since the second sequence can be specified with an output iterator. And for output iterators comparison operators need not be defined. Check out the requirements of copy algorithm.) So, using three iterators form is consistent with other STL algorithms too.
STL prefers to be simplistic, consistent, generic and efficient instead of user friendly (at least in this case).