title: Higher order function « filter » in C++
body: <p>I wanted to write a higher order function <code>filter</code> with C++. The code I have come up with so far is as follows:</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;string&gt;
  #include &lt;functional&gt;
  #include &lt;algorithm&gt;
  #include &lt;vector&gt;
  #include &lt;list&gt;
  #include &lt;iterator&gt;
  
  using namespace std;
  
  bool isOdd(int const i) {
    return i % 2 != 0;
  }
  
  template &lt;
    template &lt;class, class&gt; class Container,
    class Predicate,
    class Allocator,
    class A
  &gt;
  Container&lt;A, Allocator&gt; filter(Container&lt;A, Allocator&gt; const &amp; container, Predicate const &amp; pred) {
    Container&lt;A, Allocator&gt; filtered(container);
    container.erase(remove_if(filtered.begin(), filtered.end(), pred), filtered.end());
    return filtered;
  }
  
  int main() {
    int const a[] = {23, 12, 78, 21, 97, 64};
    vector&lt;int const&gt; const v(a, a + 6);
    vector&lt;int const&gt; const filtered = filter(v, isOdd);
    copy(filtered.begin(), filtered.end(), ostream_iterator&lt;int const&gt;(cout, " "));
  }
  </code></pre>
  
  <p>However on compiling this code, I get the following error messages that I am unable to understand and hence get rid of:</p>
  
  <pre><code>/usr/include/c++/4.3/ext/new_allocator.h: In instantiation of ‘__gnu_cxx::new_allocator&lt;const int&gt;’:
  /usr/include/c++/4.3/bits/allocator.h:84:   instantiated from ‘std::allocator&lt;const int&gt;’
  /usr/include/c++/4.3/bits/stl_vector.h:75:   instantiated from ‘std::_Vector_base&lt;const int, std::allocator&lt;const int&gt; &gt;’
  /usr/include/c++/4.3/bits/stl_vector.h:176:   instantiated from ‘std::vector&lt;const int, std::allocator&lt;const int&gt; &gt;’
  Filter.cpp:29:   instantiated from here
  /usr/include/c++/4.3/ext/new_allocator.h:82: error: ‘const _Tp* __gnu_cxx::new_allocator&lt;_Tp&gt;::address(const _Tp&amp;) const [with _Tp = const int]’ cannot be overloaded
  /usr/include/c++/4.3/ext/new_allocator.h:79: error: with ‘_Tp* __gnu_cxx::new_allocator&lt;_Tp&gt;::address(_Tp&amp;) const [with _Tp = const int]’
  Filter.cpp: In function ‘Container&lt;A, Allocator&gt; filter(const Container&lt;A, Allocator&gt;&amp;, const Predicate&amp;) [with Container = std::vector, Predicate = bool ()(int), Allocator = std::allocator&lt;const int&gt;, A = const int]’:
  Filter.cpp:30:   instantiated from here
  Filter.cpp:23: error: passing ‘const std::vector&lt;const int, std::allocator&lt;const int&gt; &gt;’ as ‘this’ argument of ‘__gnu_cxx::__normal_iterator&lt;typename std::_Vector_base&lt;_Tp, _Alloc&gt;::_Tp_alloc_type::pointer, std::vector&lt;_Tp, _Alloc&gt; &gt; std::vector&lt;_Tp, _Alloc&gt;::erase(__gnu_cxx::__normal_iterator&lt;typename std::_Vector_base&lt;_Tp, _Alloc&gt;::_Tp_alloc_type::pointer, std::vector&lt;_Tp, _Alloc&gt; &gt;, __gnu_cxx::__normal_iterator&lt;typename std::_Vector_base&lt;_Tp, _Alloc&gt;::_Tp_alloc_type::pointer, std::vector&lt;_Tp, _Alloc&gt; &gt;) [with _Tp = const int, _Alloc = std::allocator&lt;const int&gt;]’ discards qualifiers
  /usr/include/c++/4.3/bits/stl_algo.h: In function ‘_FIter std::remove_if(_FIter, _FIter, _Predicate) [with _FIter = __gnu_cxx::__normal_iterator&lt;const int*, std::vector&lt;const int, std::allocator&lt;const int&gt; &gt; &gt;, _Predicate = bool (*)(int)]’:
  Filter.cpp:23:   instantiated from ‘Container&lt;A, Allocator&gt; filter(const Container&lt;A, Allocator&gt;&amp;, const Predicate&amp;) [with Container = std::vector, Predicate = bool ()(int), Allocator = std::allocator&lt;const int&gt;, A = const int]’
  Filter.cpp:30:   instantiated from here
  /usr/include/c++/4.3/bits/stl_algo.h:821: error: assignment of read-only location ‘__result.__gnu_cxx::__normal_iterator&lt;_Iterator, _Container&gt;::operator* [with _Iterator = const int*, _Container = std::vector&lt;const int, std::allocator&lt;const int&gt; &gt;]()’
  /usr/include/c++/4.3/ext/new_allocator.h: In member function ‘void __gnu_cxx::new_allocator&lt;_Tp&gt;::deallocate(_Tp*, size_t) [with _Tp = const int]’:
  /usr/include/c++/4.3/bits/stl_vector.h:150:   instantiated from ‘void std::_Vector_base&lt;_Tp, _Alloc&gt;::_M_deallocate(_Tp*, size_t) [with _Tp = const int, _Alloc = std::allocator&lt;const int&gt;]’
  /usr/include/c++/4.3/bits/stl_vector.h:136:   instantiated from ‘std::_Vector_base&lt;_Tp, _Alloc&gt;::~_Vector_base() [with _Tp = const int, _Alloc = std::allocator&lt;const int&gt;]’
  /usr/include/c++/4.3/bits/stl_vector.h:286:   instantiated from ‘std::vector&lt;_Tp, _Alloc&gt;::vector(_InputIterator, _InputIterator, const _Alloc&amp;) [with _InputIterator = const int*, _Tp = const int, _Alloc = std::allocator&lt;const int&gt;]’
  Filter.cpp:29:   instantiated from here
  /usr/include/c++/4.3/ext/new_allocator.h:98: error: invalid conversion from ‘const void*’ to ‘void*’
  /usr/include/c++/4.3/ext/new_allocator.h:98: error:   initializing argument 1 of ‘void operator delete(void*)’
  /usr/include/c++/4.3/bits/stl_algobase.h: In function ‘_OI std::__copy_move_a(_II, _II, _OI) [with bool _IsMove = false, _II = const int*, _OI = const int*]’:
  /usr/include/c++/4.3/bits/stl_algobase.h:435:   instantiated from ‘_OI std::__copy_move_a2(_II, _II, _OI) [with bool _IsMove = false, _II = __gnu_cxx::__normal_iterator&lt;const int*, std::vector&lt;const int, std::allocator&lt;const int&gt; &gt; &gt;, _OI = __gnu_cxx::__normal_iterator&lt;const int*, std::vector&lt;const int, std::allocator&lt;const int&gt; &gt; &gt;]’
  /usr/include/c++/4.3/bits/stl_algobase.h:466:   instantiated from ‘_OI std::copy(_II, _II, _OI) [with _II = __gnu_cxx::__normal_iterator&lt;const int*, std::vector&lt;const int, std::allocator&lt;const int&gt; &gt; &gt;, _OI = __gnu_cxx::__normal_iterator&lt;const int*, std::vector&lt;const int, std::allocator&lt;const int&gt; &gt; &gt;]’
  /usr/include/c++/4.3/bits/vector.tcc:136:   instantiated from ‘__gnu_cxx::__normal_iterator&lt;typename std::_Vector_base&lt;_Tp, _Alloc&gt;::_Tp_alloc_type::pointer, std::vector&lt;_Tp, _Alloc&gt; &gt; std::vector&lt;_Tp, _Alloc&gt;::erase(__gnu_cxx::__normal_iterator&lt;typename std::_Vector_base&lt;_Tp, _Alloc&gt;::_Tp_alloc_type::pointer, std::vector&lt;_Tp, _Alloc&gt; &gt;, __gnu_cxx::__normal_iterator&lt;typename std::_Vector_base&lt;_Tp, _Alloc&gt;::_Tp_alloc_type::pointer, std::vector&lt;_Tp, _Alloc&gt; &gt;) [with _Tp = const int, _Alloc = std::allocator&lt;const int&gt;]’
  Filter.cpp:23:   instantiated from ‘Container&lt;A, Allocator&gt; filter(const Container&lt;A, Allocator&gt;&amp;, const Predicate&amp;) [with Container = std::vector, Predicate = bool ()(int), Allocator = std::allocator&lt;const int&gt;, A = const int]’
  Filter.cpp:30:   instantiated from here
  /usr/include/c++/4.3/bits/stl_algobase.h:396: error: no matching function for call to ‘std::__copy_move&lt;false, true, std::random_access_iterator_tag&gt;::__copy_m(const int*&amp;, const int*&amp;, const int*&amp;)’
  </code></pre>
  
  <p>Please tell me what I am doing wrong here and what is the correct way to achieve the kind of higher order polymorphism I want.</p>
  
  <p>Thanks.</p>
  
  <p><strong>EDIT:</strong></p>
  
  <p>Thank you, everyone. Here's the new code I got after applying your suggestions (and it works now, yay!)</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;string&gt;
  #include &lt;functional&gt;
  #include &lt;algorithm&gt;
  #include &lt;vector&gt;
  #include &lt;list&gt;
  #include &lt;iterator&gt;
  
  using namespace std;
  
  bool isOdd(int const i) {
    return i % 2 != 0;
  }
  
  template &lt;
    template &lt;typename, typename&gt; class Container,
    typename Predicate,
    typename Allocator,
    typename A
  &gt;
  Container&lt;A, Allocator&gt; filter(Container&lt;A, Allocator&gt; const &amp; container, Predicate const &amp; pred) {
    Container&lt;A, Allocator&gt; filtered(container);
    filtered.erase(remove_if(filtered.begin(), filtered.end(), pred), filtered.end());
    return filtered;
  }
  
  int main() {
    int a[] = {23, 12, 78, 21, 97, 64};
    vector&lt;int&gt; v(a, a + 6);
    vector&lt;int&gt; filtered = filter(v, isOdd);
    copy(filtered.begin(), filtered.end(), ostream_iterator&lt;int&gt;(cout, " "));
  }
  </code></pre>