I have around 8,000, and sometimes 14,000 instances of this structure, stored in a TArray.
My problem is that I need to search one instance using its Identifier, and sometimes using its Mag. So, I’ve though to create two TMap, one using Identifier as the key, and the other one using Mag as the key. But, I don’t know if it is a good design or I’m wasting a lot of resources having two TMap.
You really want everything in one container, that is the best practice.
If there is a single clear key such as a GUID “ID” then you can create a TMAP with the GUID as key. When you want the “key” to be present in the data of the value, or when there is no common single key, you put everything in a struct like you did already and collect that struct in a TArray.
Using the structure you provided, To get the element you want you need to filter the TArray by a value within the struct. This can be done with a predicate.
// TArray<FBall> Balls; // Containing data.
const int32 SomeIdentifier = 50;
const FBall* TheBallPtr = Balls.FindByPredicate([SomeIdentifier] (const FBall& BallInArray) { return BallInArray.Identifier == SomeIdentifier }; );
if (TheBallPtr != nullptr) {
// Do something with it.
}
I recently explained how this works in another topic, see post 2 and 3 here:
which is why you can filter all data by predicate like I showed.
const bool bGetByMag = true;
TArray<FBall> Balls; // filled with your structs.
const int32 SomeIdentifier = 50;
const FBall* TheBallPtr = Balls.FindByPredicate([SomeIdentifier, bGetByMag] (const FBall& BallInArray) { return (bGetByMag ? BallInArray.Mag == SomeIdentifier : BallInArray.Identifier == SomeIdentifier) }; );
if (TheBallPtr != nullptr) {
// Do something with it, you found it.
}
In this code sample a pointer to the ball in the ball array is retrieved by the “key” from the array, be it the Mag or the Identifier. You only need this.
FindByPredicate looks like more complex than using two TMap.
That’s correct. FindByPredicate is linear search by checking each element
FilterByPredicate()
/**
* Filters the elements in the map based on a predicate functor.
*
* @param Pred The functor to apply to each element.
* @returns TMap with the same type as this object which contains
* the subset of elements for which the functor returns true.
*/
template <typename Predicate>
TMap<KeyType, ValueType> FilterByPredicate(Predicate Pred) const
{
TMap<KeyType, ValueType> FilterResults;
FilterResults.Reserve(Pairs.Num());
for (const ElementType& Pair : Pairs)
{
if (Pred(Pair))
{
FilterResults.Add(Pair);
}
}
return FilterResults;
}
While complexity of TMap’s [] is at most O(log n), probably even lower due to hashing, can’t properly evaluate it right now.
So, if your struct as lightweight as shown on your snippets, two maps with structs as values should be fine. If your structs are ways heavier (like, each map is a hundred of megabytes) then you can store pointers as values.
Overall, yes, this is the simple way of sacrificing of a bit of memory for speed.
Nevertheless, you can estimately run a linear search over 15k elements like 10k~ times per second. Probably a bit less in UE since that second is already have a plenty of work to do.