Show me most effective C++, single function implementation of an RLE encoding over…
- User
Show me most effective C++, single function implementation of an RLE encoding over std::vector<uint8_t>.
- Assistant
Here's an efficient C++ implementation of Run-Length Encoding (RLE) for a
std::vector<uint8_t>. This implementation is optimized for performance, handles edge cases, and uses a single function. The encoded output is also stored in astd::vector<uint8_t>, where each run is represented by two bytes: the count (length of run) followed by the value.#include <vector> #include <cstdint> #include <stdexcept> std::vector<uint8_t> rle_encode(const std::vector<uint8_t>& input) { if (input.empty()) { return std::vector<uint8_t>(); } std::vector<uint8_t> output; output.reserve(input.size()); // Pre-allocate to reduce reallocations uint8_t current_value = input[0]; uint8_t count = 1; for (size_t i = 1; i < input.size(); ++i) { if (input[i] == current_value && count < 255) { // Continue counting if the value is the same and count hasn't reached max ++count; } else { // Write the current run to output (count, value) output.push_back(count); output.push_back(current_value); // Start a new run current_value = input[i]; count = 1; } } // Write the final run output.push_back(count); output.push_back(current_value); return output; }Explanation of the Implementation
-
Input and Output Format:
- The input is a
std::vector<uint8_t>containing the raw data to be encoded. - The output is a
std::vector<uint8_t>where each run is encoded as two bytes: the first byte is the count (number of repetitions, up to 255), and the second byte is the value being repeated.
- The input is a
-
Edge Case Handling:
- If the input vector is empty, an empty vector is returned.
- The implementation ensures that runs longer than 255 are split into multiple runs (since
uint8_tcan only store values up to 255).
-
Efficiency:
output.reserve(input.size())is used to pre-allocate memory for the output vector, reducing the number of reallocations. In the worst case (no compression), the output size could be up to twice the input size, but this is a reasonable starting point.- The algorithm processes the input in a single pass, making it O(n) in time complexity, where
nis the size of the input vector.
-
Run-Length Limit:
- The count is stored as a
uint8_t, so the maximum run length is 255. If a run exceeds this, it is split into multiple runs (handled implicitly by thecount < 255check).
- The count is stored as a
Example Usage
Here's an example of how to use the function:
#include <iostream> #include <vector> #include <cstdint> void print_vector(const std::vector<uint8_t>& vec) { for (const auto& val : vec) { std::cout << static_cast<int>(val) << " "; } std::cout << std::endl; } int main() { // Example input: a vector with repeated values std::vector<uint8_t> input = {1, 1, 1, 2, 2, 3, 3, 3, 3, 4}; // Encode the input std::vector<uint8_t> encoded = rle_encode(input); // Print the original and encoded vectors std::cout << "Original: "; print_vector(input); std::cout << "Encoded: "; print_vector(encoded); return 0; }Example Output
For the input
{1, 1, 1, 2, 2, 3, 3, 3, 3, 4}, the output will be:Original: 1 1 1 2 2 3 3 3 3 4 Encoded: 3 1 2 2 4 3 1 4Decoding the Output
The encoded output can be interpreted as pairs of bytes:
3 1→ Three1s2 2→ Two2s4 3→ Four3s1 4→ One4
Notes on Optimality
-
Compression Efficiency:
- RLE is most effective for data with long runs of repeated values. For data with few repetitions, the encoded output may be larger than the input (due to the overhead of storing counts).
-
Performance:
- This implementation is highly efficient for most use cases, with minimal memory overhead and a single-pass algorithm.
- If you need even better performance for very large inputs, you could consider using SIMD instructions or parallel processing, but that would significantly complicate the code.
-
Limitations:
- The maximum run length is 255 due to the use of
uint8_tfor counts. If you need to support longer runs, you could modify the function to useuint16_tor another type for counts, but this would change the output format.
- The maximum run length is 255 due to the use of
-
Alternative Formats:
- If you need a different encoding format (e.g., variable-length counts or a different way of handling runs), the function can be adapted accordingly.
This implementation strikes a good balance between simplicity, efficiency, and robustness, making it suitable for most practical applications.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.