标签: unordered-map

当我std::unordered_map使用基于for循环的范围迭代两次时,顺序是否保证相等？

std::unordered_map<std::string, std::string> map;

std::string query = "INSERT INTO table (";
bool first = true;
for(auto i : map)
{
    if(first) first = false;
    else query += ", ";
    query += i.first;
}
query += ") ";

query += "VALUES (";
first = true;
for(auto i : map)
{
    if(first) first = false;
    else query += ", ";
    query += i.second;
}
query += ");"

在上面的示例中,结果字符串应采用该形式.因此,重要的是两个时间,迭代的顺序是相同的.

INSERT INTO table (key1, key2, key3) VALUES (value1, value2, value3);

这是用C++保证的吗？

StackOverflow上有几个答案表明以下循环是一种很好的方法来擦除std::unordered_map满足某些谓词的元素pred:

std::unordered_map<...> m;
auto it = m.begin();
while (it != m.end())
{
    if (pred(*it))
        it = m.erase(it);
    else
        ++it;
}

我对C++ 11(而不是C++ 14)特别感兴趣,而cppreference.com上的以下不祥之处表明上述循环依赖于未定义的行为,并且可能在C++ 11中无效:

保留未擦除元素的顺序(这使得可以在迭代容器时擦除单个元素)(从C++ 14开始)

另请参见标题2356.无序关联容器中擦除的稳定性,其中包含对第754页的工作草案N3797第14项的请求的措辞更改(附加短语开头",并保留相对顺序......").

这个措辞与N3797有关.

按照指示修改[unord.req],p14:

-14- insert和emplace成员不应影响对容器元素的引用的有效性,但可能使容器的所有迭代器无效.擦除成员应仅使迭代器和对已擦除元素的引用无效,并保留未擦除元素的相对顺序.

如果我对cppreference.com的注释的解释是正确的,并且上面的循环依赖于C++ 11中的未定义行为,那么在C++ 11中解决这个问题的最有效方法是什么？

我需要将一对映射long long到a double,但我不确定要使用什么散列函数.每对可以由任意两个数字组成,但在实践中它们通常是介于0和之间的数字100(但同样,这是不可保证的).

这是tr1::unordered_map文档.我开始是这样的:

typedef long long Int;
typedef std::pair<Int, Int> IntPair;

struct IntPairHash {
  size_t operator(const IntPair& p) const {
    return ...; // how to hash the pair?
  }
};

struct IntPairEqual {
  bool operator(const IntPair& a, const IntPair& b) const {
    return a.first == b.first 
      && a.second == b.second;
  }
};

tr1::unordered_map<IntPair, double, IntPairHash, IntPairEqual> myMap;

一般来说,我不知道要使用什么哈希函数.什么是一个很好的通用哈希函数？

考虑在迭代时从关联容器中删除元素的规范算法:

for (auto iter = myMap.begin(); iter != myMap.end(); )
{
    if (/* removal condition */)
    {
        iter = myMap.erase(iter);
    }
    else
    {
        ++iter;
    }
}

在使用C++ 11 std::unordered_map容器时,我一直在不加思索地应用这个算法.但是,在浏览cppreference.comstd::unordered_map::erase上的文档之后,在阅读以下注释后我变得有点担心:

保留未擦除元素的顺序(这使得可以在迭代容器时擦除单个元素)(从C++ 14开始)

基于这个陈述,我假设在C++ 14标准中添加了语言,以确保库实现者在调用后保证排序std::unordered_map::erase.例如,这样的要求可能会限制实现在删除元素后不重新整理整个容器,而只是允许它从相应的存储桶中删除元素？

如果我在C++ 11中没有这样的保证,并且如果我希望我的代码是可移植的,那么如果我std::unordered_map在迭代期间删除一个元素,我是否必须担心一些元素会被访问多次或根本不访问？

我的代码:

 typedef pair<int,int> Pair
  tr1::unordered_map<Pair,bool> h;
  h.insert(make_pair(Pair(0,0),true));

Erorr

 undefined reference to `std::tr1::hash<std::pair<int, int> >::operator()(std::pair<int, int>) const'

我需要修理什么？

谢谢

我想知道是否unordered_map使用类型擦除实现,因为unordered_map<Key, A*>并且unordered_map<Key, B*>可以使用完全相同的代码(除了强制转换,这是机器代码中的无操作).也就是说,两者的实现可以基于unordered_map<Key, void*>保存代码大小.

更新:此技术通常被称为精简模板成语(感谢下面的评论者指出这一点).

更新2:我对Howard Hinnant的观点特别感兴趣.我希望他读到这个.

所以我写了这个小测试:

#include <iostream>

#if BOOST
# include <boost/unordered_map.hpp>
  using boost::unordered_map;
#else
# include <unordered_map>
  using std::unordered_map;
#endif

struct A { A(int x) : x(x) {} int x; };
struct B { B(int x) : x(x) {} int x; };

int main()
{
#if SMALL
    unordered_map<std::string, void*> ma, mb;
#else
    unordered_map<std::string, A*> ma;
    unordered_map<std::string, B*> mb;
#endif

    ma["foo"] = new …

请考虑以下情况:

using namespace std;
unordered_map<int, vector<A>> elements;

现在我正在迭代这个无序的地图:

for (auto it = elements.begin(); it != elements.end(); ++it)

在循环内部,我正在形成几个元素elements(当前的一个it指向和更多的元素,不一定是那些在线的那些!).因为每个元素只能是一个集群的一部分,所以我想从地图中删除它们,然后继续下一个元素(即构建下一个集群).

我怎么能这样做并仍然在正确的位置继续迭代？

我知道如何使用std::unordered_map::emplace,但我该如何使用emplace_hint？cplusplus和cppreference都没有提供一组示例来说明我们如何知道放置元素的位置.

任何人都可以提供一些有关这方面的信息,或者提供一些示例/插图,告诉我们什么时候可以知道布置元素应该去哪里？

以下代码导致对哈希函数的无法解释的调用：

namespace foo {
    using Position = tuple <int, int, int>;
    
    std::ostream& operator<<(std::ostream& out, const Position& pos) noexcept{
        return out << get<0>(pos) << ", " << get<1>(pos) << ", " << get<2>(pos);
    }

    struct hashFunc{
        std::size_t operator()(const Position& pos) const noexcept{
            int res = get<0>(pos) * 17 ^ get<1>(pos) * 11 ^ get<2>(pos);
            cout << "@@@ hash function called for key: " << pos 
                 << ", hash: " << res << endl;
            return res;
        }
    };

    template<typename T>
    void print_buckets(T&& …

C++中的multimap看起来很奇怪,我想知道为什么

#include <iostream>
#include <unordered_map>

using namespace std;

typedef unordered_multimap<char,int> MyMap;

int main(int argc, char **argv)
{
    MyMap map;
    map.insert(MyMap::value_type('a', 1));
    map.insert(MyMap::value_type('b', 2));
    map.insert(MyMap::value_type('c', 3));
    map.insert(MyMap::value_type('d', 4));
    map.insert(MyMap::value_type('a', 7));
    map.insert(MyMap::value_type('b', 18));

    for(auto it = map.begin(); it != map.end(); it++) {
        cout << it->first << '\t';
        cout << it->second << endl;
    }

    cout << "all values to a" << endl;
    for(auto it = map.find('a'); it != map.end(); it++) {
        cout << it->first << '\t' << it->second << endl;
    }

}

这是输出: …