Most efficient way to find and then remove from a TArray?

Development Programming & Scripting C++
1

I’m basically trying to figure out the equivalent of an iterator erase in an stl vector. Here’s the example situation:

I have an array of structs. I do a find in that array using a predicate (e.g. checking against a member variable of the struct). I get a result which I then use in some way. At the end of the function, I delete that found object from the array.

Unless I’m mistaken, in STL, when erasing by iterator, it’s able to use the address of the iterator to directly access it. From what I can tell in the UE4 code, Remove is doing another find for the element in order to remove it. Remove does have an index version (RemoveAt), but since there is no version of Find that returns an index, it’s not possible to use that version in the above example.

Is there something I’m missing or is this just a performance hole in the UE4 code?

2

The most efficient way is to find the element you want,swap it with the last element of the array, and delete the last element. This way you avoid moving the rest of the elements to cover the “hole” left by the deleted element.
You can get it by using the Remove*Swap-like functions (RemoveSingleSwap, RemoveAtSwap, etc.) from TArray.

Of course, this is only possible when the order of the elements in the array does not matter.

1 Like
3

I think you missed the point of my post. I agree that swap and pop/erase unsorted is the most efficient way to erase, but that’s not my question. My issue is with the find. I don’t want to have to find in the array twice which is what has to happen right now in my example, as far as I can tell.

STL uses the address of the iterator to find the offset into the vector memory to know where to delete. This makes it very fast. TArray doesn’t use iterators so it has either Remove, which takes the element, or RemoveAt, which takes the index. RemoveAt does roughly the same as what I described for vector erase, but Remove does a find in order to get the index so that it can use it to erase. I want to eliminate that find.

4

Yep, I may not understand what you want to achieve. Maybe some code snippet make it clearer.

TArray<T>::Remove (T const & value) finds an element and removes it.



TArray<int> Values{0, 1, 2, 3, 4};
auto RemovedNum = Values.Remove(2);  // RemovedNum == 1, Values = {0, 1, 3, 4}
5

Here you go:



struct FComplexStuct
{
    FString Name;

    //A bunch of other variables
};

void DestroyThingByName(FString name)
{
    FComplexStuct* cs = thingArray.FindByPredicate(&](FComplexStuct& cs) { return cs.Name == name; });
    if (cs)
    {
        //Do some processing on cs i.e. cleanup and deinit

        thingArray.Remove(*cs); //This line will do another find
    }
}
6

Maybe try TMap or TLinkedList?

7

Those are completely different data structures and neither of which will work for my case. Regardless, it’s not the point of the discussion. Let’s keep this focused on TArray and what it is capable of doing.

It’s fully possible that the answer to my question is simply, yeah, that’s how it works and there’s no better way without touching the engine code.

8

The fastest way to find and remove a single item is by finding it’s index.



const int32 ItemIndex = Array.IndexOfByKey(Item); // or IndexOfByPredicate etc...
if (ItemIndex != INDEX_NONE)
{
      // Swap with last element, remove, don't change allocation.
      Array.RemoveAtSwap(ItemIndex, 1, false);
}

If you care about indices, you can use RemoveAt() instead (though this moves subsequent elements). The expensive part is reallocating, but you can optionally do so with the bool parameter.

Finding the element as a pointer is NOT the most efficient method because that requires two loops of the arrays’ contents.

If you want to remove many elements and change allocation size, I recommend removing first then calling Shrink();



// Remove a bunch of stuff without changing allocations
for (blah)
{
     Array.RemoveAtSwap(Index, 1, false);
}

// Shrink allocation to fit.
Array.Shrink();
5 Likes
9

Just use a TIndexedContainerIterator.



TArray<FName> MyNameList;
TArray<FName>::Iterator MyIterator = MyNameList.CreateIterator();

while(MyIterator)
{
   if (*MyIterator == FNAME_None)
   {
       MyIterator.RemoveCurrent();
   }
}
1 Like
10

This is the right answer. I wasn’t aware of IndexOfByPredicate. This allows both quick access to the item as well as use of RemoveAt/RemoveAtSwap.

11

So, this is simple remove_if algorithm.



void DestroyThingByName(FName Name)
{
  auto Remover = &Name](FComplexStruct& Item) -> bool {
    if (Item.Name == Name) {
      Item.DoSomeDestroy();
      return true;
    }
    return false;
  };

  auto Index = Algo::RemoveIf(ThingArray, Remover);
  ThingArray.SetNum(Index);
}