title: Is this a standard library error, or mine?
body: <p>When I try to compile a program I'm working on, I get the following error:</p>
  
  <pre><code>In file included from /usr/include/c++/4.8.1/bits/stl_algobase.h:64:0,
                   from /usr/include/c++/4.8.1/bits/char_traits.h:39,
                   from /usr/include/c++/4.8.1/string:40,
                   from main.cpp:1:
  /usr/include/c++/4.8.1/bits/stl_pair.h: In instantiation of ‘struct std::pair&lt;trie&lt;std::basic_string&lt;char&gt; &gt;::iterator, bool&gt;’:
  main.cpp:7:15:   required from here
  /usr/include/c++/4.8.1/bits/stl_pair.h:127:17: error: ‘constexpr std::pair&lt;_T1, _T2&gt;::pair(const std::pair&lt;_T1, _T2&gt;&amp;) [with _T1 = trie&lt;std::basic_string&lt;char&gt; &gt;::iterator; _T2 = bool]’ declared to take const reference, but implicit declaration would take non-const
         constexpr pair(const pair&amp;) = default;
                   ^
  </code></pre>
  
  <p>If I'm reading the error correctly, this sounds like a problem with the standard library, although my money is still that it's my fault somehow...</p>
  
  <p>If it matters, here is main.cpp (<code>trie.h</code> is a class I'm working on):</p>
  
  <pre><code>#include &lt;string&gt;
  #include "trie.h"
  
  int main()
  {
      trie&lt;std::string&gt; t;
      t.insert("te");
      trie&lt;std::string&gt; u(std::move(t));
  
      for(auto i: u)
          ;
  }
  </code></pre>
  
  <hr>
  
  <p>EDIT:  And here is the relevant trie code.  <code>trie.h</code>:</p>
  
  <pre><code>template&lt;typename T&gt;
  class trie {
  public:
      // misc. declarations
      class iterator;
      typedef T key_type;
      typedef T value_type;
      typedef size_t size_type;
      typedef iterator const_iterator;
  
      // constructors
      trie(trie&lt;T&gt;* const = nullptr, bool = false);
      trie(const trie&lt;T&gt;&amp;, trie&lt;T&gt;* const = nullptr);
      trie(trie&lt;T&gt;&amp;&amp;);
      template&lt;typename InputIt&gt; trie(InputIt, InputIt, trie&lt;T&gt;* const = nullptr);
  
      // destructor, auto-generated one is fine
      ~trie() =default;
  
      // ...
  
      // other members
      std::pair&lt;iterator,bool&gt; insert(const value_type&amp;);
  
      // ...
  
  private:
      std::map&lt;typename T::value_type, std::unique_ptr&lt;trie&lt;T&gt;&gt;&gt; children;
      trie&lt;T&gt;* parent;
      bool is_leaf = false;
  };
  
  #include "trie_iterator.h"
  
  // ...
  
  template&lt;typename T&gt;
  std::pair&lt;typename trie&lt;T&gt;::iterator,bool&gt; trie&lt;T&gt;::insert(const value_type&amp; value)
  {
    bool inserted = false;
    bool at_leaf = false;
    std::stack&lt;typename iterator::state&gt; parents;
    trie&lt;T&gt;* currentNode{this};
  
    for(const auto&amp; it = value.begin(); it != value.end(); ++it) {
      bool is_last = (it + 1 == value.end());
      auto childIt = currentNode-&gt;children.find(*it);
      if(childIt == currentNode-&gt;children.end()) {
        inserted = true;
        if(is_last) {
          // The sequence is new to this trie, so insert it.
          // It is the last element, so don't create a new trie.
          parents.emplace(
            currentNode,
            currentNode-&gt;children.emplace({*it, {nullptr}}).first
          );
        }
        else {
          // Create a new trie and follow it.
          std::unique_ptr&lt;trie&lt;T&gt;&gt; p(new trie&lt;T&gt;(currentNode));
          currentNode = currentNode-&gt;children.emplace(*it, std::move(p)).first-&gt;second;
        }
      }
      else {
        if(is_last) {
          if(childIt-&gt;second != nullptr) {
            inserted = true;
            at_leaf = true;
            childIt-&gt;second-&gt;is_leaf = true;
          }
          // Done.  Build a return value.
          // TODO
        }
        else {
          if(childIt-&gt;second == nullptr) {
            childIt-&gt;second = new trie&lt;T&gt;(currentNode);
            inserted = true;
          }
          currentNode = childIt-&gt;second;
        }
      }
    }
    // Build pair and return it
    return {{std::move(parents), value, at_leaf}, inserted};
  }
  </code></pre>
  
  <p>I apologize for how lengthy this code is; note that <strong>the implementation of <code>insert</code> doesn't matter; the error appears no matter what</strong>, including with an empty <code>insert</code> body.</p>
  
  <p>And here is the <code>trie&lt;T&gt;::iterator</code> class:</p>
  
  <pre><code>template&lt;typename T&gt;
  class trie&lt;T&gt;::iterator {
      friend class trie&lt;T&gt;;
      // TODO: Either this structure or trie::parent is not needed
      struct state {
          state(const trie&lt;T&gt;* const node, const typename std::map&lt;typename T::value_type, std::unique_ptr&lt;trie&lt;T&gt;&gt;&gt;::const_iterator&amp; node_map_it ) :
              node{node}, node_map_it{node_map_it} {}
          bool operator==(const state&amp; other) const {
              return node == other.node &amp;&amp; node_map_it == other.node_map_it;
          }
          const trie&lt;T&gt;* node;
          typename std::map&lt;typename T::value_type, std::unique_ptr&lt;trie&lt;T&gt;&gt;&gt;::const_iterator node_map_it;
      };
      enum class fall_to {left, right};
  public:
      iterator() =default;
      iterator(trie&lt;T&gt;* node) {
          parents.emplace(node, node-&gt;children.cbegin());
          at_end = (parents.top().node_map_it == parents.top().node-&gt;children.cend());
          at_leaf = parents.top().node-&gt;is_leaf;
          fall_down();
      }
      ~iterator() =default;
      iterator(typename trie&lt;T&gt;::iterator&amp; other) =default;
      iterator(typename trie&lt;T&gt;::iterator&amp;&amp; other) :
          parents{std::move(other.parents)},
          built{std::move(other.built)}
      {}
      iterator&amp; operator=(typename trie&lt;T&gt;::iterator other) {
          swap(*this, other);
          return *this;
      }
  
      void swap(typename trie&lt;T&gt;::iterator&amp; other) {
          std::swap(parents, other.parents);
          std::swap(built, other.built);
      }
      static void swap(typename trie&lt;T&gt;::iterator&amp; a, typename trie&lt;T&gt;::iterator&amp; b) { a.swap(b); }
  
      const T&amp; operator*() const { return built; }
      const T* operator-&gt;() const { return &amp;built; }
  
      void operator++() {
          if(at_leaf)
              at_leaf = false;
          else
              while(++parents.top().node_map_it == parents.top().node-&gt;children.cend())
                  walk_up();
          fall_down();
      }
      void operator--() {
          if(at_leaf)
              walk_up();
          while(parents.top().node_map_it-- == parents.top().node-&gt;children.cbegin()) {
              at_leaf = parents.top().node-&gt;is_leaf;
              if(at_leaf)
                  // No need to fall down.
                  return;
              walk_up();
          }
          fall_down(fall_to::right);
      }
  
      bool operator==(const typename trie&lt;T&gt;::iterator&amp; other) const {
          return parents.top() == other.parents.top() &amp;&amp; at_end == other.at_end;
      }
      bool operator!=(const typename trie&lt;T&gt;::iterator&amp; other) const { return !operator==(other); }
  private:
      iterator(const std::stack&lt;state&gt;&amp; parents, const T&amp; built, bool at_end) :
          parents{parents}, built{built}, at_end{at_end} {}
      void inline fall_down(const enum fall_to fall = fall_to::left) {
          // TODO: This function could possibly be made smaller.
          trie&lt;T&gt;* child;
          if(at_leaf)
              return;
          while((child = parents.top().node_map_it-&gt;second.get()) != nullptr) {
              built.push_back(parents.top().node_map_it-&gt;first);
              if(fall == fall_to::left) {
                  parents.emplace(child, child-&gt;children.cbegin());
                  at_leaf = child-&gt;is_leaf;
                  if(at_leaf)
                      return;
              }
              else // fall_to::right
                  parents.emplace(child, --child-&gt;children.cend());
          }
          // One final push_back to put the final element (the one that has no
          // children) in built.
          built.push_back(parents.top().node_map_it-&gt;first);
      }
      void inline walk_up() {
          built.pop_back();
          parents.pop();
      }
  
      std::stack&lt;state&gt; parents;
      // TODO: we could switch the use of push_back and pop_back for insert and erase
      // using an end iterator, to gain some additional compatibility.
      T built;
      bool at_end;
      bool at_leaf;
  };
  </code></pre>