diff --git a/daemon/table/fib.cpp b/daemon/table/fib.cpp
index c28a695..ee9e733 100644
--- a/daemon/table/fib.cpp
+++ b/daemon/table/fib.cpp
@@ -27,10 +27,25 @@
 #include "pit-entry.hpp"
 #include "measurements-entry.hpp"
 
+#include <boost/concept/assert.hpp>
+#include <boost/concept_check.hpp>
+#include <type_traits>
+
 namespace nfd {
 
 const shared_ptr<fib::Entry> Fib::s_emptyEntry = make_shared<fib::Entry>(Name());
 
+// http://en.cppreference.com/w/cpp/concept/ForwardIterator
+BOOST_CONCEPT_ASSERT((boost::ForwardIterator<Fib::const_iterator>));
+// boost::ForwardIterator follows SGI standard http://www.sgi.com/tech/stl/ForwardIterator.html,
+// which doesn't require DefaultConstructible
+#ifdef HAVE_IS_DEFAULT_CONSTRUCTIBLE
+static_assert(std::is_default_constructible<Fib::const_iterator>::value,
+              "Fib::const_iterator must be default-constructible");
+#else
+BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<Fib::const_iterator>));
+#endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE
+
 Fib::Fib(NameTree& nameTree)
   : m_nameTree(nameTree)
   , m_nItems(0)
diff --git a/daemon/table/fib.hpp b/daemon/table/fib.hpp
index 3a19949..34a2009 100644
--- a/daemon/table/fib.hpp
+++ b/daemon/table/fib.hpp
@@ -95,15 +95,26 @@
 public: // enumeration
   class const_iterator;
 
+  /** \brief returns an iterator pointing to the first FIB entry
+   *  \note Iteration order is implementation-specific and is undefined
+   *  \note The returned iterator may get invalidated if FIB or another NameTree-based
+   *        table is modified
+   */
   const_iterator
   begin() const;
 
+  /** \brief returns an iterator referring to the past-the-end FIB entry
+   *  \note The returned iterator may get invalidated if FIB or another NameTree-based
+   *        table is modified
+   */
   const_iterator
   end() const;
 
-  class const_iterator : public std::iterator<std::forward_iterator_tag, fib::Entry>
+  class const_iterator : public std::iterator<std::forward_iterator_tag, const fib::Entry>
   {
   public:
+    const_iterator() = default;
+
     explicit
     const_iterator(const NameTree::const_iterator& it);
 
@@ -193,7 +204,7 @@
 inline const fib::Entry&
 Fib::const_iterator::operator*() const
 {
-  return *(m_nameTreeIterator->getFibEntry());
+  return *this->operator->();
 }
 
 inline shared_ptr<fib::Entry>
diff --git a/daemon/table/name-tree.cpp b/daemon/table/name-tree.cpp
index d7cb544..3ac469d 100644
--- a/daemon/table/name-tree.cpp
+++ b/daemon/table/name-tree.cpp
@@ -27,10 +27,25 @@
 #include "core/logger.hpp"
 #include "core/city-hash.hpp"
 
+#include <boost/concept/assert.hpp>
+#include <boost/concept_check.hpp>
+#include <type_traits>
+
 namespace nfd {
 
 NFD_LOG_INIT("NameTree");
 
+// http://en.cppreference.com/w/cpp/concept/ForwardIterator
+BOOST_CONCEPT_ASSERT((boost::ForwardIterator<NameTree::const_iterator>));
+// boost::ForwardIterator follows SGI standard http://www.sgi.com/tech/stl/ForwardIterator.html,
+// which doesn't require DefaultConstructible
+#ifdef HAVE_IS_DEFAULT_CONSTRUCTIBLE
+static_assert(std::is_default_constructible<NameTree::const_iterator>::value,
+              "NameTree::const_iterator must be default-constructible");
+#else
+BOOST_CONCEPT_ASSERT((boost::DefaultConstructible<NameTree::const_iterator>));
+#endif // HAVE_IS_DEFAULT_CONSTRUCTIBLE
+
 namespace name_tree {
 
 class Hash32
@@ -569,12 +584,17 @@
   output << "--------------------------\n";
 }
 
+NameTree::const_iterator::const_iterator()
+  : m_nameTree(nullptr)
+{
+}
+
 NameTree::const_iterator::const_iterator(NameTree::IteratorType type,
                             const NameTree& nameTree,
                             shared_ptr<name_tree::Entry> entry,
                             const name_tree::EntrySelector& entrySelector,
                             const name_tree::EntrySubTreeSelector& entrySubTreeSelector)
-  : m_nameTree(nameTree)
+  : m_nameTree(&nameTree)
   , m_entry(entry)
   , m_subTreeRoot(entry)
   , m_entrySelector(make_shared<name_tree::EntrySelector>(entrySelector))
@@ -590,7 +610,7 @@
 {
   NFD_LOG_TRACE("const_iterator::operator++()");
 
-  BOOST_ASSERT(m_entry != m_nameTree.m_end);
+  BOOST_ASSERT(m_entry != m_nameTree->m_end);
 
   if (m_type == FULL_ENUMERATE_TYPE) // fullEnumerate
     {
@@ -608,12 +628,12 @@
 
       // process other buckets
 
-      for (int newLocation = m_entry->m_hash % m_nameTree.m_nBuckets + 1;
-           newLocation < static_cast<int>(m_nameTree.m_nBuckets);
+      for (int newLocation = m_entry->m_hash % m_nameTree->m_nBuckets + 1;
+           newLocation < static_cast<int>(m_nameTree->m_nBuckets);
            ++newLocation)
         {
           // process each bucket
-          name_tree::Node* node = m_nameTree.m_buckets[newLocation];
+          name_tree::Node* node = m_nameTree->m_buckets[newLocation];
           while (node != 0)
             {
               m_entry = node->m_entry;
@@ -627,7 +647,7 @@
         }
       BOOST_VERIFY(isFound == false);
       // Reach to the end()
-      m_entry = m_nameTree.m_end;
+      m_entry = m_nameTree->m_end;
       return *this;
     }
 
@@ -727,7 +747,7 @@
             }
         }
 
-      m_entry = m_nameTree.m_end;
+      m_entry = m_nameTree->m_end;
       return *this;
     }
 
@@ -745,7 +765,7 @@
         }
 
       // Reach to the end (Root)
-      m_entry = m_nameTree.m_end;
+      m_entry = m_nameTree->m_end;
       return *this;
     }
 
