Какая структура данных, подобная множеству карт, может поддерживать замену при сохранении порядка?

Я хочу реализовать мультикарту, которая поддерживает порядок вставки записей и позволяет вставлять/заменять на месте, не влияя на порядок. LinkedListMultimap Гуавы почти идеален, но не позволяет заменить тот тип, который я ищу. LinkedListMultimap реализован в виде хеш-карты и нескольких связанных списков; это выглядит так:

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

Внутри каждый узел имеет указатель на следующий узел в последовательности, а также на следующий узел с тем же ключом, а хэш-таблица поддерживает сопоставление ключей с первым узлом с этим ключом.

К сожалению, это не позволяет выполнять эффективную вставку или замену на месте. Например, чтобы заменить (C,4) на (B,8), мне пришлось бы пройти сколь угодно длинный путь назад, чтобы найти (B,2), чтобы обновить его указатель «следующий из того же ключа».

Лучшая идея, которая у меня есть, — связать каждый элемент с порядковым номером и сохранить отсортированный набор для каждого ключа. Но чтобы вставить в середину последовательности, мне понадобились бы бесконечно делимые порядковые номера.

(Кстати, я реализую это на C++, но я просто ищу описание структуры данных, которая будет работать. Если есть уже существующая библиотека, которая будет работать, это было бы здорово, но даже boost::multi_index_container не работает. кажется, не справляется с задачей.)


data-structures guava language-agnostic boost-multi-index
person Tavian Barnes    schedule 25.02.2015    source источник

Ответы (3)


arrow_upward
0
arrow_downward

Ответ №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";
}
person Joaquín M López Muñoz    schedule 27.02.2015
comment
Посмотрите потом на mm.equal_range("B"); это (B,2) (B,5) (B,8) вместо (B,2) (B,8) (B,5). coliru.stacked-crooked.com/a/076cc158114c4b6a - person Tavian Barnes; 27.02.2015
comment
Я понимаю. Смотрите мой новый ответ. - person Joaquín M López Muñoz; 28.02.2015

arrow_upward
0
arrow_downward

Ответ 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, так как он больше не нужен.
person Joaquín M López Muñoz    schedule 28.02.2015

arrow_upward
0
arrow_downward

Ответ №3

Мой второй ответ можно уточнить, чтобы поместить субкомпаратор внутри самого объекта 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. Общая стратегия остается точно такой же.

person Joaquín M López Muñoz    schedule 28.02.2015
comment
Я вижу, что вы сделали, очень красиво! К сожалению, вставка в середину индекса random_access - это O(n), но, поскольку она не требует копий, на практике это, вероятно, быстро для моего случая. Мне любопытно, можно ли это сделать за сублинейное время. - person Tavian Barnes; 28.02.2015
comment
(Вне области Boost.MultiIndex.) Чтобы выполнить сублинейную замену, вам нужно знать два элемента x и y, которые идут первыми в последовательности. Векторная последовательность дает вам это за постоянное время, но, как вы указываете, средняя вставка - это O (n). Альтернативой может быть использование дерева статистики заказов (en.wikipedia.org/wiki/Order_statistic_tree). ) в качестве базовой последовательности: проверка относительного порядка может быть выполнена за O (log n), а также вставка в середине. - person Joaquín M López Muñoz; 28.02.2015
comment
Ах, дерево статистики заказов идеально! Не могу поверить, что я не думал об этом сам на самом деле. Если вы поставите это как ответ, я с радостью приму это. - person Tavian Barnes; 28.02.2015
comment
Вам придется измерять, но я уверен, что векторная последовательность, показанная в моем примере с Boost.MultiIndex, на практике превзойдет дерево статистики порядка. Пожалуйста, дайте мне знать, если вы делаете упражнение. - person Joaquín M López Muñoz; 28.02.2015