Are there any faster way to erase elements from std::vectors?

Question

I'm trying to upgrade from C to C++, and I'm having a lot of issues to get used to it. In C, I'm used to work with pointers and linked list, but that is some tiresome job. Then, I was introduced to std::vectors, and the world become prettier. Until I had to work with really huge vectors (a vector of 3 million of small vectors (usually some vector<short>)). Then my nightmare started. The operation is simply (described below).

vector<vector<short>> v;
v = build(); \\create all 3 million of small vectors
for(int i = 0; i < v.size(); i++){
   if(someReallyFastTest(v[i])){
      v.erase(v.begin() + i);
      i--;
   }
}

The program does its purpose, but takes days to finish. I tried to depurate the code and then I notice that the command

v.erase(v.begin() + i);

takes seconds to complete the task. Since in each turn I have to erase thousands of elements, it take hours to complete the task. I don't want to go back and work with pointers and linked list so soon. Is there any faster way to do this task?

Do you really need "3 million small vectors"? Can't you consolidate some of that data, or even reduce the amount of data? Or maybe at least use a single `vector` instead of a `vector` of `vector`s? — Remy Lebeau, Aug 13 '21 at 20:09
Tactical note: You may see significant performance improvement from `vector> v = build(); \\create all 3 million of small vectors`. The compiler can easily see that the result of `build` is only being used to initialize `v` and can take steps to eliminate copying. — user4581301, Aug 13 '21 at 20:09
If the order of your vector's elements are not important, do consider [a later answer](https://stackoverflow.com/a/59338794/16287) in the posted duplicate that notes that `std::partition` can be faster. — Drew Dormann, Aug 13 '21 at 20:23
`std::vector::erase` moves every element beyond the one that’s being erased down one position. So the code in the question is O(n^2) for removing multiple elements. `std::remove_if` is linear, i.e., much better here. — Pete Becker, Aug 13 '21 at 20:26
If you are looking at a lot of deletions and insertions, you may want to consider using `std::list`. Insertion and deletion are a matter of changing pointers (after the items are located), whereas a `std::vector` may have to copy all remaining items up a cell or more. — Thomas Matthews, Aug 13 '21 at 20:51
If your elements don't have to be in a particular order, you can copy the last element to the ith position and then truncate the vector by one element. — j6t, Aug 14 '21 at 10:35

Are there any faster way to erase elements from std::vectors?

0 Answers0