什么样的多映射数据结构可以在维护秩序的同时支持替换

Question

我希望实现一个多映射，它可以维护条目的插入顺序，并允许在不影响顺序的情况下就地插入/替换。Guava的LinkedListMultimap几乎是完美的，但不允许我想要的那种替代品。CCD_ 2被实现为散列映射和多个链表；它看起来像这样：

                             ________________
                            /                
(A,1) -> (B,2) -> (A,3) -> (C,4) -> (B,5) -> (C,6) -> (A,7)
 _______________/________________/_________________/
           _______________________/

在内部，每个节点都有一个指向序列中下一个节点以及具有相同键的下一个结点的指针，哈希表维护从键到具有该键的第一个节点的映射。

不幸的是，这不允许有效的就地插入或替换。例如，要用(B,8)替换(C,4)，我必须向后走任意长的路才能找到(B,2)，以便更新其"同一个键的下一个"指针。

到目前为止，我的最佳想法是将每个元素与序列号相关联，并为每个键保留一个排序集。但要插入序列的中间，我需要无限可分的序列号。

（顺便说一句，我正在C++中实现这一点，但我只是在寻找一个可以工作的数据结构的描述。如果有一个预先存在的库可以工作，那就太好了，但即使是boost::multi_index_container似乎也无法胜任这项任务。）

Answer 1

答案#1

为什么Boost.MultiIndex对您没有帮助？

在Coliru上直播

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/sequenced_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/member.hpp>
using namespace boost::multi_index;
#include <iosfwd>
template<typename T,typename Q>
struct pair_
{
  T first;
  Q second;
};
template<typename T,typename Q>
std::ostream& operator<<(std::ostream& os,const pair_<T,Q>& p)
{
  return os<<"("<<p.first<<","<<p.second<<")";
}
template<typename T,typename Q>
using list_multimap=multi_index_container<
  pair_<T,Q>,
  indexed_by<
    sequenced<>,
    ordered_non_unique<
      composite_key<
        pair_<T,Q>,
        member<pair_<T,Q>,T,&pair_<T,Q>::first>,
        member<pair_<T,Q>,Q,&pair_<T,Q>::second>
      >
    >
  >
>;
template<typename T,typename Q>
std::ostream& operator<<(std::ostream& os,const list_multimap<T,Q>& lmm)
{
   for(const auto& p:lmm)os<<p<<" ";
   return os;
}
#include <string>
#include <iostream>
int main()
{
  list_multimap<std::string,int> lmm{{"A",1},{"B",2},{"A",3},{"C",4},{"B",5},{"C",6},{"A",7}};
  auto&                          mm=lmm.get<1>();
  std::cout<<lmm<<"n";
  // List values with key "A"
  auto r=mm.equal_range("A");
  while(r.first!=r.second)std::cout<<*(r.first)++<<" ";
  std::cout<<"n";
  // replace (C,4) with (B,8)
  mm.replace(mm.find(std::make_tuple("C",4)),{"B",8});
  std::cout<<lmm<<"n";
}

Answer 2

答案#2

我认为，我的第一个答案可以进行提炼，以获得你想要的：

在Coliru上直播

#include <algorithm>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <functional>
using namespace boost::multi_index;
#include <iosfwd>
template<typename T,typename Q>
struct pair_
{
  T first;
  Q second;
  using compare=std::function<bool(const pair_&,const pair_&)>;
  mutable compare* subcmp;
  pair_(const T& first,const Q& second,compare* subcmp=nullptr):
    first(first),second(second),subcmp(subcmp){}
};
namespace std{
template<typename T,typename Q>
struct less<pair_<T,Q>>
{
  bool operator()(const pair_<T,Q>& x,const pair_<T,Q>& y)const
  {
     if(x.first<y.first)return true;
     if(y.first<x.first)return false;
     if(x.subcmp)       return (*x.subcmp)(x,y);
     if(y.subcmp)       return (*y.subcmp)(x,y);
     return false;
  }
  template<typename R>
  bool operator()(const R& x,const pair_<T,Q>& y)const
  {
     return x<y.first;
  }
  template<typename R>
  bool operator()(const pair_<T,Q>& x,const R& y)const
  {
     return x.first<y;
  }
};
} // namespace std
template<typename T,typename Q>
std::ostream& operator<<(std::ostream& os,const pair_<T,Q>& p)
{
  return os<<"("<<p.first<<","<<p.second<<")";
}
template<typename T,typename Q>
using list_multimap=multi_index_container<
  pair_<T,Q>,
  indexed_by<
    random_access<>,
    ordered_non_unique<identity<pair_<T,Q>>>
  >
