Project 11.05 Section 11 ⚡ Embedded Relevance: High Erase-Remove std::remove Iterator Invalidation C++20 std::erase Memory Compaction

11.05 In-Place Vector Compaction, Iterator Invalidation, and C++20 std::erase

Executive Summary: Understanding the separation of algorithms from containers in C++. We dissect why std::remove does not alter container size, analyze iterator invalidation hazards during array filtering, and review C++20 std::erase.

💻 1. Annotated Source Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void printVector(const vector<int>& vec);

int main() {
	vector<int> numbers = { 1, 2, 3, 2, 4, 2, 5, 2 };

	cout << "Original vector: ";
	printVector(numbers);

	//step 1: use remove
	auto newEnd = remove(numbers.begin(), numbers.end(), 2);

	//step 2: erase them from container
	numbers.erase(newEnd, numbers.end());

	cout << "Vector after removing all 2s: ";
	printVector(numbers);

	return 0;
}

void printVector(const vector<int>& vec) {
	for (int value : vec) {
		cout << value << " ";
	}
	cout << endl;
}

📐 2. Architecture & UML Class Model

📐 Erase-Remove Idiom & std::erase / std::erase_if (C++20)

+ Public - Private # Protected

<<compilation-unit>> EraseRemovePipeline Iterator Algorithm

Attributes / Data Members

(none / stateless)

Operations / Methods

+eraseRemoveClassic(vec: vector<int>&, val: int) : void[vec.erase(std::remove(...), vec.end())]

+eraseModernCpp20(vec: vector<int>&, val: int) : size_t[std::erase(vec, val)]

📚 3. Core C++ Concepts Deep-Dive

1. The Two-Step Remove-Erase Idiom

In standard C++, std::remove only shifts non-matching elements to the front of the range and returns a past-the-end iterator. It cannot alter the container's size() because generic algorithms operate only on iterators without knowledge of container topology. The container's erase() method must be called to truncate the tail.

📚 Concept Implementation

vec.erase(std::remove(vec.begin(), vec.end(), targetValue), vec.end());

⚡ 4. Embedded Systems & Hardware Reality

1. Deterministic In-Place Compaction

The remove-erase idiom operates strictly in-place with $O(N)$ linear time and $O(1)$ auxiliary space. In embedded sensor filtering (e.g. stripping corrupted checksum packets from an acquisition buffer), in-place compaction avoids allocating secondary temporary buffers.

⚠️ Iterator Invalidation Hazards

Calling erase() invalidates iterators pointing to deleted and subsequent elements. Performing manual loops with vec.erase(it) without updating it = vec.erase(it) results in undefined memory dereferences.

💡 5. Production-Ready Embedded Refactoring

In modern C++20, the verbose two-step idiom is replaced with uniform, clear std::erase:

💡 Production-Ready Refactor

#include <vector>
#include <iostream>

int main() {
    std::vector<int> sensorReadings = {10, -999, 25, -999, 32};

    // Modern C++20: Single expressive call
    std::erase(sensorReadings, -999);

    for (int val : sensorReadings) {
        std::cout << val << ' '; // Prints: 10 25 32
    }
    return 0;
}

📝 Knowledge Verification Quiz

Test your understanding of the C++ concepts and embedded microcontroller trade-offs covered in this guide. Click any option for instant feedback.

Q1. Why does std::remove(vec.begin(), vec.end(), val) not change the size of the vector by itself?

A It is a bug in the standard library.

B std::remove operates solely on iterators and has no member access to the underlying container's size or memory allocator.

C It only marks elements as invisible.

D It converts elements to nullptrs.

Detailed Explanation: STL algorithms are decoupled from containers. std::remove moves valid elements to the front and returns an iterator to the new logical end, requiring vec.erase() to deallocate the remaining tail.

Q2. What is the time complexity of the Erase-Remove idiom on a contiguous array of N elements?

A O(1)

B O(N) linear time with O(1) extra memory

C O(N^2) quadratic time

D O(log N)

Detailed Explanation: The algorithm makes a single pass over the elements ($O(N)$ comparisons and moves) and shifts elements in-place with zero additional memory allocation.