标签: unordered

我期望下面的两个无序集合被评估为等价,但令我惊讶的是它们不是.发生这种情况是因为两个字符串存储在同一个哈希桶中,而运算符==对集合中的项目进行顺序比较.这应该被视为std :: unordered_set中的错误吗？有人有一个优雅的解决方法吗？

std::unordered_set<std::string> a,b;
a.insert("500666");
a.insert("961021");
b.insert("961021");
b.insert("500666");

if (a == b)   // condition is evaulated as false
{   
}

我有这个模板类:

template <typename T> Thing { ... };

我想在unordered_set中使用它:

template <typename T> class Bozo {
  typedef unordered_set<Thing<T> > things_type;
  things_type things;
  ...
};

现在,除了哈希函数之外,类Thing具有所需的一切.我想使这个通用所以我尝试类似的东西:

namespace std { namespace tr1 {
  template <typename T> size_t hash<Thing<T> >::operator()(const Thing<T> &t) const { ... }
}}

尝试用g ++ 4.7编译它会让它尖叫

在'<'之前预期的初始化程序

有关

hash<Thing<T> >

声明的一部分.任何线索都有助于挽救我头上剩下的少量毛发.

我有 2 个对象数组，我必须比较它们，但对象的顺序并不重要。我无法对它们进行排序，因为我没有它们的键名，因为函数必须是通用的。我将拥有的关于数组的唯一信息是两个数组的对象具有相同数量的键并且这些键具有相同的名称。所以 array1 必须包含与 array2 相同的对象。

var array1 = [{"key1":"Banana", "key2":"Yammy"}, {"key1":"Broccoli", "key2":"Ew"}];
var array2 = [{"key1":"Broccoli", "key2":"Ew"}, {"key1":"Banana", "key2":"Yammy"}];

在示例中，array1 必须等于 array2。我尝试使用 chai.eql()方法，但没有用。

(这个问题比Haskell更普遍适用,但这是我用来表达它的语言.)

foldl和之间的区别foldr似乎取决于列表是否有序.即,foldl和foldl通过将函数的起始值和所述第一或最后一个元素折叠列表,然后向所述第一应用程序的结果和第二或第二到最后一个元素,则第二个应用程序的结果第三或第三到最后的元素等

但是Haskell的Data.Set和Data.Map库定义了他们自己的版本foldl和foldr.例如,对于地图,它们是:

foldr :: (a -> b -> b) -> b -> Map k a -> b
foldl :: (b -> a -> b) -> b -> Map k a -> b -- I've swapped `a` and `b`
  -- in the second type signature to clarify the correspondence.

地图和集合未订购.我是否应该预期版本foldl和foldr为集合和地图定义的性能差异,或者确实foldr f做同样的事情foldl (flip f)？

下面的列表有一些重复的子列表，元素的顺序不同：

l1 = [
    ['The', 'quick', 'brown', 'fox'],
    ['hi', 'there'],
    ['jumps', 'over', 'the', 'lazy', 'dog'],
    ['there', 'hi'],
    ['jumps', 'dog', 'over','lazy', 'the'],
]

如何删除重复项，保留看到的第一个实例，以获得：

l1 = [
    ['The', 'quick', 'brown', 'fox'],
    ['hi', 'there'],
    ['jumps', 'over', 'the', 'lazy', 'dog'],
]

我试过了：

[list(i) for i in set(map(tuple, l1))]

尽管如此，我不知道这是否是大型列表的最快方法，而且我的尝试没有按预期工作。知道如何有效地删除它们吗？

缩小范围:我目前正在使用Boost.Unordered.我看到两种可能的解决方案

1. 定义我自己的Equality Predicates和Hash Functions,并利用模板(可能is_pointer)区分指针和实例;

2. 简单地boost::hash通过提供hash_value(Type* const& x)哈希来扩展; 并将==运算符重载作为自由函数添加,其(Type* const& x, Type* const& y)参数与等式检查相同.

我不确定这两种变化是否真的可行,因为我没有测试它们.我想找出你处理这个问题.欢迎实施:)

编辑1: 这个怎么样？

template<class T>
struct Equals: std::binary_function<T, T, bool> {
    bool operator()(T const& left, T const& right) const {
        return left == right;
    }
};

template<class T>
struct Equals<T*> : std::binary_function<T*, T*, bool> {
    bool operator()(T* const& left, T* const& right) const {
        return *left == *right;
    }
};

编辑2:

我刚刚定义:

friend …

我想知道是否可以保证 unordered_map 的顺序在所有 CPU、线程等中始终相同。

我意识到特定顺序本身可能没有明显的模式（因此，“无序”映射），但是如果我在另一台机器上运行我的进程，或者连续多次运行，或者在不同的线程上运行，插入项目的顺序将始终如果哈希函数和插入顺序保持不变，是否会相同？换句话说，如果我的代码不改变，我的进程的每次执行都会导致映射的元素处于相同的顺序吗？

我已经运行了一些测试，插入后的项目顺序似乎每次都是相同的，但这可能只是侥幸，而且我只有这台机器可以测试。我需要知道顺序是否会受到任何其他因素的影响，例如 CPU/内存架构、操作系统（Windows 8 与 Windows 10）等。

假设我有以下数组：

a = [4,2,3,1,4]

然后我排序：

b = sorted(A) = [1,2,3,4,4]

我怎么能有一个列表来映射每个数字的位置，例如：

position(b,a) = [3,1,2,0,4]

澄清此列表包含位置而不是值）

（ps' 还考虑到前 4 个在位置 0）

此代码无法在Visual Studio 2013中编译:

#include <iostream>
#include <unordered_map>

class MyClass
{
public:
    char a;
};

int main()
{
    std::unordered_map<int, MyClass&> MyMap;
    MyClass obj;
    obj.a = 'a';
    MyMap.emplace(1, obj);
    std::cout << MyMap[1].a;
}

有了这些错误消息:

Error   1   error C2440: 'initializing' : cannot convert from 'int' to 'MyClass &'  c:\program files (x86)\microsoft visual studio 12.0\vc\include\tuple    746

Error   2   error C2439: 'std::pair<const _Kty,_Ty>::second' : member could not be initialized  c:\program files (x86)\microsoft visual studio 12.0\vc\include\tuple    746

当我将其更改为指针时,它编译得很好.引用在std :: unordered_map中作为值类型无效吗？

使用boost :: unordered_map时,相同的代码可以正常工作.

在 C++14 中，我有一个std::vector值，我想删除与给定值匹配的所有元素，并且我不关心在删除后保留元素的顺序。规范规定std::remove保留剩余元素的相对顺序。

是否有内置算法可以执行类似 a 的操作std::remove，但不保留顺序？我希望这样做，因为将向量末尾的元素交换到要删除的位置的工作量较少，从而打乱向量中元素的顺序。该算法仍然是线性的，因为它必须访问每个元素来检查是否被删除，但如果最终只有少数项目被删除，那么它必须在每个元素上执行的持续工作量就会大大减少。