>;
template<typename T,typename Q>
std::ostream& operator<<(std::ostream& os,const list_multimap<T,Q>& lmm)
{
   for(const auto& p:lmm)os<<p<<" ";
   return os;
}
#include <string>
#include <iostream>
int main()
{
  list_multimap<std::string,int> lmm{{"A",1},{"B",2},{"A",3},{"C",4},{"B",5},{"C",6},{"A",7}};
  auto&                          mm=lmm.get<1>();
  std::cout<<lmm<<"n";
  // list values with key "A"
  auto r=mm.equal_range("A");
  while(r.first!=r.second)std::cout<<*(r.first)++<<" ";
  std::cout<<"n";
  // replace (C,4) with (B,8)
  pair_<std::string,int>::compare subcmp=[&](const auto&x, const auto& y){
    auto itx=lmm.iterator_to(x);
    auto ity=lmm.iterator_to(y);
    return itx<ity;
  };
  r=mm.equal_range("C");
  auto it=std::find_if(r.first,r.second,[](const auto& x){return x.second==4;});
  mm.modify(it,[&](auto&x){x={"B",8,&subcmp};});
  it->subcmp=nullptr;
  std::cout<<lmm<<"n";
  // list values with key "B"
  r=mm.equal_range("B");
  while(r.first!=r.second)std::cout<<*(r.first)++<<" ";
  std::cout<<"n";  
}

关键思想是：

• 使用随机访问索引，而不是顺序索引
• 让元素由用户提供的比较函数进行子排序（当键相等时），存储在subcmp中，这是可选的（如果subcmp为空）
• 在替换值时，请使用modify（以便在适当的位置更改元素），并提供一个简单遵循随机访问索引中元素顺序的子标量。修改完成后，将subcmp设置为nullptr，因为不再需要它

Answer 3

答案#3

我的第二个答案可以进一步细化，将子carer放置在less<pair_<T,Q>>对象本身中：

在Coliru上直播

#include <algorithm>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/identity.hpp>
#include <functional>
using namespace boost::multi_index;
#include <iosfwd>
template<typename T,typename Q>
struct pair_
{
  T first;
  Q second;
};
namespace std{
template<typename T,typename Q>
struct less<pair_<T,Q>>
{
  using subcompare=std::function<bool(const pair_<T,Q>&,const pair_<T,Q>&)>;
  subcompare subcmp;
  bool operator()(const pair_<T,Q>& x,const pair_<T,Q>& y)const
  {
     if(x.first<y.first)return true;
     if(y.first<x.first)return false;
     if(subcmp)         return subcmp(x,y);
     return false;
  }
  template<typename R>
  bool operator()(const R& x,const pair_<T,Q>& y)const
  {
     return x<y.first;
  }
  template<typename R>
  bool operator()(const pair_<T,Q>& x,const R& y)const
  {
     return x.first<y;
  }
};
} // namespace std
template<typename T,typename Q>
std::ostream& operator<<(std::ostream& os,const pair_<T,Q>& p)
{
  return os<<"("<<p.first<<","<<p.second<<")";
}
template<typename T,typename Q>
using list_multimap=multi_index_container<
  pair_<T,Q>,
  indexed_by<
    random_access<>,
    ordered_non_unique<
      identity<pair_<T,Q>>,
      std::reference_wrapper<const std::less<pair_<T,Q>>>>
  >
>;
template<typename T,typename Q>
std::ostream& operator<<(std::ostream& os,const list_multimap<T,Q>& lmm)
{
   for(const auto& p:lmm)os<<p<<" ";
   return os;
}
#include <string>
#include <iostream>
int main()
{
  std::less<pair_<std::string,int>> less;
  list_multimap<std::string,int>    lmm{boost::make_tuple(
                                      boost::make_tuple(),
                                      boost::make_tuple(
                                        identity<pair_<std::string,int>>{},
                                        std::cref(less)
                                      )
                                    )};
  auto&                             mm=lmm.get<1>();
  lmm={{"A",1},{"B",2},{"A",3},{"C",4},{"B",5},{"C",6},{"A",7}};
  std::cout<<lmm<<"n";
  // list values with key "A"
  auto r=mm.equal_range("A");
  std::for_each(r.first,r.second,[](const auto& x){std::cout<<x<<" ";});
  std::cout<<"n";
  // replace (C,4) with (B,8)
  std::less<pair_<std::string,int>>::subcompare subcmp=
  [&](const auto&x, const auto& y){
    return lmm.iterator_to(x)<lmm.iterator_to(y);
  };
  r=mm.equal_range("C");
  auto it=std::find_if(r.first,r.second,[](const auto& x){return x.second==4;});
  less.subcmp=subcmp;
  mm.modify(it,[](auto& x){x={"B",8};});
  less.subcmp=nullptr;
  std::cout<<lmm<<"n";
  // list values with key "B"
  r=mm.equal_range("B");
  std::for_each(r.first,r.second,[](const auto& x){std::cout<<x<<" ";});
  std::cout<<"n";  
}

这使我们大大减少了内存使用，因为元素本身不需要为subcmp提供额外的指针。总体战略保持不变。