Modifying Algorithms and Iterator Safety
Deslize para mostrar o menu
When using modifying STL algorithms like std::remove or std::rotate, be aware of iterator invalidation. These algorithms can reorder or overwrite elements, making previously obtained iterators invalid. For example, std::remove shifts elements, and std::rotate rearranges their order. Knowing which iterators remain valid after such operations is essential for writing safe, correct code.
main.cpp
123456789101112131415161718192021222324252627282930313233#include <iostream> #include <deque> #include <algorithm> int main() { std::deque<int> dq = {1, 2, 3, 4, 5, 6}; // Get an iterator to the third element auto it = dq.begin() + 2; // Use std::remove to move all 3's to the end (simulate removal) auto new_end = std::remove(dq.begin(), dq.end(), 3); // Erase the "removed" elements dq.erase(new_end, dq.end()); // Use std::rotate to shift elements std::rotate(dq.begin(), dq.begin() + 1, dq.end()); // Check if our old iterator is still valid // (it originally pointed to the value 3) if (it != dq.end()) std::cout << "Iterator points to: " << *it << std::endl; else std::cout << "Iterator is at end" << std::endl; // Print the deque after modifications std::cout << "Deque contents: "; for (int n : dq) std::cout << n << ' '; std::cout << std::endl; }
In this example, an iterator is taken before applying modifying algorithms. After std::remove, elements are rearranged and a new logical end is produced. Calling erase then changes the container’s size and shifts elements, which can invalidate existing iterators. The subsequent std::rotate further reorders elements and may also invalidate iterators. For std::deque, both erasing and rotating can make previously stored iterators unsafe to use, highlighting the need to understand iterator validity when applying modifying algorithms.
main.cpp
123456789101112131415161718#include <iostream> #include <deque> #include <algorithm> int main() { std::deque<int> dq = {1, 2, 3, 4, 5}; // Get an iterator to the second element auto it = dq.begin() + 1; // Remove the second element using erase dq.erase(it); // Mistake: try to use 'it' after erasure // This is undefined behavior! std::cout << "Using invalidated iterator: " << *it << std::endl; }
This code shows a common mistake: after erasing an element from a container like std::deque, any iterator pointing to that element, and possibly others, becomes invalid. Dereferencing such an iterator after erase leads to undefined behavior, causing crashes or incorrect results. To avoid this, always check when operations invalidate iterators. When a container is modified in a way that may invalidate iterators, do not reuse old iterators. Instead, re-acquire them or adjust your logic to account for the changes.
Best practice: After performing container modifications that might invalidate iterators, always obtain new iterators for further operations. Never assume that previously acquired iterators remain valid unless the documentation explicitly guarantees it.
Obrigado pelo seu feedback!
Pergunte à IA
Pergunte à IA
Pergunte o que quiser ou experimente uma das perguntas sugeridas para iniciar nosso bate-papo
