3 ms·
Removal of an element in a vector is definitely O(n), regardless of cache effects.
by detrino 13y ago
Removal of an element in a vector is definitely O(n), regardless of cache effects.
- mihai_ionic 13y agotemplate <typename T> void remove(std::vector<T>& v, std::size_t i) { std::swap(v[i], v.back()); v.resize(v.size() - 1); }
- detrino 13y agoThat's just a different algorithm that produces different results than .erase() and has nothing to do with cache.
- alexchamberlain 13y agoNo one is saying it is not O(n), they're just saying that the cache effects can be larger than the complexity hit.
- detrino 13y agoExcept the parent did make that claim.