Efficient set method in run length encoded C++ map

I have been designing a C++ class that maps an integer to an integer using a vector. Because there is a lot of repetitive data (for example 11115555666222), I am using a compression scheme where I am keeping the struct in a vector that holds the value along with a number indicating where the next value in the sequence starts.

For the example sequence 11115555666222, the vector looks like this:

{{1,4}, {5,8}, {6,11}, {2, 14}}

Below is what the header looks like -

#pragma once
#include <vector>

class myMap
{
public:
myMap(int numValues, int initValues)
{
vecSpans.push_back({ numValues, initValues });
}

int get(int index) const;
{
//can be implemented using binary search over vecSpans
}
void set(int index, int value)
{
//is there any known algorithm to do it elegantly?
}

private:
struct span
{
int next_start;
int value;
};
std::vector<span> vecSpans;
};

// End of file:

I can write get() using a binary search because of the fact that vecSpans stores spans in ascending order. But is there any elegant algorithm to do set()? The brute force approach results in an O(N) algorithm with ugly code. If it makes sense I can provide the implementation for that.

For a vector of this type (std::vector<span>), there can't be a setoperation which is more efficient than O(N).

Inside set, finding the insertion point where some modification(s) have to take place, can be accomplished by the same binary search as the get operation. However, the necessary modification to the vector cannot generally avoid inserting an element near to that place, or a deletion of an element near that place - and that is on O(N) operation.

For example, applying set(0,2) to your example will result in a new vector

{{2,1} {1,3}, {5,8}, {6,11}, {2, 14}}

so the element {2,1} has to be inserted at the beginning, which means all other elements have to be shifted one "slot" to the right.

Picking a different data structure internally could solve this, but that would affect the required space, hence invalidating the compression scheme.

• I think you verified my understanding that one can not do better than O(N) using vector as data structure. I haven't thought of any other data structure yet. Please let me know if you have any suggestions. Currently I have optimized O(N) code that tries to avoid insert/erase whenever possible. So if set() is called in sequence instead of randomly insert happens only at transition points. But that made the code very difficult to read. Mar 27 '21 at 22:17
• @abhijitsawant The O(N) isn't a problem if N is small. The vector solution will be optimal for N ≤ 8 due to cache effects, and still quite efficient until N grows beyond 20 or 100 or so. Beyond that, consider a tree data structure where each node stores the size of the sub-tree. This allows get() and set() in O(log N) time if the tree is balanced. Trees can be encoded into a vector for compact storage, thus avoiding pointers.
– amon
Mar 27 '21 at 22:49

Consider the problem of patching one of your RLE sequences with another. Assume that there was some null value, e.g., ∅, that you can use as the second element of your pairs, that represents "nothing here". So that, for example, the RLE sequence {{25, ∅}, {3, 2}, {5, ∅}, {3, 9}} means a sequence that starts with 25 "nothing here" (or maybe "don't care") followed by 3 '2's, followed by 5 more "don't cares", followed by 3 '9's.

And now, implement lookup on a pair of "patch" with "original" RLE without creating an actual patched version of the original. It's a lookup, except it takes into account the "patch" sequence.

Got that patching going? Now imagine "patching a patched" RLE - that is, you now have two patches rather than one. You can actually run your patch algorithm on those two and get one all-encompassing patch, right?

So now you see how to do it. You have your original sequence which remains unchanged. And you have your patch sequence. Which you accumulate new patches too. And whenever you're doing a lookup in your up-to-date-sequence you're actually doing a lookup in the patch+original. After awhile the patch gets kind of long. Eventually there comes a point when you'd finally like to apply the patch to the original sequence, getting a new sequence that represents the current patched state - and you throw away the original and the patch and start with an empty patch sequence and your new "original" (the current state).

BTW, if you know how to lookup an element in your RLE sequence via binary search - you can do the same in your patch sequence too - so that you still have time complexity for indexing which is O(log n) (just with a higher constant multiplier). And traversal from beginning to end is still linear (i.e., constant time to go from one element to the next). The patch merge itself is obviously linear, and that means that having to actually do the merge from time to time (as the patch gets longer) just adds "amortized" to all these times.

• To be honest I didn't get how patch works. Can you please provide example with regards to how it is initialized, what exactly happens to it when set() is called? Mar 27 '21 at 22:19