diff --git a/ndn-cxx/face.cpp b/ndn-cxx/face.cpp
index a225a9d..70fd8db 100644
--- a/ndn-cxx/face.cpp
+++ b/ndn-cxx/face.cpp
@@ -179,7 +179,7 @@
                       const NackCallback& afterNacked,
                       const TimeoutCallback& afterTimeout)
 {
-  auto id = m_impl->generatePendingInterestId();
+  auto id = m_impl->m_pendingInterestTable.allocateId();
 
   auto interest2 = make_shared<Interest>(interest);
   interest2->getNonce();
@@ -188,14 +188,14 @@
     impl->asyncExpressInterest(id, interest2, afterSatisfied, afterNacked, afterTimeout);
   } IO_CAPTURE_WEAK_IMPL_END
 
-  return PendingInterestHandle(*this, id);
+  return PendingInterestHandle(*this, reinterpret_cast<const PendingInterestId*>(id));
 }
 
 void
 Face::cancelPendingInterest(const PendingInterestId* pendingInterestId)
 {
   IO_CAPTURE_WEAK_IMPL(post) {
-    impl->asyncRemovePendingInterest(pendingInterestId);
+    impl->asyncRemovePendingInterest(reinterpret_cast<RecordId>(pendingInterestId));
   } IO_CAPTURE_WEAK_IMPL_END
 }
 
@@ -230,52 +230,44 @@
 }
 
 RegisteredPrefixHandle
-Face::setInterestFilter(const InterestFilter& interestFilter,
-                        const InterestCallback& onInterest,
+Face::setInterestFilter(const InterestFilter& filter, const InterestCallback& onInterest,
                         const RegisterPrefixFailureCallback& onFailure,
-                        const security::SigningInfo& signingInfo,
-                        uint64_t flags)
+                        const security::SigningInfo& signingInfo, uint64_t flags)
 {
-  return setInterestFilter(interestFilter, onInterest, nullptr, onFailure, signingInfo, flags);
+  return setInterestFilter(filter, onInterest, nullptr, onFailure, signingInfo, flags);
 }
 
 RegisteredPrefixHandle
-Face::setInterestFilter(const InterestFilter& interestFilter,
-                        const InterestCallback& onInterest,
+Face::setInterestFilter(const InterestFilter& filter, const InterestCallback& onInterest,
                         const RegisterPrefixSuccessCallback& onSuccess,
                         const RegisterPrefixFailureCallback& onFailure,
-                        const security::SigningInfo& signingInfo,
-                        uint64_t flags)
+                        const security::SigningInfo& signingInfo, uint64_t flags)
 {
-  auto filter = make_shared<InterestFilterRecord>(interestFilter, onInterest);
-
   nfd::CommandOptions options;
   options.setSigningInfo(signingInfo);
 
-  auto id = m_impl->registerPrefix(interestFilter.getPrefix(), filter,
-                                   onSuccess, onFailure, flags, options);
-  return RegisteredPrefixHandle(*this, id);
+  auto id = m_impl->registerPrefix(filter.getPrefix(), onSuccess, onFailure, flags, options,
+                                   filter, onInterest);
+  return RegisteredPrefixHandle(*this, reinterpret_cast<const RegisteredPrefixId*>(id));
 }
 
 InterestFilterHandle
-Face::setInterestFilter(const InterestFilter& interestFilter,
-                        const InterestCallback& onInterest)
+Face::setInterestFilter(const InterestFilter& filter, const InterestCallback& onInterest)
 {
-  auto filter = make_shared<InterestFilterRecord>(interestFilter, onInterest);
+  auto id = m_impl->m_interestFilterTable.allocateId();
 
   IO_CAPTURE_WEAK_IMPL(post) {
-    impl->asyncSetInterestFilter(filter);
+    impl->asyncSetInterestFilter(id, filter, onInterest);
   } IO_CAPTURE_WEAK_IMPL_END
 
-  auto id = reinterpret_cast<const InterestFilterId*>(filter.get());
-  return InterestFilterHandle(*this, id);
+  return InterestFilterHandle(*this, reinterpret_cast<const InterestFilterId*>(id));
 }
 
 void
 Face::clearInterestFilter(const InterestFilterId* interestFilterId)
 {
   IO_CAPTURE_WEAK_IMPL(post) {
-    impl->asyncUnsetInterestFilter(interestFilterId);
+    impl->asyncUnsetInterestFilter(reinterpret_cast<RecordId>(interestFilterId));
   } IO_CAPTURE_WEAK_IMPL_END
 }
 
@@ -289,8 +281,8 @@
   nfd::CommandOptions options;
   options.setSigningInfo(signingInfo);
 
-  auto id = m_impl->registerPrefix(prefix, nullptr, onSuccess, onFailure, flags, options);
-  return RegisteredPrefixHandle(*this, id);
+  auto id = m_impl->registerPrefix(prefix, onSuccess, onFailure, flags, options, nullopt, nullptr);
+  return RegisteredPrefixHandle(*this, reinterpret_cast<const RegisteredPrefixId*>(id));
 }
 
 void
@@ -299,7 +291,8 @@
                            const UnregisterPrefixFailureCallback& onFailure)
 {
   IO_CAPTURE_WEAK_IMPL(post) {
-    impl->asyncUnregisterPrefix(registeredPrefixId, onSuccess, onFailure);
+    impl->asyncUnregisterPrefix(reinterpret_cast<RecordId>(registeredPrefixId),
+                                onSuccess, onFailure);
   } IO_CAPTURE_WEAK_IMPL_END
 }
 
