标签: unordered-map

我需要一个可搜索的GUID集合(存储为16个字节),其中实际的唯一ID是智能指针结构/类的成员.这是引用计数并由"最后引用删除"基础上的其他对象指向 - 类似于std::shared_ptr.但由于我的智能指针类的自定义性质,我不想使用shared_ptr.

不过,我确实想使用类似std::unordered_map或std::unordered_set(如果他们足够快)持有的指针的集合.

即使智能指针地址是唯一的,因此最好用作哈希,我需要表中的可搜索键作为GUID; 这样我就可以find(guid)用来快速找到正确的智能指针.

难以用文字解释,所以这里有一些代码:

class SmartPointer
{
public:
   GUID guid;
   int refCount; // Incremented/decremented when things point or stop pointing to it.
   void* actualObject; // The actual data attached to the smart pointer.
};

// Generate a unique 128-bit id.
GUID id;

// Create the smart pointer object.
SmartPointer* sp = new SmartPointer();
sp->guid = id;

// Create a set of SmartPointers.
std::unordered_set<SmartPointer*> set;
set.insert(sp);

// Need …

我正在研究C ++ unordered_map容器类型。我只是在验证我从C ++网站上读取的有关使用operator []进行元素访问的内容。

它说时间复杂度通常是恒定的，但最坏的情况是线性时间。由于我的应用程序必须保证可以恒定时间访问此映射内的元素，因此我想验证对容器的理解。

每当我的应用程序访问此unordered_map内的元素时，它所寻找的对象肯定存在，因此容器将永远不会尝试添加缺少的元素。由于我只进行查找，这是否意味着unordered_map将始终为我提供恒定的访问时间？的线性时间的情况下只适用于某些情况下，一个插入会发生，是正确的吗？

编辑：unordered_map内部的元素保证是唯一的。它们保存内存中存在的几个唯一对象的地址。

我知道在构建一个无序的地图时M,我会准确插入k元素.我应该如何选择铲斗的数量M？

我正在考虑n = 10*k在尺寸和碰撞机会之间进行合理的权衡.

C++标准是否有效地要求std::unordered_map在内存中将每个键和值放在一起的符合实现？

我认为答案是肯定的,因为大部分内容std::unordered_map是按照术语来规定的std::pair,我不认为隐藏内存中不相交的键值对的细节所需的操作可以完全隐藏,但我不确定.

所以我可以说我声明了一个像这样的unordered_map:

unordered_map<string, vector<string>> my_map;

我有一个我想要存储在其中的值列表,如下所示:

vector<string> vec1 = {"banana", "apple"}; 
vector<string> vec2 = {"banana", "banana"};
vector<string> vec3 = {"banana", "watermelon"};

如果我通过并将每个向量初始化到地图,使用其第0个索引中的字符串作为键,如下所示:

my_map[vec1[0]] = vec1;
my_map[vec2[0]] = vec2;
my_map[vec3[0]] = vec3;

unordered_map是否会存储所有三个向量,尽管它们具有相同的访问密钥？如果我想访问每个向量,有没有一种方法可以按照上面列表中出现的顺序执行此操作？

例如,如果我这样做:

 vector<string> output1;
 vector<string> output2;
 vector<string> output3;

 output1 = my_map["banana"];
 output2 = my_map["banana"];
 output3 = my_map["banana"];

哪些向量将分配给output1,output2和output3？我很确定它会为所有人提供相同的矢量但是unordered_map如何决定哪一个？我怎样才能使vec1被分配给output1,vec2到output2等？

我正在尝试编写康威的"生命游戏".在接近我的目标时,我遇到了编译错误:

C2338:C++库不提供此类型的哈希值.

起初我使用了SFML类sf::Vector2D.当它无法为我工作时,我写了一个属于我自己的类,希望我能实现丢失的hashCode方法.

我的问题是:
是否可以使用我自己的类使用自己的hashCode方法std::unordered_map？我需要使用一个可以容纳两个数字的类.(我也尝试过std::tuple,但是struct东西).

这是我的一张代码:

#include "GameMechanics.h"



GameMechanics::GameMechanics(Elements * elements):elements(elements)
{
    this->refreshTime = 1000000;    //ms
    this->clock.restart();
}


GameMechanics::~GameMechanics()
{
}

bool GameMechanics::isRunning()
{
    return this->running;
}

void GameMechanics::setRunning(bool running)
{
    this->running = running;
}

void GameMechanics::loop()
{

    unsigned passedTime = clock.getElapsedTime().asMicroseconds();  //check passed time since the clock got restarted
    this->timeHeap  +=  passedTime; //add passed time to the timeheap
    this->clock.restart();
    //only refresh every "refreshTime" seconds
    if (timeHeap >= …

如果我试图保存一个int和一个std::thread在std::unordered_map<int, std::thread>一切似乎工作正常.

但是,如果我包装std::unordered_map,那么我在标准库中得到一个错误.

错误是: no matching constructor for initialization of '_Mypair'

有没有办法解决这个问题,并在它被包裹时使其工作？

这有效:

Source.cpp

#include <thread>
#include <unordered_map>

void display() {}

int main()
{
    std::unordered_map<int, std::thread> map_;
    std::thread tempThread(&display);
    map_.emplace(0, std::move(tempThread));

    return 0;
}

这不起作用:

MapperWrapper.h

#ifndef MAPPERWRAPPER_H
#define MAPPERWRAPPER_H

#include <unordered_map>
#include <utility>

template <typename KeyType, typename valueType> class MapperWrapper
{
    public:
        void add(KeyType key, valueType value)
        {
            mapper.emplace(std::make_pair(key, value));
        }

    protected:
        std::unordered_map<KeyType, valueType> mapper;
};
#endif // MAPPERWRAPPER_H

Source.cpp

#include …

假设我有例如a std::unordered_map<K,std::set<int>> table.在循环:

for(auto it = table[k].begin(); it != table[k].end(); ++it){}

是否会在每次迭代时调用K的哈希运算符()？编译器g++带有标志:-m64 -g -std=c++11 -O3

在考虑重复之前,请理解我的问题的基础.

为什么C++ std::map接受a std::pair作为键类型,但是a std::unordered_map不接受？

第一个案例完美编译:

#include <map>
#include <utility>

using namespace std;

typedef pair<int,int> int_pair;

int main()
{
    map<int_pair,int> m;

    return 0;
}

第二种情况给出了大量的编译错误.从这个SO问题和这个SO问题中可以清楚地看出,必须创建自定义散列函数和等价运算符.

#include <unordered_map>
#include <utility>

using namespace std;

typedef pair<int,int> int_pair;

int main()
{
    unordered_map<int_pair,int> m;

    return 0;
}

这里的问题不是如何编写哈希函数std::unordered_map.问题是,为什么在不需要的时候std::map需要一个人？

我知道std::map是一个二进制搜索树(BST),但是在非基本类型(int_pair)的键之间进行比较的确切程度如何呢？

我试图知道两个给定的数组是否相等，与元素的排列无关，但包含相同的元素，并且所有元素的频率必须相同。

    int SameArray(int arr1[], int arr2[], int N, int M)
    {
        unordered_map<int, int> ump;
        if(N == M)
        {
            for(int i = 0; i < N; i++)
            {
                ump[arr1[i]]++;
            }
            for(int i = 0; i< M; i++)
            {
                if(ump.find(arr2[i]) != ump.end())
                    ump[arr2[i]]--;
            }
            if(ump.empty())
            return 1;
        }
        return 0;
    }

它没有显示任何错误，但输出始终为0。