TMap with custom struct as key able to make duplicate keys

Development Programming & Scripting C++
, , ,
1

I have a custom struct I’m trying to use as a key.

I’m able to make a TMap<FMyStruct, FSomeValue> and add duplicate keys. I’ll post my code for the struct below, seems pretty normal to me. Any help appreciated.

Just as a reference also - I’m testing this not PIE just in the editor by having this struct live on a UObject derived class that is instance exposed and exposed on spawn as a variable in an Actor blueprint. I’m using an instance of that actor blueprint with some call in editor functions to call the add functions on my object. However, I got the same behavior in blueprint using the TMap directly exposed as a UPROPERTY(BlueprintReadWrite).

USTRUCT(BlueprintType, Category = "ImportTools")
struct FMyStruct
{
	GENERATED_BODY()
	 FMyStruct(){};
	 FMyStruct(const FString& InMyStruct, const FString& InMyStruct2)
	{
		 MyStructName =  InMyStruct;
		 MyStructName2 =  InMyStruct2;
	};

	UPROPERTY(EditAnywhere, BlueprintReadOnly, Category = "Device")
	FString MyStructName = FString("NONE");

	UPROPERTY(EditAnywhere, BlueprintReadOnly, Category = "Device")
	FString MyStructName2 = FString("NONE");

	bool operator==(const  FMyStruct& Other) const
	{
		return Equals(Other);
	}

	bool operator!=(const  FMyStruct& Other) const
	{
		return !Equals(Other);
	}
 	bool Equals(const  FMyStruct& Other) const
	{
		return MyStructName == Other.MyStructName && MyStructName2 == Other.MyStructName2;
	}
};

FORCEINLINE uint32 GetTypeHash(const  FMyStruct& This)
{
	const uint32 Hash = FCrc::MemCrc32(&This, sizeof(FMyStruct));
	return Hash;
}

I have also tried this with a TSet with no issues it’s just TMap that is giving me trouble.

2

I also get mixed results when I run .Find(). Sometimes I’m able to get a valid pointer and other times not using the same key run over run.

I’m confirming my results by just printing both FString fields in the key by for eaching all the keys in the map.

3

You should be using TMultiMap instead of TMap. That container is explicitly able to store the same key multiple times. You’re probably breaking some invariant by having two struct instances that return different hash values but still compare equal.

Compare with the std::hash reference which explicitly states the following requirement:

For two parameters k1 and k2 that are equal, std::hash<Key>()(k1) == std::hash<Key>()(k2)
std::hash - cppreference.com

TMap assumes that two items that compare as equals using Matches will also return the same value from GetKeyHash
Map Containers in Unreal Engine | Unreal Engine 5.0 Documentation

4

I don’t want to have duplicate keys - If .Add() is called for TMap and the same key exists I want to override the value associated with that key. I want to enforce uniqueness and TMultiMap is also not compatible with reflection yet. I agree though, something is wrong with my setup where the hash is different but Equals returns true.

5

Ah I thought you wanted to be able to add the same key again and store both values in the map instead of overwrite the existing value. Hence the suggestion to use TMultiMap.

This should fix your GetTypeHash to return the same value for instances of FMyStruct that compare equal. The TMap should work from there.

FORCEINLINE uint32 GetTypeHash(const  FMyStruct& This)
{
	return HashCombine(GetTypeHash(This.MyStructName), GetTypeHash(This.MyStructName2));
}
1 Like
6

Seems to have the same issue -

I modified the code just slightly for clarity.

Screenshot of an FMyStruct being created with duplicate keys. I tested this with variable being expose on spawn and instance editable - the details panel on the instanced actor can also create duplicates. Though one thing to note - if you restart the editor or recompile the blueprint the duplicates are only then removed.

If I use an already supported unreal type like TMap<FString, FSomeVal> then it works as intended.

image
image490×944 39.5 KB

Actual Code Used → 

USTRUCT(BlueprintType, Category = "Testing")
struct FMyStruct
{
	GENERATED_BODY()

	FMyStruct()
	: FMyStruct(TEXT("None"), TEXT("None"))
	{}

	FMyStruct(FString InString1, FString InString2)
	: String1(InString1), String2(InString2)
	{}

	FMyStruct(const FMyStruct& Other)
	: String1(Other.String1), String2(Other.String2)
	{}

	UPROPERTY(EditAnywhere, BlueprintReadOnly, Category = "Testing")
	FString String1;

	UPROPERTY(EditAnywhere, BlueprintReadOnly, Category = "Testing")
	FString String2;

	FORCEINLINE bool operator==(const FMyStruct& Other) const
	{
		return Equals(Other);
	}

	FORCEINLINE	bool Equals(const FMyStruct& Other) const
	{
		return (String2.Equals(Other.String2) && String1.Equals(String1));
	}
};

FORCEINLINE uint32 GetTypeHash(const FMyStruct& This)
{
	return HashCombine(GetTypeHash(This.String1), GetTypeHash(This.String2));
}
7

In actually testing this with code it now does work as intended for .Add() and .Find() in TMap! Though the blueprint problem still remains, and that may be a bug.

If you could though, slightly elaborate on why GetTypeHash() with HashCombine works over just getting the size of the struct directly?

8

Just tested this with a key struct created in blueprint and while the map property allows me to add the duplicate key first, compiling the blueprint removes those again.

Your version of GetTypeHash is still combining the hash of This.String1 with itself instead of combining the hashes of This.String1 and This.String2. The problem with the MemCrc32 implementation is that any two instances of the struct that hold the same values in String1 and String2 may compare equal, but each of the Strings may point to a different memory location where the actual contents of the string are stored. And since MemCrc32 only looks at the first level of memory (i.e. it does not follow the pointers to the actual text stored in the strings) it only sees the different memory locations of the string resulting in a different hash.

Here is a small Compiler Explorer example that hopefully makes this clearer.
Notice how the “test” string in both ks1 and ks2 causes the same output from the memoryHexDump function? That’s because the implementation of std::string in MSVC is able store small strings in its own memory without requiring any additional (dynamic) allocations. For the MemCrc32 these strings would result in the same hash (assuming that all bytes of the string are actually initialized to the same values and don’t have any uninitialized bytes with random data left over).
The second string “very long string” exceeds the limit so it requires an additional (dynamic) allocation. This happens for both ks1 and ks2 meaning they each get the memory required to hold their text contents. As you can see from the output these are stored at different addresses. MemCrc32 only sees these instead which would automatically result in different hashes.

The output looks different between compilers and optimizations may also change the output slightly.

1 Like
9

A yes, that was a typo, I went ahead and edited it out for the next person.

Wow, that really gave me a brain wrinkle. Great insight! Thank you so much for your time.