diff --git a/ndn-cxx/face.hpp b/ndn-cxx/face.hpp
index 734165d..c14e556 100644
--- a/ndn-cxx/face.hpp
+++ b/ndn-cxx/face.hpp
@@ -273,18 +273,17 @@
    * different callbacks, use one registerPrefix call, followed (in onSuccess callback) by
    * a series of setInterestFilter calls.
    *
-   * @param interestFilter Interest filter (prefix part will be registered with the forwarder)
-   * @param onInterest     A callback to be called when a matching interest is received
-   * @param onFailure      A callback to be called when prefixRegister command fails
-   * @param flags          (optional) RIB flags
-   * @param signingInfo    (optional) Signing parameters.  When omitted, a default parameters
-   *                       used in the signature will be used.
+   * @param filter      Interest filter (prefix part will be registered with the forwarder)
+   * @param onInterest  A callback to be called when a matching interest is received
+   * @param onFailure   A callback to be called when prefixRegister command fails
+   * @param signingInfo Signing parameters. When omitted, a default parameters used in the
+   *                    signature will be used.
+   * @param flags       Prefix registration flags
    *
-   * @return A handle for unregistering the prefix.
+   * @return A handle for unregistering the prefix and unsetting the Interest filter.
    */
   RegisteredPrefixHandle
