Erase One Element From Vector C++

[Jackie Bullinger]

erase() function, on the other hand, is used to remove specific elements from the container or a range of elements from the container, thus reducing its size by the number of elements removed.

If you look closely, vec.begin() is just a pointer to the starting position of our vector and adding the value of i to it increments the pointer to the position i. So, we instead can access the pointer to the ith element with &vec[i]:

The reason is that indices are affected by erase so if you remove the 4-th element, then the former 5-th element is now the new 4-th element, and it won't be processed by your loop if you're doing i++.

The code takes every number in vec that can't be divided by 3 and copies it to vec2. Afterwards it copies vec2 in vec. It is pretty fast. To process 20,000,000 elements this algorithm only takes 0.8 sec!

With this, you will erase the nth element of vec but before you erase the second element, all the other elements of vec will be shifted and the vector size will be reduced by 1. This can be a problem as you may be looping through vec while its size() is decreasing.

Here there is a single parameter, position which is an iterator pointing to a single element to be removed from the vector.Member types iterator and const_iterator are random access iterator types that point to elements.

The return value is an iterator pointing to the new location of the element that followed the last element that was erased by the function call. This is the container end of the operation that erased the last element in the sequence.

The previous answers assume that you always have a signed index. Sadly, std::vector uses size_type for indexing, and difference_type for iterator arithmetic, so they don't work together if you have "-Wconversion" and friends enabled. This is another way to answer the question, while being able to handle both signed and unsigned:

Your specific problem is that your Player class does not have an assignment operator. You must make "Player" either copyable or movable in order to remove it from a vector. This is due to that vector needs to be contiguous and therefore needs to reorder elements in order to fill gaps created when you remove elements.

You might need to write such a loop explicitly e. g. if you need the iterator itself to determine if the element is to be removed (the condition parameter needs to accept a reference to element, remember?), e. g. due to specific relationship to successor/predecessor (if this relationship is equality, though, there is std::unique).

Linear: the number of calls to the destructor of T is the same as the number of elements erased, the assignment operator of T is called the number of times equal to the number of elements in the vector after the erased elements.

You could use the same technique as std::vector::erase() uses - shifting items ina tail to newly free space. But it is not thread-safe in terms of parallel access to the same items. And it doesn't deallocate the memory.

Sure, you could add lots of hooks to concurrent_vector, but those additions would probably make it a whole lot slower. Marking vector entries as invalid requires a flag per element. You could embed it with each entry (has implications for the user type used to define the vector element) or collect them all together somewhere else (forcing more cache lines to be available for simple array access and possibly introduce false sharing issues). Either way, the accessor methods would be complicated by extra checking to avoid entries that have been marked invalid. Currently the accessor does a simple two-level lookup to find the segment and the index within the segment:

Moreover, the thing that makes TBB concurrent vector philosophically different than its STL equivalent is that the allocations are never relocated as would have to be done withthe suggested compact() operation. It's more important to preserve vector locations and any cache residency that may be based on that memory layout than to provide operations that might disrupt the current cache context. Doing a compact to remove invalid elements is directly counter to that philosophy.

There is nothing to prevent you from defining a vector element type that contains a validity flag. You could easily perform some experiments on this to convince yourself of the extra overhead that would be required to add such features.

Perhaps Arch or Alexeycould come up with appropriate "template programming tricks" to trick out the expanded concurrent_vector you suggest, but I doubt it. Everything from constructors down to accessors would have to be duplicated in order to have versions that check for validity and take the performance hit. And for what? a version of concurrent_vector that doesn't scale but at least is type-safe? I think there are more important things for the development team to worry about, but that's just me.

While I'm here, let me make one little adjustment to your statementon the problem of carrying validity bits in a bit mask. It's not moving elements around internally that will hurt performance. It's the fact that the bit mask is probably going to be in cached memory, which means, if you're really talking bits, that each flag shares a cache line with up to 511 of its neighbors. Any thread writing a bit needs to pull that part of the bit mask into its local cache/store buffers, which means that threads could serialize on the validity test. At least if the validity bits are distributed with the elements, collisions are less likely.

Engineers? Where? I was a physics and math major when I was in school. And I love having a job that makes me deal with questions like those you raise, because it makes me strive to become more knowledgable, in order to help you (that's the collective "you").

Books from Intel Press? They're all great! Honestly, I must say that I don't own any of the books in the quartet referenced in your last post. I did do some review work on the first edition of Rich Gerber's book, and I looked over the table of contents of Shameem's book and found it to have reasonable coverage, but Ihaven't gotten a copy yet. Stewart Taylor's book is about Intel Integrated Performance Primitives and James Reinders' is about VTuneAnalyzer; neither is likely to explain much about multi-core programming issues asa primary topic, but either of the first two could be useful.

Intel does not verify all solutions, including but not limited to any file transfers that may appear in this community. Accordingly, Intel disclaims all express and implied warranties, including without limitation, the implied warranties of merchantability, fitness for a particular purpose, and non-infringement, as well as any warranty arising from course of performance, course of dealing, or usage in trade.

I am using a "std::vector myvec" that holds temporary data. A random element in the vector may be erased at any time. I don't want to use the std::vector::erase method as it will shuffle all elements which degrades performance.

AFAIK, std::vector needs to guarantee contiguous storage at all times, so I don't think there's any way to avoid memory moves when you delete an item. Std::list does not have that requirement, and it is designed specifically for random deletions and insertions. However, it does not provide random access (by index).

Another thing you could do if you still need to work with std::vector is to mark items as deleted instead of actually deleting them. For basic data types, you could reserve a specific value (like NULL for pointers) as meaning "deleted item". For structures and classes, you probably already use pointers, so NULL is good. If not, you could add a member m_bIsDeleted.

If by "items don't have destructors" you mean to say that your items are not pointers to objects, structures or other data, then no, there is not way to avoid a copy/move (actually three - one for the first item being moved to aux, one for the second item being moved into the first, and one for aux being moved to the second item).

Out of curiosity, does anyone know if there is any chance the swap can be optimized to a move when the items don't have destructors?
I guess that could be difficult unless the memory in the vector is actually shrunk..
Not that it should really matter, but for large POD types it seems unnecessary to exchange the memory instead of just copying.

Erasing an element in a vector is O(n) as we have to remove the element and still need to shift all successive elements to fill the gap created. If a vector has n elements, then in the worst case we will need to shift n-1 elemets, hence the complexity is O(n).
in your example , vec[i] will give 3

3x10^5 is the upper bound, it takes 4.77 second to run for it.
I guess, in 1 second, we have about 10^7 instructions, so for n=3x10^5, we are executing 4.7x10^7 instructions, maybe u can compare different values and find out the order based on it.

I feel it passes 10^5 because we are doing just a single operation, under which we must take other factors in consideration. Instructions per second are around 10^8 to 10^9, so constant factors cannot be neglected. We will have to go onto finer details like calculating exact operations using O(n(n-1)/2) etc.

I have an array of IDs and I want the user to be able to select which ones they want to delete. I used dialoguer::MultiSelect for this. It returns a vector of indices of the elements selected. But as shown in the example above, removing multiple elements using their indices isn't that straight forward. I searched online but I couldn't find anything about this (for Rust at least). My only solution so far is to put the contents of these indices in another vector (say vec_buf) and then iterate through each element in vec_buf, removing the element from vector using their content. But this is a terrible solution so does anyone have a more idiomatic solution?

c80f0f1006