{"id":3783,"date":"2010-08-09T17:26:00","date_gmt":"2010-08-09T17:26:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/vcblog\/2010\/08\/09\/the-filterator\/"},"modified":"2019-02-18T18:45:28","modified_gmt":"2019-02-18T18:45:28","slug":"the-filterator","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/cppblog\/the-filterator\/","title":{"rendered":"The Filterator"},"content":{"rendered":"

My name is Ahmed Charles and I currently work on Windows Error Reporting.  I believe that this is the first time that someone not on the VC team has written a blog, but I hope you will find it useful anyways.  I’d like to thank Stephan T. Lavavej for the idea and valuable feedback while writing it.  And we both owe the idea for the iterator to Boost.<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

A common question from programmers who have an intermediate amount of experience with using the STL is, “How do I write an STL iterator?”.  Writing an STL iterator is not especially difficult – it just requires some care.  STL iterators must satisfy a number of requirements (given by section 24.2 of the (soon to be) International Standard for C++, draft at http:\/\/www.open-std.org\/jtc1\/sc22\/wg21\/docs\/papers\/2010\/n3092.pdf<\/a>), and the code to do so takes roughly 150 editor lines.  Figuring out the code from the requirements can be overwhelming, but once you see the code, it’s easy.<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

Therefore, I’ve written an example STL iterator, whose purpose in life is to wrap an existing iterator and filter the elements based on a supplied predicate, which I’ve imaginatively called Filterator (in homage to the Mallocator).  I’ve carefully implemented all of the checks that would be required in real production code.  And I’ve exhaustively commented the various parts of the iterator to aid in determining which portions should be changed when implementing other iterators.  Hopefully, this should demystify the implementation of STL iterators:<\/span><\/p>\n

<\/span><\/p>\n

<\/p>\n

C:Temp>type filterator.cpp<\/p>\n

<\/span><\/p>\n

\/\/ The following headers are required for all iterators.<\/p>\n

<\/span><\/p>\n

#include <iterator>    <\/span>\/\/ Required for iterator_traits<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

\/\/ The following headers contain stuff that filterator uses.<\/p>\n

<\/span><\/p>\n

#include <type_traits> \/\/ Required for std::conditional\/<\/p>\n

<\/span><\/p>\n

                       <\/span>\/\/ is_same\/is_convertible<\/p>\n

<\/span><\/p>\n

#include <memory>      <\/span>\/\/ For std::addressof<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

\/\/ The following headers contain stuff that main() uses.<\/p>\n

<\/span><\/p>\n

#include <algorithm>   <\/span>\/\/ For std::fill<\/p>\n

<\/span><\/p>\n

#include <iostream>    <\/span>\/\/ For std::cout<\/p>\n

<\/span><\/p>\n

#include <ostream>     <\/span>\/\/ For std::endl<\/p>\n

<\/span><\/p>\n

#include <string>      <\/span>\/\/ For std::string<\/p>\n

<\/span><\/p>\n

#include <vector>      <\/span>\/\/ For std::vector<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

template <class Iterator, class Predicate><\/p>\n

<\/span><\/p>\n

class filterator {<\/p>\n

<\/span><\/p>\n

public:<\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ Required to access private members in the converting<\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ constructor because different instantiations of a<\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ template are different classes without special access<\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ rights to each other.<\/p>\n

<\/span><\/p>\n

    <\/span>template <class OtherIterator, class OtherPredicate><\/p>\n

<\/span><\/p>\n

        <\/span>friend class filterator;<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ Define iterator_category to be the iterator category<\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ of the Iterator used, unless it is a random access<\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ iterator, which cannot provide constant time<\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ functions for random access operators because of<\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ needing to test the predicate.<\/p>\n

<\/span><\/p>\n

    <\/span>typedef typename std::iterator_traits<<\/p>\n

<\/span><\/p>\n

        <\/span>Iterator>::iterator_category underlying_category;<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>typedef typename std::conditional<std::is_same<<\/p>\n

<\/span><\/p>\n

            <\/span>underlying_category,<\/p>\n

<\/span><\/p>\n

            <\/span>std::random_access_iterator_tag<\/p>\n

<\/span><\/p>\n

        <\/span>>::value,<\/p>\n

<\/span><\/p>\n

        <\/span>std::bidirectional_iterator_tag,<\/p>\n

<\/span><\/p>\n

        <\/span>underlying_category>::type iterator_category;<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ Define the other typedefs required by iterators.<\/p>\n

<\/span><\/p>\n

    <\/span>typedef typename std::iterator_traits<<\/p>\n

<\/span><\/p>\n

        <\/span>Iterator>::value_type value_type;<\/p>\n

<\/span><\/p>\n

    <\/span>typedef typename std::iterator_traits<<\/p>\n

<\/span><\/p>\n

        <\/span>Iterator>::reference reference;<\/p>\n

<\/span><\/p>\n

    <\/span>typedef typename std::iterator_traits<<\/p>\n

<\/span><\/p>\n

        <\/span>Iterator>::pointer pointer;<\/p>\n

<\/span><\/p>\n

    <\/span>typedef typename std::iterator_traits<<\/p>\n

<\/span><\/p>\n

        <\/span>Iterator>::difference_type difference_type;<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ Default constructor which value-initializes all of<\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ the members.<\/p>\n

<\/span><\/p>\n

    <\/span>filterator() : m_iter(), m_end(), m_pred() {}<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ Constructs a filterator from all possible parameters.<\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ pred may be default constructed, as well.<\/p>\n

<\/span><\/p>\n

    <\/span>filterator(Iterator begin, Iterator end,<\/p>\n

<\/span><\/p>\n

        <\/span>Predicate pred = Predicate())<\/p>\n

<\/span><\/p>\n

 <\/span>       <\/span>: m_iter(begin), m_end(end), m_pred(pred) {<\/p>\n

<\/span><\/p>\n

        <\/span>validate_predicate();<\/p>\n

<\/span><\/p>\n

    <\/span>}<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ Converting constructor which can be used to convert<\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ iterators into const_iterators.<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>template <class OtherIterator> filterator(<\/p>\n

<\/span><\/p>\n

        <\/span>const filterator<OtherIterator, Predicate>& f,<\/p>\n

<\/span><\/p>\n

        <\/span>typename std::enable_if<<\/p>\n

<\/span><\/p>\n

            <\/span>std::is_convertible<<\/p>\n

<\/span><\/p>\n

                <\/span>OtherIterator, Iterator<\/p>\n

<\/span><\/p>\n

            <\/span>>::value>::type * = nullptr)<\/p>\n

<\/span><\/p>\n

        <\/span>: m_iter(f.m_iter),<\/p>\n

<\/span><\/p>\n

        <\/span>m_end(f.m_end),<\/p>\n

<\/span><\/p>\n

  <\/span>      <\/span>m_pred(f.m_pred) {}<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ Returns a copy of the predicate for this filterator.<\/p>\n

<\/span><\/p>\n

    <\/span>Predicate predicate() const {<\/p>\n

<\/span><\/p>\n

        <\/span>return m_pred;<\/p>\n

<\/span><\/p>\n

    <\/span>}<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ Returns a copy of a filterator representing the end<\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ of this sequence.<\/p>\n

<\/span><\/p>\n

    <\/span>filterator end() const {<\/p>\n

<\/span><\/p>\n

        <\/span>return filterator(m_end, m_end, m_pred);<\/p>\n

<\/span><\/p>\n

    <\/span>}<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ Returns a copy of the end iterator for this<\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ filterator.<\/p>\n

<\/span><\/p>\n

    <\/span>Iterator base_end() const {<\/p>\n

<\/span><\/p>\n

        <\/span>return m_end;<\/p>\n

<\/span><\/p>\n

    <\/span>}<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ Returns a copy of the iterator which represents the<\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ current position.<\/p>\n

<\/span><\/p>\n

    <\/span>Iterator base() const {<\/p>\n

<\/span><\/p>\n

        <\/span>return m_iter;<\/p>\n

<\/span><\/p>\n

    <\/span>}<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ Dereferences this iterator<\/p>\n

<\/span><\/p>\n

    <\/span>reference operator*() const {<\/p>\n

<\/span><\/p>\n

        <\/span>return *m_iter;<\/p>\n

<\/span><\/p>\n

    <\/span>}<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ Dereferences this iterator<\/p>\n

<\/span><\/p>\n

    <\/span>pointer operator->() const {<\/p>\n

<\/span><\/p>\n

       <\/span> <\/span>return std::addressof(*m_iter);<\/p>\n

<\/span><\/p>\n

    <\/span>}<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ Pre-increment operator which checks the predicate<\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ before stopping.<\/p>\n

<\/span><\/p>\n

    <\/span>filterator& operator++() {<\/p>\n

<\/span><\/p>\n

        <\/span>++m_iter;<\/p>\n

<\/span><\/p>\n

        <\/span>validate_predicate();<\/p>\n

<\/span><\/p>\n

        <\/span>return *this;<\/p>\n

<\/span><\/p>\n

    <\/span>}<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ Post-increment operator which checks the predicate<\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ before stopping.<\/p>\n

<\/span><\/p>\n

    <\/span>filterator operator++(int) {<\/p>\n

<\/span><\/p>\n

        <\/span>filterator temp(*this);<\/p>\n

<\/span><\/p>\n

        <\/span>++*this;<\/p>\n

<\/span><\/p>\n

        <\/span>return temp;<\/p>\n

<\/span><\/p>\n

   <\/span>}<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ Pre-decrement operator which checks the predicate<\/p>\n

<\/span><\/p>\n

    <\/span>\/\/ before stopping.<\/p>\n

<\/span><\/p>\n

    <\/span>filterator& operator–() {<\/p>\n

<\/span><\/p>\n

        <\/span>–m_iter;<\/p>\n

<\/span><\/p>\n

        <\/span>\/\/ note that we don’t store a begin iterator to<\/p>\n

<\/span><\/p>\n

        <\/span>\/\/ check for passing the beginning of the sequence,<\/p>\n

<\/span><\/p>\n

        <\/span>\/\/ unlike the end. This is because decrementing the<\/p>\n

<\/span><\/p>\n

        <\/span>\/\/ first iterator is undefined and applying a filter<\/p>\n

<\/span><\/p>\n

        <\/span>\/\/ on top of the underlying iterator doesn’t change<\/p>\n

<\/span><\/p>\n

        <\/span>\/\/ this, even if the resulting sequence is empty.<\/p>\n

<\/span><\/p>\n

        <\/span>while (!m_pred(*m_iter)) –m_iter;<\/p>\n

<\/span><\/p>\n

        <\/span>return *this;<\/p>\n

<\/span><\/p>\n

    <\/span>}<\/p>\n

<\/span><\/p>\n

<\/span><\/p>\n

<\/span><\/p><\/p>\n","protected":false},"excerpt":{"rendered":"

My name is Ahmed Charles and I currently work on Windows Error Reporting.  I believe that this is the first time that someone not on the VC team has written a blog, but I hope you will find it useful anyways.  I’d like to thank Stephan T. Lavavej for the idea and valuable feedback while […]<\/p>\n","protected":false},"author":289,"featured_media":35994,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[3,32],"class_list":["post-3783","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-cplusplus","tag-dev","tag-stl"],"acf":[],"blog_post_summary":"

My name is Ahmed Charles and I currently work on Windows Error Reporting.  I believe that this is the first time that someone not on the VC team has written a blog, but I hope you will find it useful anyways.  I’d like to thank Stephan T. Lavavej for the idea and valuable feedback while […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts\/3783","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/users\/289"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/comments?post=3783"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts\/3783\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/media\/35994"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/media?parent=3783"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/categories?post=3783"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/tags?post=3783"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}