diff --git a/daemon/table/name-tree.hpp b/daemon/table/name-tree.hpp
index 6e936d0..8d4e437 100644
--- a/daemon/table/name-tree.hpp
+++ b/daemon/table/name-tree.hpp
@@ -184,6 +184,8 @@
    *    ...
    *  }
    *  \endcode
+   *  \note Iteration order is implementation-specific and is undefined
+   *  \note The returned iterator may get invalidated when NameTree is modified
    */
   boost::iterator_range<const_iterator>
   findAllMatches(const Name& prefix,
@@ -201,6 +203,8 @@
    *    ...
    *  }
    *  \endcode
+   *  \note Iteration order is implementation-specific and is undefined
+   *  \note The returned iterator may get invalidated when NameTree is modified
    */
   boost::iterator_range<const_iterator>
   fullEnumerate(const name_tree::EntrySelector& entrySelector = name_tree::AnyEntry()) const;
@@ -216,15 +220,25 @@
    *    ...
    *  }
    *  \endcode
+   *  \note Iteration order is implementation-specific and is undefined
+   *  \note The returned iterator may get invalidated when NameTree is modified
    */
   boost::iterator_range<const_iterator>
   partialEnumerate(const Name& prefix,
                    const name_tree::EntrySubTreeSelector& entrySubTreeSelector =
                          name_tree::AnyEntrySubTree()) const;
 
+  /** \brief Get an iterator pointing to the first NameTree entry
+   *  \note Iteration order is implementation-specific and is undefined
+   *  \note The returned iterator may get invalidated when NameTree is modified
+   */
   const_iterator
   begin() const;
 
+  /** \brief Get an iterator referring to the past-the-end FIB entry
+   *  \note Iteration order is implementation-specific and is undefined
+   *  \note The returned iterator may get invalidated when NameTree is modified
+   */
   const_iterator
   end() const;
 
@@ -234,11 +248,13 @@
     FIND_ALL_MATCHES_TYPE
   };
 
-  class const_iterator : public std::iterator<std::forward_iterator_tag, name_tree::Entry>
+  class const_iterator : public std::iterator<std::forward_iterator_tag, const name_tree::Entry>
   {
   public:
     friend class NameTree;
 
+    const_iterator();
+
     const_iterator(NameTree::IteratorType type,
       const NameTree& nameTree,
       shared_ptr<name_tree::Entry> entry,
@@ -266,7 +282,7 @@
     operator!=(const const_iterator& other) const;
 
   private:
-    const NameTree&                             m_nameTree;
+    const NameTree*                             m_nameTree;
     shared_ptr<name_tree::Entry>                m_entry;
     shared_ptr<name_tree::Entry>                m_subTreeRoot;
     shared_ptr<name_tree::EntrySelector>        m_entrySelector;