有效修改用作键的集合元素的最安全方法

Question

我有 std::set<std::set<T>> 个我需要经常修改的内部集。

我怎样才能有效地做到这一点？我能想出的唯一方法要么似乎导致未定义的行为，要么导致整个内部集被复制，这两种方法似乎都是坏主意。

Answer 1

你可以将内部类型设为 not a set:

struct DerefComparator {
    template <typename T>
    bool operator()(const T& lhs, const T& rhs) const
    {
        return *lhs < *rhs;
    }
};

std::set<std::shared_ptr<std::set<T>>, DerefComparator> the_set;
auto it = the_set.find(...);

// copy out - doesn't copy the whole set
auto inner = *it;
the_set.erase(it);

// make modifications as before
inner->insert(...);
inner->erase(...);

// move in
the_set.insert(std::move(inner));

Answer 2

Boost.MultiIndex 允许就地修改元素，如示例所示：

Live Coliru Demo

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/identity.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <cassert>
#include <set>

template<typename T>
using set_set=boost::multi_index_container<
  std::set<T>,
  boost::multi_index::indexed_by<
    boost::multi_index::ordered_unique<
      boost::multi_index::identity<std::set<T>>
    >
  >
>;

int main()
{
  set_set<int> ss={{0,1,2},{1,2,3},{2,3,4},{6,4,5}};

  auto it=ss.find(std::set<int>{6,4,5}); // get last element
  ss.modify(it,[](auto& s){
    s.erase(6);   // change 6
    s.insert(3);  // for 3
  });
  assert((*it==std::set<int>{3,4,5}));
}

有效修改用作键的集合元素的最安全方法

Safest way to efficiently modify set element that is used as a key

c++

performance

set

undefined-behavior