标签: unordered-set

这个问题关系到 这一个,并更准确地这样回答.

这里是:我有一个U无符号整数的C++/TR1 unordered_set (粗基数100-50000,粗略值范围0到10 ^ 6).鉴于基数N,我希望尽可能快地迭代N随机但独特的成员U.没有典型值N,但它应该对小的快速工作N.

更详细地说,这里的"随机性"的概念是两个调用应该产生稍微不同的子集 - 越不同,越好,但这不是太关键.只要块的起始索引是随机N的U,我就会对连续(或包裹的连续)成员块感到满意.以相同的成本不连续更好,但主要关注的是速度.U温和地改变,但在呼叫之间不断变化(在呼叫之间插入/删除大约0-10个元素).

我到底有多远:

1. 平凡的方法:
   选择随机指标i这样(i+N-1) < |U|.获取迭代器,使用它it来U.begin()推进它,然后在子集上启动实际循环.优点:容易.缺点:浪费++.iit++

2. 桶的做法(这我有"新",从上面的链接导出):
   选择i如上,发现桶b中的i个元素是,获得local_iterator lit 到U.begin(b),提前lit通过lit++,直到我们打i的个元素U,并从此不断递增lit的N时间.如果我们到达桶的末尾,我们lit将从下一个桶的开头继续.如果我想让它更随机,我可以i完全随机选择并包裹桶.

我的开放性问题:

1. 对于上面的第2点,是否真的是U我找不到i-th元素时我不能以某种方式得到迭代器？这样可以省去桶边界控制等等.对于我来说,作为一个初学者,标准的前向迭代器应该知道如何 …

什么是

operator size_t () const

环境:Visual Studio 2010 Professional

TL; DR

今天我正在寻找一种使用方法std::tr1::unordered_set.因为我上次询问如何使用std::map,我决定自己找出来.

我用Google搜索,大部分结果告诉我有一个结构来进行散列.这种方式对我来说有点复杂,我一直在寻找并最终遇到了另一种方法.

我需要实施

bool operator == (const edge & another) const

和

operator size_t () const

结果代码接近问题的结尾.

==熟悉没有任何问题.size_t也很熟悉.但是什么operator size_t呢？

好像equals和hashCode对Java,它需要根据有效的Java被覆盖起来.但我不确定,尤其是名字的时候size_t.

结果代码如下.完整的程序工作正常,并产生正确的输出.

class edge {
public:
    int x;
    int y;
    edge(int _x, int _y) : x(_x), y(_y) {
    }
    bool operator == (const edge & another) const {
        return (x == another.x && …

假设我有以下User结构:

struct User { 
    string userId; 
    UserType userType; // UserType is just an enumeration
    string hostName;
    string ipAddress;
    //and more other attributes will be added here

};

我需要存储一组用户记录(大约10 ^ 5个用户,也可以扩展得更高).如果我将它存储为unordered_set或unordered_map,它的性能会更好吗？Unordered_set在技术上与HashSet相同,unordered_map与HashMap相同,对吧？使用常规集(有序)不是一个选项,因为当元素数量增加时插入和删除将变得非常慢.

unordered_set <User> userRecords;

要么

unordered_map <string, User> userRecords; // string is the user ID.

我需要它在插入,删除和通过其userId访问特定用户对象方面非常快.

有很多的答案有std::vector,但怎么样std::unordered_set？

我真正的问题(密切相关)是这样的; 如果我事先保留我所知道的合理尺寸,那么在每次使用之前通过清除它来重复使用相同的无序集是否有效？

什么是迭代无序对元素的简洁方法unordered_set？

(所以顺序无关紧要,元素应该不同)

例如{1,2,3} =>(1,2)(2,3)(1,3)

我最初的尝试是类似的

for (i = 0; i < size - 1; i++) {
  for (j = i + 1; j < size; j++) {
    ...
  }
}

但是对于迭代器来说这并不是非常方便.

第三个参数的用途是KeyEqual什么std::unordered_set？哈希唯一性还不够吗？

template<
    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
> class unordered_set;

抱歉，如果这个问题听起来很幼稚。从 Python/PHP 迁移到 C++ :)

现在我的实现KeyEqual总是重复Hashimpl。所以我想知道我是否做得正确。

我是 C++ 新手，被要求将 Java 程序转换为 C++。我正在尝试编写一种方法来检查 unordered_set 中的所有元素是否存在于另一个 unordered_set 中。我发现下面的示例使用 hash_set，但 hash_set 已弃用，建议现在使用 unordered_set。

// returns true if one contains all elements in two
bool SpecSet::containsAll(hash_set<Species*> one, hash_set<Species*> two) {
   sort(one.begin(), one.end());
   sort(two.begin(), two.end());
   return includes(one.begin(), one.end(), two.begin(), two.end());
}

所以我需要一种使用 unordered_set 来做到这一点的方法。排序不适用于无序集，并且查找速度很重要，因此我不想使用有序集。

bool SpecSet::containsAll(unordered_set<Species*> one, unordered_set<Species*> two) {

   return ?;
}

我真的很感谢您提供一些帮助来有效地做到这一点。

编辑：我想这会起作用。看来除了一分为二循环之外，没有更有效的方法了。

bool SpecSet::containsAll(unordered_set<Species*> one, unordered_set<Species*> two) {
   if(two.size() > one.size())
   {
      return false;
   }

   for(Species *species : two)
   {
      if(one.find(species) == one.end())
      {
         return false;
      }
   } …

http://www.cplusplus.com/reference/unordered_set/unordered_set/find/

在 unordered_set 中查找的时间复杂度对于 unordered_set 来说平均是恒定的。如果我有一个 unordered_set 字符串，那么在该集合中查找字符串的时间复杂度是多少？它是常量还是 O(字符串长度)？

正如指出的使用的std ::的unique_ptr的一个std :: unordered_set，这是不容易找到一个指针T*中std::unordered_set<std::unique_ptr<T>>。在 C++20 之前，我们被迫构造一个std::unique_ptr<T>.

感谢无序容器提案的异构查找（http://wg21.link/P0919r3和http://wg21.link/p1690r1），这个问题在 C++20 中得到解决。但是可用的解决方案对我来说看起来很笨拙（即使按照 C++ 标准）。似乎我需要从头开始实现不是一个，而是两个函子（用于透明散列和透明比较）：

template<class T>
struct Equal {
    using is_transparent = void;
    bool operator()(const std::unique_ptr<T>& lhs, const std::unique_ptr<T>& rhs) const {
        return lhs == rhs;
    }
    bool operator()(const std::unique_ptr<T>& lhs, const T* rhs) const {
        return lhs.get() == rhs;
    }
    bool operator()(const T* lhs, const std::unique_ptr<T>& rhs) const {
        return lhs == rhs.get();
    }
};

template<class …

为什么插入集合的最坏情况复杂度是容器大小的线性常数而不是元素本身的大小？

我专门谈论字符串。如果我有一个大小为 m 的字符串集，那么如果我插入一个大小为 x 的新字符串，我假设插入操作需要读取大小为 x 的字符串才能计算键？那么我们为什么不考虑那个时间呢？

如果还有另一个大小为 1000*x 的字符串，那么在最坏的情况下插入仍然需要 m 大小？无论字符串大小，时间都是0(m)？如何？