-  setInterestFilter(const InterestFilter& interestFilter,
-                    const InterestCallback& onInterest,
+  setInterestFilter(const InterestFilter& filter, const InterestCallback& onInterest,
                     const RegisterPrefixFailureCallback& onFailure,
                     const security::SigningInfo& signingInfo = security::SigningInfo(),
                     uint64_t flags = nfd::ROUTE_FLAG_CHILD_INHERIT);
@@ -299,19 +298,18 @@
    * different callbacks, use one registerPrefix call, followed (in onSuccess callback) by
    * a series of setInterestFilter calls.
    *
-   * @param interestFilter Interest filter (prefix part will be registered with the forwarder)
-   * @param onInterest     A callback to be called when a matching interest is received
-   * @param onSuccess      A callback to be called when prefixRegister command succeeds
-   * @param onFailure      A callback to be called when prefixRegister command fails
-   * @param flags          (optional) RIB flags
-   * @param signingInfo    (optional) Signing parameters.  When omitted, a default parameters
-   *                       used in the signature will be used.
+   * @param filter      Interest filter (prefix part will be registered with the forwarder)
+   * @param onInterest  A callback to be called when a matching interest is received
+   * @param onSuccess   A callback to be called when prefixRegister command succeeds
+   * @param onFailure   A callback to be called when prefixRegister command fails
+   * @param signingInfo Signing parameters. When omitted, a default parameters used in the
+   *                    signature will be used.
+   * @param flags       Prefix registration flags
    *
-   * @return A handle for unregistering the prefix.
+   * @return A handle for unregistering the prefix and unsetting the Interest filter.
    */
   RegisteredPrefixHandle
-  setInterestFilter(const InterestFilter& interestFilter,
-                    const InterestCallback& onInterest,
+  setInterestFilter(const InterestFilter& filter, const InterestCallback& onInterest,
                     const RegisterPrefixSuccessCallback& onSuccess,
                     const RegisterPrefixFailureCallback& onFailure,
                     const security::SigningInfo& signingInfo = security::SigningInfo(),
@@ -320,7 +318,7 @@
   /**
    * @brief Set InterestFilter to dispatch incoming matching interest to onInterest callback
    *
-   * @param interestFilter Interest
+   * @param filter     Interest filter
    * @param onInterest A callback to be called when a matching interest is received
    *
    * This method modifies library's FIB only, and does not register the prefix with the
@@ -330,8 +328,7 @@
    * @return A handle for unsetting the Interest filter.
    */
   InterestFilterHandle
-  setInterestFilter(const InterestFilter& interestFilter,
-                    const InterestCallback& onInterest);
+  setInterestFilter(const InterestFilter& filter, const InterestCallback& onInterest);
 
   /**
    * @brief Register prefix with the connected NDN forwarder
@@ -343,8 +340,8 @@
    * @param prefix      A prefix to register with the connected NDN forwarder
    * @param onSuccess   A callback to be called when prefixRegister command succeeds
    * @param onFailure   A callback to be called when prefixRegister command fails
-   * @param signingInfo (optional) Signing parameters.  When omitted, a default parameters
-   *                    used in the signature will be used.
+   * @param signingInfo Signing parameters. When omitted, a default parameters used in the
+   *                    signature will be used.
    * @param flags       Prefix registration flags
    *
    * @return A handle for unregistering the prefix.
diff --git a/ndn-cxx/impl/container-with-on-empty-signal.hpp b/ndn-cxx/impl/container-with-on-empty-signal.hpp
deleted file mode 100644
index b40b19e..0000000
--- a/ndn-cxx/impl/container-with-on-empty-signal.hpp
+++ /dev/null
@@ -1,108 +0,0 @@
-/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
-/*
- * Copyright (c) 2013-2018 Regents of the University of California.
- *
- * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
- *
- * ndn-cxx library is free software: you can redistribute it and/or modify it under the
- * terms of the GNU Lesser General Public License as published by the Free Software
- * Foundation, either version 3 of the License, or (at your option) any later version.
- *
- * ndn-cxx library is distributed in the hope that it will be useful, but WITHOUT ANY
- * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
- * PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more details.
- *
- * You should have received copies of the GNU General Public License and GNU Lesser
- * General Public License along with ndn-cxx, e.g., in COPYING.md file.  If not, see
- * <http://www.gnu.org/licenses/>.
- *
- * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
- */
-
-#ifndef NDN_IMPL_CONTAINER_WITH_ON_EMPTY_SIGNAL_HPP
-#define NDN_IMPL_CONTAINER_WITH_ON_EMPTY_SIGNAL_HPP
-
-#include "ndn-cxx/detail/common.hpp"
-#include "ndn-cxx/util/signal.hpp"
-
-namespace ndn {
-
-/**
- * @brief A container that emits onEmpty signal when it becomes empty
- */
-template<class T>
-class ContainerWithOnEmptySignal
-{
-public:
-  typedef std::list<T> Base;
-  typedef typename Base::value_type value_type;
-  typedef typename Base::iterator iterator;
-
-  iterator
-  begin()
-  {
-    return m_container.begin();
-  }
-
-  iterator
-  end()
-  {
-    return m_container.end();
-  }
-
-  size_t
-  size()
-  {
-    return m_container.size();
-  }
-
-  bool
-  empty()
-  {
-    return m_container.empty();
-  }
-
-  iterator
-  erase(iterator item)
-  {
-    iterator next = m_container.erase(item);
-    if (empty()) {
-      this->onEmpty();
-    }
-    return next;
-  }
-
-  void
-  clear()
-  {
-    m_container.clear();
-    this->onEmpty();
-  }
-
-  std::pair<iterator, bool>
-  insert(const value_type& value)
-  {
-    return {m_container.insert(end(), value), true};
-  }
-
-  template<class Predicate>
-  void remove_if(Predicate p)
-  {
-    m_container.remove_if(p);
-    if (empty()) {
-      this->onEmpty();
-    }
-  }
-
-public:
-  Base m_container;
-
-  /**
-   * @brief Signal to be fired when container becomes empty
-   */
-  util::Signal<ContainerWithOnEmptySignal<T>> onEmpty;
-};
-
-} // namespace ndn
-
-#endif // NDN_IMPL_CONTAINER_WITH_ON_EMPTY_SIGNAL_HPP
diff --git a/ndn-cxx/impl/face-impl.hpp b/ndn-cxx/impl/face-impl.hpp
index e8219ed..4a9c56a 100644
--- a/ndn-cxx/impl/face-impl.hpp
+++ b/ndn-cxx/impl/face-impl.hpp
@@ -23,7 +23,6 @@
 #define NDN_IMPL_FACE_IMPL_HPP
 
 #include "ndn-cxx/face.hpp"
-#include "ndn-cxx/impl/container-with-on-empty-signal.hpp"
 #include "ndn-cxx/impl/lp-field-tag.hpp"
 #include "ndn-cxx/impl/pending-interest.hpp"
 #include "ndn-cxx/impl/registered-prefix.hpp"
@@ -59,15 +58,14 @@
 class Face::Impl : noncopyable
 {
 public:
-  using PendingInterestTable = ContainerWithOnEmptySignal<shared_ptr<PendingInterest>>;
-  using InterestFilterTable = std::list<shared_ptr<InterestFilterRecord>>;
-  using RegisteredPrefixTable = ContainerWithOnEmptySignal<shared_ptr<RegisteredPrefix>>;
+  using PendingInterestTable = RecordContainer<PendingInterest>;
+  using InterestFilterTable = RecordContainer<InterestFilterRecord>;
+  using RegisteredPrefixTable = RecordContainer<RegisteredPrefix>;
 
   explicit
   Impl(Face& face)
     : m_face(face)
     , m_scheduler(m_face.getIoService())
-    , m_lastPendingInterestId(0)
   {
     auto postOnEmptyPitOrNoRegisteredPrefixes = [this] {
       this->m_face.getIoService().post([this] { this->onEmptyPitOrNoRegisteredPrefixes(); });
@@ -82,16 +80,8 @@
   }
 
 public: // consumer
-  const PendingInterestId*
-  generatePendingInterestId()
-  {
-    auto id = ++m_lastPendingInterestId;
-    return reinterpret_cast<const PendingInterestId*>(id);
-  }
-
   void
-  asyncExpressInterest(const PendingInterestId* id,
-                       shared_ptr<const Interest> interest,
+  asyncExpressInterest(RecordId id, shared_ptr<const Interest> interest,
                        const DataCallback& afterSatisfied,
                        const NackCallback& afterNacked,
                        const TimeoutCallback& afterTimeout)
@@ -100,28 +90,23 @@
     this->ensureConnected(true);
 
     const Interest& interest2 = *interest;
-    auto i = m_pendingInterestTable.insert(make_shared<PendingInterest>(
-      id, std::move(interest), afterSatisfied, afterNacked, afterTimeout, ref(m_scheduler))).first;
-    // In dispatchInterest, an InterestCallback may respond with Data right away and delete
-    // the PendingInterestTable entry. shared_ptr is retained to ensure PendingInterest instance
-    // remains valid in this case.
-    shared_ptr<PendingInterest> entry = *i;
-    entry->setDeleter([this, i] { m_pendingInterestTable.erase(i); });
+    auto& entry = m_pendingInterestTable.put(id, std::move(interest), afterSatisfied, afterNacked,
+                                             afterTimeout, ref(m_scheduler));
 
     lp::Packet lpPacket;
     addFieldFromTag<lp::NextHopFaceIdField, lp::NextHopFaceIdTag>(lpPacket, interest2);
     addFieldFromTag<lp::CongestionMarkField, lp::CongestionMarkTag>(lpPacket, interest2);
 
-    entry->recordForwarding();
+    entry.recordForwarding();
     m_face.m_transport->send(finishEncoding(std::move(lpPacket), interest2.wireEncode(),
                                             'I', interest2.getName()));
-    dispatchInterest(*entry, interest2);
+    dispatchInterest(entry, interest2);
   }
 
   void
-  asyncRemovePendingInterest(const PendingInterestId* pendingInterestId)
+  asyncRemovePendingInterest(RecordId id)
   {
-    m_pendingInterestTable.remove_if(MatchPendingInterestId(pendingInterestId));
+    m_pendingInterestTable.erase(id);
   }
 
   void
@@ -136,24 +121,22 @@
   satisfyPendingInterests(const Data& data)
   {
     bool hasAppMatch = false, hasForwarderMatch = false;
-    for (auto i = m_pendingInterestTable.begin(); i != m_pendingInterestTable.end(); ) {
-      shared_ptr<PendingInterest> entry = *i;
-      if (!entry->getInterest()->matchesData(data)) {
-        ++i;
-        continue;
+    m_pendingInterestTable.removeIf([&] (PendingInterest& entry) {
+      if (!entry.getInterest()->matchesData(data)) {
+        return false;
       }
+      NDN_LOG_DEBUG("   satisfying " << *entry.getInterest() << " from " << entry.getOrigin());
 
-      NDN_LOG_DEBUG("   satisfying " << *entry->getInterest() << " from " << entry->getOrigin());
-      i = m_pendingInterestTable.erase(i);
-
-      if (entry->getOrigin() == PendingInterestOrigin::APP) {
+      if (entry.getOrigin() == PendingInterestOrigin::APP) {
         hasAppMatch = true;
-        entry->invokeDataCallback(data);
+        entry.invokeDataCallback(data);
       }
       else {
         hasForwarderMatch = true;
       }
-    }
+
+      return true;
+    });
     // if Data matches no pending Interest record, it is sent to the forwarder as unsolicited Data
     return hasForwarderMatch || !hasAppMatch;
   }
@@ -164,29 +147,25 @@
   nackPendingInterests(const lp::Nack& nack)
   {
     optional<lp::Nack> outNack;
-    for (auto i = m_pendingInterestTable.begin(); i != m_pendingInterestTable.end(); ) {
-      shared_ptr<PendingInterest> entry = *i;
-      if (!nack.getInterest().matchesInterest(*entry->getInterest())) {
-        ++i;
-        continue;
+    m_pendingInterestTable.removeIf([&] (PendingInterest& entry) {
+      if (!nack.getInterest().matchesInterest(*entry.getInterest())) {
+        return false;
       }
+      NDN_LOG_DEBUG("   nacking " << *entry.getInterest() << " from " << entry.getOrigin());
 
-      NDN_LOG_DEBUG("   nacking " << *entry->getInterest() << " from " << entry->getOrigin());
-
-      optional<lp::Nack> outNack1 = entry->recordNack(nack);
+      optional<lp::Nack> outNack1 = entry.recordNack(nack);
       if (!outNack1) {
-        ++i;
-        continue;
+        return false;
       }
 
-      if (entry->getOrigin() == PendingInterestOrigin::APP) {
-        entry->invokeNackCallback(*outNack1);
+      if (entry.getOrigin() == PendingInterestOrigin::APP) {
+        entry.invokeNackCallback(*outNack1);
       }
       else {
         outNack = outNack1;
       }
-      i = m_pendingInterestTable.erase(i);
-    }
+      return true;
+    });
     // send "least severe" Nack from any PendingInterest record originated from forwarder, because
     // it is unimportant to consider Nack reason for the unlikely case when forwarder sends multiple
     // Interests to an app in a short while
@@ -195,21 +174,20 @@
 
 public: // producer
   void
-  asyncSetInterestFilter(shared_ptr<InterestFilterRecord> interestFilterRecord)
+  asyncSetInterestFilter(RecordId id, const InterestFilter& filter,
+                         const InterestCallback& onInterest)
   {
-    NDN_LOG_INFO("setting InterestFilter: " << interestFilterRecord->getFilter());
-    m_interestFilterTable.push_back(std::move(interestFilterRecord));
+    NDN_LOG_INFO("setting InterestFilter: " << filter);
+    m_interestFilterTable.put(id, filter, onInterest);
   }
 
   void
-  asyncUnsetInterestFilter(const InterestFilterId* interestFilterId)
+  asyncUnsetInterestFilter(RecordId id)
   {
-    InterestFilterTable::iterator i = std::find_if(m_interestFilterTable.begin(),
-                                                   m_interestFilterTable.end(),
-                                                   MatchInterestFilterId(interestFilterId));
-    if (i != m_interestFilterTable.end()) {
-      NDN_LOG_INFO("unsetting InterestFilter: " << (*i)->getFilter());
-      m_interestFilterTable.erase(i);
+    const InterestFilterRecord* record = m_interestFilterTable.get(id);
+    if (record != nullptr) {
+      NDN_LOG_INFO("unsetting InterestFilter: " << record->getFilter());
+      m_interestFilterTable.erase(id);
     }
   }
 
@@ -217,27 +195,21 @@
   processIncomingInterest(shared_ptr<const Interest> interest)
   {
     const Interest& interest2 = *interest;
-    auto i = m_pendingInterestTable.insert(make_shared<PendingInterest>(
-      std::move(interest), ref(m_scheduler))).first;
-    // In dispatchInterest, an InterestCallback may respond with Data right away and delete
-    // the PendingInterestTable entry. shared_ptr is retained to ensure PendingInterest instance
-    // remains valid in this case.
-    shared_ptr<PendingInterest> entry = *i;
-    entry->setDeleter([this, i] { m_pendingInterestTable.erase(i); });
-
-    this->dispatchInterest(*entry, interest2);
+    auto& entry = m_pendingInterestTable.insert(std::move(interest), ref(m_scheduler));
+    dispatchInterest(entry, interest2);
   }
 
   void
   dispatchInterest(PendingInterest& entry, const Interest& interest)
   {
-    for (const auto& filter : m_interestFilterTable) {
-      if (filter->doesMatch(entry)) {
-        NDN_LOG_DEBUG("   matches " << filter->getFilter());
-        entry.recordForwarding();
-        filter->invokeInterestCallback(interest);
+    m_interestFilterTable.forEach([&] (const InterestFilterRecord& filter) {
+      if (!filter.doesMatch(entry)) {
+        return;
       }
-    }
+      NDN_LOG_DEBUG("   matches " << filter.getFilter());
+      entry.recordForwarding();
+      filter.invokeInterestCallback(interest);
+    });
   }
 
   void
@@ -280,98 +252,76 @@
   }
 
 public: // prefix registration
-  const RegisteredPrefixId*
+  RecordId
   registerPrefix(const Name& prefix,
-                 shared_ptr<InterestFilterRecord> filter,
                  const RegisterPrefixSuccessCallback& onSuccess,
                  const RegisterPrefixFailureCallback& onFailure,
-                 uint64_t flags,
-                 const nfd::CommandOptions& options)
+                 uint64_t flags, const nfd::CommandOptions& options,
+                 const optional<InterestFilter>& filter, const InterestCallback& onInterest)
   {
     NDN_LOG_INFO("registering prefix: " << prefix);
-    auto record = make_shared<RegisteredPrefix>(prefix, filter, options);
+    auto id = m_registeredPrefixTable.allocateId();
 
-    nfd::ControlParameters params;
-    params.setName(prefix);
-    params.setFlags(flags);
     m_face.m_nfdController->start<nfd::RibRegisterCommand>(
-      params,
-      [=] (const nfd::ControlParameters&) { this->afterPrefixRegistered(record, onSuccess); },
+      nfd::ControlParameters().setName(prefix).setFlags(flags),
+      [=] (const nfd::ControlParameters&) {
+        NDN_LOG_INFO("registered prefix: " << prefix);
+
+        RecordId filterId = 0;
+        if (filter) {
+          NDN_LOG_INFO("setting InterestFilter: " << *filter);
+          InterestFilterRecord& filterRecord = m_interestFilterTable.insert(*filter, onInterest);
+          filterId = filterRecord.getId();
+        }
+
+        m_registeredPrefixTable.put(id, prefix, options, filterId);
+
+        if (onSuccess != nullptr) {
+          onSuccess(prefix);
+        }
+      },
       [=] (const nfd::ControlResponse& resp) {
-        NDN_LOG_INFO("register prefix failed: " << record->getPrefix());
-        onFailure(record->getPrefix(), resp.getText());
+        NDN_LOG_INFO("register prefix failed: " << prefix);
+        onFailure(prefix, resp.getText());
       },
       options);
 
-    return reinterpret_cast<const RegisteredPrefixId*>(record.get());
+    return id;
   }
 
   void
-  afterPrefixRegistered(shared_ptr<RegisteredPrefix> registeredPrefix,
-                        const RegisterPrefixSuccessCallback& onSuccess)
-  {
-    NDN_LOG_INFO("registered prefix: " << registeredPrefix->getPrefix());
-    m_registeredPrefixTable.insert(registeredPrefix);
-
-    if (registeredPrefix->getFilter() != nullptr) {
-      // it was a combined operation
-      m_interestFilterTable.push_back(registeredPrefix->getFilter());
-    }
-
-    if (onSuccess != nullptr) {
-      onSuccess(registeredPrefix->getPrefix());
-    }
-  }
-
-  void
-  asyncUnregisterPrefix(const RegisteredPrefixId* registeredPrefixId,
+  asyncUnregisterPrefix(RecordId id,
                         const UnregisterPrefixSuccessCallback& onSuccess,
                         const UnregisterPrefixFailureCallback& onFailure)
   {
-    auto i = std::find_if(m_registeredPrefixTable.begin(),
-                          m_registeredPrefixTable.end(),
-                          MatchRegisteredPrefixId(registeredPrefixId));
-    if (i != m_registeredPrefixTable.end()) {
-      RegisteredPrefix& record = **i;
-      const shared_ptr<InterestFilterRecord>& filter = record.getFilter();
-
-      if (filter != nullptr) {
-        // it was a combined operation
-        m_interestFilterTable.remove(filter);
-      }
-
-      NDN_LOG_INFO("unregistering prefix: " << record.getPrefix());
-
-      nfd::ControlParameters params;
-      params.setName(record.getPrefix());
-      m_face.m_nfdController->start<nfd::RibUnregisterCommand>(
-        params,
-        [=] (const nfd::ControlParameters&) { this->finalizeUnregisterPrefix(i, onSuccess); },
-        [=] (const nfd::ControlResponse& resp) {
-          NDN_LOG_INFO("unregister prefix failed: " << params.getName());
-          onFailure(resp.getText());
-        },
-        record.getCommandOptions());
-    }
-    else {
+    const RegisteredPrefix* record = m_registeredPrefixTable.get(id);
+    if (record == nullptr) {
       if (onFailure != nullptr) {
-        onFailure("Unrecognized PrefixId");
+        onFailure("Unrecognized RegisteredPrefixHandle");
       }
+      return;
     }
 
-    // there cannot be two registered prefixes with the same id
-  }
-
-  void
-  finalizeUnregisterPrefix(RegisteredPrefixTable::iterator item,
-                           const UnregisterPrefixSuccessCallback& onSuccess)
-  {
-    NDN_LOG_INFO("unregistered prefix: " << (*item)->getPrefix());
-    m_registeredPrefixTable.erase(item);
-
-    if (onSuccess != nullptr) {
-      onSuccess();
+    if (record->getFilterId() != 0) {
+      asyncUnsetInterestFilter(record->getFilterId());
     }
+
+    NDN_LOG_INFO("unregistering prefix: " << record->getPrefix());
+    m_face.m_nfdController->start<nfd::RibUnregisterCommand>(
+      nfd::ControlParameters().setName(record->getPrefix()),
+      [=] (const nfd::ControlParameters&) {
+        NDN_LOG_INFO("unregistered prefix: " << record->getPrefix());
+        m_registeredPrefixTable.erase(id);
+
+        if (onSuccess != nullptr) {
+          onSuccess();
+        }
+      },
+      [=] (const nfd::ControlResponse& resp) {
+        NDN_LOG_INFO("unregister prefix failed: " << record->getPrefix());
+        onFailure(resp.getText());
+      },
+      record->getCommandOptions());
   }
 
 public: // IO routine
@@ -427,7 +377,6 @@
   Scheduler m_scheduler;
   scheduler::ScopedEventId m_processEventsTimeoutEvent;
 
-  std::atomic_uintptr_t m_lastPendingInterestId;
   PendingInterestTable m_pendingInterestTable;
   InterestFilterTable m_interestFilterTable;
   RegisteredPrefixTable m_registeredPrefixTable;
diff --git a/ndn-cxx/impl/interest-filter-record.hpp b/ndn-cxx/impl/interest-filter-record.hpp
index a8c7a81..e3c7ea6 100644
--- a/ndn-cxx/impl/interest-filter-record.hpp
+++ b/ndn-cxx/impl/interest-filter-record.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
- * Copyright (c) 2013-2018 Regents of the University of California.
+ * Copyright (c) 2013-2019 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -27,9 +27,16 @@
 namespace ndn {
 
 /**
+ * @brief Opaque type to identify an InterestFilterRecord
+ */
+class InterestFilterId;
+
+static_assert(sizeof(const InterestFilterId*) == sizeof(RecordId), "");
+
+/**
  * @brief associates an InterestFilter with Interest callback
  */
-class InterestFilterRecord : noncopyable
+class InterestFilterRecord : public RecordBase<InterestFilterRecord>
 {
 public:
   /**
@@ -45,9 +52,6 @@
   {
   }
 
-  /**
-   * @return the filter
-   */
   const InterestFilter&
   getFilter() const
   {
@@ -82,33 +86,6 @@
   InterestCallback m_interestCallback;
 };
 
-/**
- * @brief Opaque type to identify an InterestFilterRecord
- */
-class InterestFilterId;
-
-/**
- * @brief Functor to match InterestFilterId
- */
-class MatchInterestFilterId
-{
-public:
-  explicit
-  MatchInterestFilterId(const InterestFilterId* interestFilterId)
-    : m_id(interestFilterId)
-  {
-  }
-
-  bool
-  operator()(const shared_ptr<InterestFilterRecord>& interestFilterId) const
-  {
-    return reinterpret_cast<const InterestFilterId*>(interestFilterId.get()) == m_id;
-  }
-
-private:
-  const InterestFilterId* m_id;
-};
-
 } // namespace ndn
 
 #endif // NDN_IMPL_INTEREST_FILTER_RECORD_HPP
diff --git a/ndn-cxx/impl/pending-interest.hpp b/ndn-cxx/impl/pending-interest.hpp
index a41934e..15cedbc 100644
--- a/ndn-cxx/impl/pending-interest.hpp
+++ b/ndn-cxx/impl/pending-interest.hpp
@@ -25,6 +25,7 @@
 #include "ndn-cxx/data.hpp"
 #include "ndn-cxx/face.hpp"
 #include "ndn-cxx/interest.hpp"
+#include "ndn-cxx/impl/record-container.hpp"
 #include "ndn-cxx/lp/nack.hpp"
 #include "ndn-cxx/util/scheduler.hpp"
 
@@ -35,6 +36,8 @@
  */
 class PendingInterestId;
 
+static_assert(sizeof(const PendingInterestId*) == sizeof(RecordId), "");
+
 /**
  * @brief Indicates where a pending Interest came from
  */
@@ -60,7 +63,7 @@
 /**
  * @brief Stores a pending Interest and associated callbacks
  */
-class PendingInterest : noncopyable
+class PendingInterest : public RecordBase<PendingInterest>
 {
 public:
   /**
@@ -69,14 +72,10 @@
    * The timeout is set based on the current time and InterestLifetime.
    * This class will invoke the timeout callback unless the record is deleted before timeout.
    */
-  PendingInterest(const PendingInterestId* id,
-                  shared_ptr<const Interest> interest,
-                  const DataCallback& dataCallback,
-                  const NackCallback& nackCallback,
-                  const TimeoutCallback& timeoutCallback,
+  PendingInterest(shared_ptr<const Interest> interest, const DataCallback& dataCallback,
+                  const NackCallback& nackCallback, const TimeoutCallback& timeoutCallback,
                   Scheduler& scheduler)
-    : m_id(id)
-    , m_interest(std::move(interest))
+    : m_interest(std::move(interest))
     , m_origin(PendingInterestOrigin::APP)
     , m_dataCallback(dataCallback)
     , m_nackCallback(nackCallback)
@@ -88,25 +87,15 @@
 
   /**
    * @brief Construct a pending Interest record for an Interest from NFD
-   *
-   * @param interest the Interest
-   * @param scheduler Scheduler for scheduling the timeout event
    */
   PendingInterest(shared_ptr<const Interest> interest, Scheduler& scheduler)
-    : m_id(nullptr)
-    , m_interest(std::move(interest))
+    : m_interest(std::move(interest))
     , m_origin(PendingInterestOrigin::FORWARDER)
     , m_nNotNacked(0)
   {
     scheduleTimeoutEvent(scheduler);
   }
 
-  const PendingInterestId*
-  getId() const
-  {
-    return m_id;
-  }
-
   shared_ptr<const Interest>
   getInterest() const
   {
@@ -172,15 +161,6 @@
     }
   }
 
-  /**
-   * @brief Set cleanup function to be invoked when Interest times out
-   */
-  void
-  setDeleter(const std::function<void()>& deleter)
-  {
-    m_deleter = deleter;
-  }
-
 private:
   void
   scheduleTimeoutEvent(Scheduler& scheduler)
@@ -199,12 +179,10 @@
       m_timeoutCallback(*m_interest);
     }
 
-    BOOST_ASSERT(m_deleter);
-    m_deleter();
+    deleteSelf();
   }
 
 private:
-  const PendingInterestId* m_id;
   shared_ptr<const Interest> m_interest;
   PendingInterestOrigin m_origin;
   DataCallback m_dataCallback;
@@ -216,28 +194,6 @@
   std::function<void()> m_deleter;
 };
 
-/**
- * @brief Functor to match PendingInterestId
- */
-class MatchPendingInterestId
-{
-public:
-  explicit
-  MatchPendingInterestId(const PendingInterestId* pendingInterestId)
-    : m_id(pendingInterestId)
-  {
-  }
-
-  bool
-  operator()(const shared_ptr<const PendingInterest>& pendingInterest) const
-  {
-    return pendingInterest->getId() == m_id;
-  }
-
-private:
-  const PendingInterestId* m_id;
-};
-
 } // namespace ndn
 
 #endif // NDN_IMPL_PENDING_INTEREST_HPP
diff --git a/ndn-cxx/impl/record-container.hpp b/ndn-cxx/impl/record-container.hpp
new file mode 100644
index 0000000..d488393
--- /dev/null
+++ b/ndn-cxx/impl/record-container.hpp
@@ -0,0 +1,199 @@
+/* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
+/*
+ * Copyright (c) 2013-2019 Regents of the University of California.
+ *
+ * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
+ *
+ * ndn-cxx library is free software: you can redistribute it and/or modify it under the
+ * terms of the GNU Lesser General Public License as published by the Free Software
+ * Foundation, either version 3 of the License, or (at your option) any later version.
+ *
+ * ndn-cxx library is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
+ * PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more details.
+ *
+ * You should have received copies of the GNU General Public License and GNU Lesser
+ * General Public License along with ndn-cxx, e.g., in COPYING.md file.  If not, see
+ * <http://www.gnu.org/licenses/>.
+ *
+ * See AUTHORS.md for complete list of ndn-cxx authors and contributors.
+ */
+
+#ifndef NDN_IMPL_RECORD_CONTAINER_HPP
+#define NDN_IMPL_RECORD_CONTAINER_HPP
+
+#include "ndn-cxx/detail/common.hpp"
+#include "ndn-cxx/util/signal.hpp"
+
+#include <atomic>
+
+namespace ndn {
+
+using RecordId = uintptr_t;
+
+template<typename T>
+class RecordContainer;
+
+/** \brief Template of PendingInterest, RegisteredPrefix, and InterestFilterRecord.
+ *  \tparam T concrete type
+ */
+template<typename T>
+class RecordBase : noncopyable
+{
+public:
+  RecordId
+  getId() const
+  {
+    BOOST_ASSERT(m_id != 0);
+    return m_id;
+  }
+
+protected:
+  ~RecordBase() = default;
+
+  /** \brief Delete this record from the container.
+   */
+  void
+  deleteSelf()
+  {
+    BOOST_ASSERT(m_container != nullptr);
+    m_container->erase(m_id);
+  }
+
+private:
+  RecordContainer<T>* m_container = nullptr;
+  RecordId m_id = 0;
+  friend RecordContainer<T>;
+};
+
+/** \brief Container of PendingInterest, RegisteredPrefix, or InterestFilterRecord.
+ *  \tparam T record type
+ */
+template<typename T>
+class RecordContainer
+{
+public:
+  using Record = T;
+  using Container = std::map<RecordId, Record>;
+
+  /** \brief Retrieve record by ID.
+   */
+  Record*
+  get(RecordId id)
+  {
+    auto i = m_container.find(id);
+    if (i == m_container.end()) {
+      return nullptr;
+    }
+    return &i->second;
+  }
+
+  /** \brief Insert a record with given ID.
+   */
+  template<typename ...TArgs>
+  Record&
+  put(RecordId id, TArgs&&... args)
+  {
+    BOOST_ASSERT(id != 0);
+    auto it = m_container.emplace(std::piecewise_construct, std::forward_as_tuple(id),
+                                  std::forward_as_tuple(std::forward<decltype(args)>(args)...));
+    BOOST_ASSERT(it.second);
+
+    Record& record = it.first->second;
+    record.m_container = this;
+    record.m_id = id;
+    return record;
+  }
+
+  RecordId
+  allocateId()
+  {
+    return ++m_lastId;
+  }
+
+  /** \brief Insert a record with newly assigned ID.
+   */
+  template<typename ...TArgs>
+  Record&
+  insert(TArgs&&... args)
+  {
+    return put(allocateId(), std::forward<decltype(args)>(args)...);
+  }
+
+  void
+  erase(RecordId id)
+  {
+    m_container.erase(id);
+    if (empty()) {
+      this->onEmpty();
+    }
+  }
+
+  void
+  clear()
+  {
+    m_container.clear();
+    this->onEmpty();
+  }
+
+  /** \brief Visit all records with the option to erase.
+   *  \tparam Visitor function of type 'bool f(Record& record)'
+   *  \param f visitor function, return true to erase record
+   */
+  template<typename Visitor>
+  void
+  removeIf(const Visitor& f)
+  {
+    for (auto i = m_container.begin(); i != m_container.end(); ) {
+      bool wantErase = f(i->second);
+      if (wantErase) {
+        i = m_container.erase(i);
+      }
+      else {
+        ++i;
+      }
+    }
+    if (empty()) {
+      this->onEmpty();
+    }
+  }
+
+  /** \brief Visit all records.
+   *  \tparam Visitor function of type 'void f(Record& record)'
+   *  \param f visitor function
+   */
+  template<typename Visitor>
+  void
+  forEach(const Visitor& f)
+  {
+    removeIf([&f] (Record& record) {
+      f(record);
+      return false;
+    });
+  }
+
+  bool
+  empty() const noexcept
+  {
+    return m_container.empty();
+  }
+
+  size_t
+  size() const noexcept
+  {
+    return m_container.size();
+  }
+
+public:
+  /** \brief Signals when container becomes empty
+   */
+  util::Signal<RecordContainer<T>> onEmpty;
+
+private:
+  Container m_container;
+  std::atomic<RecordId> m_lastId{0};
+};
+
+} // namespace ndn
+
+#endif // NDN_IMPL_RECORD_CONTAINER_HPP
diff --git a/ndn-cxx/impl/registered-prefix.hpp b/ndn-cxx/impl/registered-prefix.hpp
index dce512b..423aec1 100644
--- a/ndn-cxx/impl/registered-prefix.hpp
+++ b/ndn-cxx/impl/registered-prefix.hpp
@@ -1,6 +1,6 @@
 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
 /*
- * Copyright (c) 2013-2018 Regents of the University of California.
+ * Copyright (c) 2013-2019 Regents of the University of California.
  *
  * This file is part of ndn-cxx library (NDN C++ library with eXperimental eXtensions).
  *
@@ -22,7 +22,6 @@
 #ifndef NDN_IMPL_REGISTERED_PREFIX_HPP
 #define NDN_IMPL_REGISTERED_PREFIX_HPP
 
-#include "ndn-cxx/interest.hpp"
 #include "ndn-cxx/impl/interest-filter-record.hpp"
 #include "ndn-cxx/mgmt/nfd/command-options.hpp"
 #include "ndn-cxx/mgmt/nfd/control-parameters.hpp"
@@ -30,17 +29,23 @@
 namespace ndn {
 
 /**
+ * @brief Opaque type to identify a RegisteredPrefix
+ */
+class RegisteredPrefixId;
+
+static_assert(sizeof(const RegisteredPrefixId*) == sizeof(RecordId), "");
+
+/**
  * @brief stores information about a prefix registered in NDN forwarder
  */
-class RegisteredPrefix : noncopyable
+class RegisteredPrefix : public RecordBase<RegisteredPrefix>
 {
 public:
-  RegisteredPrefix(const Name& prefix,
-                   shared_ptr<InterestFilterRecord> filter,
-                   const nfd::CommandOptions& options)
+  RegisteredPrefix(const Name& prefix, const nfd::CommandOptions& options,
+                   RecordId filterId = 0)
     : m_prefix(prefix)
-    , m_filter(filter)
     , m_options(options)
+    , m_filterId(filterId)
   {
   }
 
@@ -50,49 +55,22 @@
     return m_prefix;
   }
 
-  const shared_ptr<InterestFilterRecord>&
-  getFilter() const
-  {
-    return m_filter;
-  }
-
   const nfd::CommandOptions&
   getCommandOptions() const
   {
     return m_options;
   }
 
+  RecordId
+  getFilterId() const
+  {
+    return m_filterId;
+  }
+
 private:
   Name m_prefix;
-  shared_ptr<InterestFilterRecord> m_filter;
   nfd::CommandOptions m_options;
-};
-
-/**
- * @brief Opaque type to identify a RegisteredPrefix
- */
-class RegisteredPrefixId;
-
-/**
- * @brief Functor to match RegisteredPrefixId
- */
-class MatchRegisteredPrefixId
-{
-public:
-  explicit
-  MatchRegisteredPrefixId(const RegisteredPrefixId* registeredPrefixId)
-    : m_id(registeredPrefixId)
-  {
-  }
-
-  bool
-  operator()(const shared_ptr<RegisteredPrefix>& registeredPrefix) const
-  {
-    return reinterpret_cast<const RegisteredPrefixId*>(registeredPrefix.get()) == m_id;
-  }
-
-private:
-  const RegisteredPrefixId* m_id;
+  RecordId m_filterId;
 };
 
 } // namespace ndn