用于查找映射到元素集的 id 的良好数据结构 (c++)

发布于 2024-07-25 02:25:01 字数 342 浏览 1 评论 0原文

没有boost，只是简单的STL。

我有一个类 Foo* 映射到一组类 ID 的指针。

我需要将指向 ID 实例的指针映射到 FOO 类。

假设我有这个功能：

void FindXXX(const ID* pID)
{

 /*find the containing FOO class quickly, but not at expense of an ugly code*/

}

现在我将每个 ID* 映射到 FOO* ，从而拥有类似

映射 myMap 的东西；我认为这有点丑陋和多余。

请建议

原文

No boost, just plain STL please.

I have a class Foo* mapping to a set of pointers of class ID.

and I need to map a pointer to an instance of ID to a FOO class.

say I have this function:

void FindXXX(const ID* pID)
{

 /*find the containing FOO class quickly, but not at expense of an ugly code*/

}

right now I map each ID* to FOO* thus having something like that

map myMap; which I think is kind of ugly and redundant.

Please suggest

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

最冷一天 2024-08-01 02:25:02

听起来像是 std::map 的工作，但你的言论似乎表明你不想使用它，是真的吗？

std::map <key_type, data_type, [comparison_function]>

Sounds like a job for std::map, but your remarks seem to indicate that you don't want to use one, is that true?

std::map <key_type, data_type, [comparison_function]>

回复收藏 0 原文

睡美人的小仙女 2024-08-01 02:25:02

嗯，这有点取决于两个集合（ID* 和 foo*）的大小。我假设您有 #ID >> #FOO 和 #FOO 足够大，无法保证通过它们进行线性搜索。

我假设 ID <-> Foo 是一对多映射。

您可以将映射存储为集合 > > 并按如下方式对它们进行排序：
该集合按 ID* 的升序排序（指针值顺序就可以了）
套装> 按该对的 .第二个中第一个 ID* 的值的升序排序。

搜索时，您需要找到 Foo* 的范围，其中第一个 ID* 的（指针）值低于搜索项，而最后一个 ID* 的值高于搜索项。这将导致迭代其集合的项目集有望小得多。
然后，迭代这些并找到包含您要查找的 ID* 的那个。

您将需要一个比较器来比较 > 像这样：

typedef Item pair<Foo*, set<ID*> >;

// Sorter in ascending order of first ID*, then ascending order of last ID*
struct IDOrdering: public binary_function<Item, Item, bool> {
  bool operator ()(const Item& lhs, const Item& rhs) {
    return *(lhs.second.begin()) < *(rhs.second.begin())
        || *(lhs.second.rbegin()) < *(rhs.second.rbegin());
  }
};


// your global map
set<Item, FirstIDOrdering> myMap;
typedef set<Item, FirstIDOrdering>::iterator ItemIterator;

// search for the item
Foo* FindXXX(const ID* pId) {
   Item criterion;
   criterion.second.insert(pId);
   ItemIterator start = myMap.lower_bound(criterion);
   while (start != myMap.end() && *(start->second.rbegin()) > pId) {
     if (start->second.count(pId))
       return start->first;
   }
   return NULL;
}

您可以在这里节省一些内存，因为 Foo* 和 ID* 只存储一次，但它是以一些复杂性和可能一些性能为代价的。

请注意，此示例并未考虑所有类型的边界情况（空列表），并且在将新项目插入全局 myMap 时必须小心，因为您可能能够将新的 ID* 添加到列表中一对<>，但您需要确保整个集合再次排序，以便查找真正起作用。

然而，很难知道什么对你来说是最好的，因为关于你试图实现的目标的信息很少：Foo* 是数百万，ID* 是数百万，这个函数是用来解析 ID* 的吗？经常给 Foo* 打电话？在系统的性能关键部分？所有这些都有助于权衡代码的可读性、复杂性和性能。

Well, it kind of depends on the size of the two sets (ID* and foo*). I assume that you have #ID >> #FOO, and #FOO big enough to not warrant linear search through them.

I assume ID <-> Foo is a 1-to-many mapping.

You could store the mapping as a set > > and sort them this way:
the set is sorted in increasing order of ID* (pointer value order would be fine)
the set> is sorted in ascending order of the value of the first ID* in the .second of the pair.

When searching, you need to find the range of Foo* that have a set where the first ID* has a (pointer) value lower than the searched-for item, and the last a value higher. This will result in a hopefully much smaller set of items to iterate over their set.
Then, iterate over these and find the one that contains the ID* you are looking for.

You will need a comparator for the pair > like this:

typedef Item pair<Foo*, set<ID*> >;

// Sorter in ascending order of first ID*, then ascending order of last ID*
struct IDOrdering: public binary_function<Item, Item, bool> {
  bool operator ()(const Item& lhs, const Item& rhs) {
    return *(lhs.second.begin()) < *(rhs.second.begin())
        || *(lhs.second.rbegin()) < *(rhs.second.rbegin());
  }
};


// your global map
set<Item, FirstIDOrdering> myMap;
typedef set<Item, FirstIDOrdering>::iterator ItemIterator;

// search for the item
Foo* FindXXX(const ID* pId) {
   Item criterion;
   criterion.second.insert(pId);
   ItemIterator start = myMap.lower_bound(criterion);
   while (start != myMap.end() && *(start->second.rbegin()) > pId) {
     if (start->second.count(pId))
       return start->first;
   }
   return NULL;
}

You may save some memory here, as Foo* and ID* are stored only once, but it comes at the cost of some complexity and probably some performance.

Note that this example does not take into account all sorts of border cases (empty lists), and you have to be careful when inserting a new item into the global myMap, as you may be able to add a new ID* to the list of a pair<>, but you need to make sure the entire set is sorted again, so that the find will actually work.

It is, however, difficult to know what would be best for you, as there is very little info about what you try to achieve: are the Foo* in the millions, the ID* in the millions, is this function to resolve ID* to Foo* called often ? In a performance critical section of your system ? All these are useful to make the trade-offs for the readability, complexity and performance of the code.

回复收藏 0 原文