6

假设我有以下内容：

struct MetadataThingy {

    void *actual_thingy;
    int some_metadata;
    int more_metadata;

    bool operator<(MetadataThingy const& other) const {
        return actual_thingy < other.actual_thingy;
    }

};

whereactual_thingy指向一些重要的数据，我希望容器按 的值actual_thingy而不是指向的元素的值排序，但是我需要存储一些关于它的其他数据，所以我创建了MetadataThingy带有比较器的包装类，它只考虑指针的值actual_thingy（而不是使用 的容器void *）

现在，给定以下代码：

std::set<MetadataThingy> thingy_set;

void test() {

    MetadataThingy m1 { nullptr, 5, 20 };
    MetadataThingy m2 { &m1, 1, 2 };
    MetadataThingy m3 { &m2, 6, 0 };

    thingy_set.insert(m1);
    thingy_set.insert(m2);
    thingy_set.insert(m3);

    MetadataThingy m;
    m = *thingy_set.find(m2); // OK.
    m = *thingy_set.find(static_cast<void *>(&m2)); // Nope. Can't use a pointer.

}

由于每个MetadataThingy对象都可以由它存储的指针值唯一标识并按指针值排序，因此只需使用 avoid *作为键来查找/删除对象是有意义的。但是，就目前的情况而言，MetadataThingy每次搜索元素时我都必须创建一个虚拟对象，这感觉非常笨拙。我已经考虑过只使用map带有指针的键和MetadataThingy值，但由于每个指针都MetadataThingy必须包含指针，这感觉有点多余。那么，有没有办法使用集合中存储的元素以外的类型的元素来查找或删除集合中的值，假设这两种类型的元素是相互可比的，并且一种类型的元素可以唯一地映射到另一个（void *和MetadataThingy是同构的）？（我没有在上面的代码中包含任何内容，但假设存在用于比较void *和MetadataThingy任何顺序的运算符重载。）

关于我要解决的问题的一些背景知识，以防万一有人可以推荐更好的方法：我需要按多个标准订购一个集合，所以我有几个MetadataThingy容器，所有容器都按不同的标准排序。在这种情况下，“元数据”是我需要跟踪所有容器中元素位置的东西，以便我可以快速删除。这听起来像是提升多索引容器的完美工作，但这些元素的顺序不断变化，这意味着 AFAIK 将意味着它不会工作。

4

4 回答 4

4

As of C++14, std::set has templated versions of its lookup functions find, lower_bound, etc. They allow you to pass any object for comparison, as long as the comparer supports it.

This means you can directly pass your void* to find, as long as the comparer supports comparing MetadataThingy and void*.

For more information, see http://en.cppreference.com/w/cpp/container/set/find.

To understand the limitation regarding Compare::is_transparent, I found this StackOverflow question very helpful.

于 2016-03-30T19:33:57.733 回答
1

您可以通过使用std::find_if和提供谓词函子来做到这一点。

#include <algorithm>

struct Predicate
{
    void const * const ptr_;
    explicit Predicate(const void* ptr) : ptr_(ptr) {}
    bool operator()(const MetadataThingy& other)
    {
        return ptr_ == other.actual_thingy;
    }
};

m = *std::find_if(thingy_set.begin(), thingy_set.end(), Predicate(&m2));

您可以使用返回的迭代器std::find_if将元素从集合中移除，方法是将其传递给set::erase.

于 2013-06-29T01:44:43.003 回答
1

不， 的签名map<>::find需要您传递密钥类型。

但是，有一个相对简单的解决方法。使用boost::optionalor std::tr2::optional（来自 C++1y）来存储你的非关键数据。

struct MetadataThingy {
  void* pBlah;
  optional<rest_of_stuff> rest;
  static MetadataThingy searcher( void* );
  MetadataThingy(...);
};

然后调用MeatadataThingy::searcher以生成您的键值。

另一种方法是存储指向子接口的智能（可能是唯一的）指针，每个子接口都有一个“获取完整数据”方法。然后，当您想要进行搜索时，创建一个返回nullptr“获取完整数据”的存根子接口。

struct MetadataFull;
struct MetadataRoot {
  virtual MetadataFull* get() = 0;
  virtual MetadataFull const* get() const = 0;
  virtual ~MetadataRoot() {}
};
template<typename T>
struct MetadataFinal: virtual MetadataRoot {
  static_assert( std::is_base_of< T, MetadataFinal<T> >::value, "CRTP failure" );
  virtual MetadataFull* get() { return static_cast<T*>(this); }
  virtual MetadataFull const* get() const { return static_cast<T const*>(this); }
};
struct MetadataStub: virtual MetadataRoot {
  virtual MetadataFull* get() { return nullptr; }
  virtual MetadataFull const* get() const { return nullptr; }
};
struct MetaDataA: virtual MetaDataRoot {
  void* pBlah;
};

struct MetaDataFull: MetaDataA, MetadataFinal<MetaDataFull> {
  // unsorted data
};
struct MetaDataAStub: MetaDataA, MetaDataStub {};

现在，这可以通过virtual函数来​​完成，但virtual如果你真的需要它，则可以通过一些小技巧来完成继承。

于 2013-06-29T02:02:14.413 回答
1

该库不支持您要求的行为，尽管我看到其他人要求同样的事情（即find在将使用交叉比较器的有序关联容器中提供模板化成员函数），尽管这种情况并不常见。

您的类型是不寻常的，因为只有一个成员属性参与对象的值（即用于比较）。编译器无法知道只有一些成员（或哪些成员）是值的一部分，而哪些不是。尽管这些对象可能并没有真正的可比性，而您只是operator<将其作为一种在关联容器中启用的简单方法。

如果是这种情况，请考虑删除operator<不真正比较对象的MetaThingy，并将数据结构更改为 a std::map<void*,MetaThingy>，这将使设计更简洁，但void*会以每个存储对象的额外成本为代价——也可能是这种情况在集合中查找的void*内部MetaThingy...在这种情况下，它甚至可能更有意义，您可以提供std::map<void*,MetaInfo>.

于 2013-06-29T02:07:04.070 回答