If the order of elements isn't important (fairly common) then you can do even better than invalidation - just swap the element you want deleted with the element on the end, and pop it off.
Of course, you have to be a little careful - if you're doing a `remove_if` loop, you have to remember to process the element that used to be on the end, and you need to make sure you don't iterate past the end of the (now shorter) array.
As for insertions in the middle, a vector may still be better than a linked list. If the vector is short you could win on that alone, but even if it's long it can be worth it.
Consider that the program you're writing probably doesn't consist entirely of middle-insertions into these data structures. If you iterate over those data structures with the same frequency as you insert into the middle, you're never not going to be O(n) there. The O(n) + O(1) = O(n) of the linked list iterate/insert may well be far slower than the O(n) + O(n) = O(n) of the vector iterate/insert for any n.
(And with binary search, your O(log n) + O(n) = O(n) may be faster again...)
Of course, you have to be a little careful - if you're doing a `remove_if` loop, you have to remember to process the element that used to be on the end, and you need to make sure you don't iterate past the end of the (now shorter) array.
As for insertions in the middle, a vector may still be better than a linked list. If the vector is short you could win on that alone, but even if it's long it can be worth it.
Consider that the program you're writing probably doesn't consist entirely of middle-insertions into these data structures. If you iterate over those data structures with the same frequency as you insert into the middle, you're never not going to be O(n) there. The O(n) + O(1) = O(n) of the linked list iterate/insert may well be far slower than the O(n) + O(n) = O(n) of the vector iterate/insert for any n.
(And with binary search, your O(log n) + O(n) = O(n) may be faster again...)