Thread: "Shrinking" an array, but keeping original indices results in a small bottleneck

Hi! I wrote a piece of code to delete some elements from an array. With deleting I'm saying: replacing the original values by 0. I don't know another way to keep the indices of the other elements at the same place. I can't just delete elements by placing them at the end and then creating a new array without the elements at the end, since then I'll end up with different indicies for the elements that I still need.

So my solution is like this:

Code:

//Step #3: Remove old edges from edgeslist and heap
      int aantal = 0;     
      for(edge=0;edge<nbEdges;edge++) { 
        for (i=0; i<nbVertsCells[delVert]; i++) {  
          ver2 = vertsCells[delVert][i];
          if( !fixed2[ver2] && ((EdgesList[edge][0] == delVert) && (EdgesList[edge][1] == ver2)) ) {
              //Remove old Edges from the edgeslist
              EdgesList[edge] = new unsigned int[2];
              EdgesList[edge][0] = 0; //set elements to zero. Adding at the end in the future?
              EdgesList[edge][1] = 0;
              delEdge = edge;
              //Remove old Edges from the Heap
              heapRemoveEdgeValue(nbEdgesHeap, heapEdges, posEdges, errorCells2, delEdge);
              delEdgeInd[aantal] = delEdge;
              aantal++;
              
          }
        }
      } 
      
         
      //Step #4: Add new edges to edgeslist
      for(i=0;i<nbNewEdges;i++) {
            //EdgesList[delEdgeInd[i]] = new unsigned int[2];
            EdgesList[delEdgeInd[i]][0] = (unsigned int)FinalEdgesList[i][0];
            EdgesList[delEdgeInd[i]][1] = (unsigned int)FinalEdgesList[i][1];
            delete[] FinalEdgesList[i];
      }
      delete[] FinalEdgesList;

Unfortuantely this piece of code seems to bug a little, when testing it takes VERY long to pass this part. Is there something wrong with my approach? I just put som elements to zero and afterwoods I use these empty place to add new elements into it. Since nbNewEdges is smaller then the amount of zeros created, there'll always be some elements in EdgesList[][] who are still both zero.

Can anyone help me out with debugging this? There's not really an error or something, but like I said: I think there's a bottleneck in it...

This looks like C++ code, so I am moving this thread to the C++ programming forum.

What is the point of deleting elements if you just set them to 0?

So is this for an edge list based software 3D renderer?

If so, I can share some code of how to do it the most efficient way. You basically use doubly-intrusive lists, one of which is the deletions list. The nodes themselves actually come from a preallocated buffer, so you have a similar cache performance to what you would with an array.

Originally Posted by Elysia

What is the point of deleting elements if you just set them to 0?

And what's the point of setting elements to 0 if you're going to delete them?

If you no longer need to access the element at index 1234 in the array, then... don't access it.