Get unique random number within range on each call

I came across this question where the goal is to design a class with two methods - get() and set_range(x, y).

The behavior of both the methods is explained in the comments below & there are examples too.

class UniqueRandomGenerator {
  int start, end;

  public:
    int get() {
      // Returns a unique random number in the range [start, end].

      // Every call should return a different random number unless there 
      // is no number left to be returned within the range [start, end].

      // When all numbers within [start, end] are already returned at least once,
      // the range is reset and then it is ok to return the previously returned 
      // number.
    }

    void set_range(int s, int e) {
      // Update the range [start, end] to be [s, e].

      // However, the random numbers returned by get() should still be unique. 
      // Only when there is no number left in [s, e], we can repeat the numbers.
    }

};

For example:

set_range(5, 8);
get(); // returns one of {5, 6, 7, 8}. Say it returns 6
set_range(3, 6);
get(); // must return one of {3, 4, 5}. Note that 6 is not there because it 
       // returned previously. Say it returns 3.
get(); // One of {4, 5}. Say 4.
get(); // One of {5}. Must be 5.
get(); // Because there is no number left, range gets reset. Now one of {3, 4, 5, 6}
       // should be returned.

• If there is only a get() operation to support & the range is constant

Approach 1 - I can shuffle the array once and keep returning the next number from the array. When I reach the end, I would shuffle the array again and start returning the number from the beginning.

Approach 2 - I can add numbers from [start, end] into the array and randomly generate an index between 0 to array.size()-1. Return the number at that index. Swap that index with the last index and then decrement the size of the array.

In both of the above approaches, there is a O(n) cost upfront even if the amortized time complexity is O(1) for each get(). If there are very few get() calls, then upfront O(n) is not desirable.

Is there a way to divide that upfront cost over multiple get() calls?

Approach 3 - I can have a set where I can track all the returned numbers. Initially, it will be empty. I can generate a random number and see if it is present in the set. If it is not present, I will add it to set and return it. Otherwise, I will generate another number.

The problem with this approach is that there is no upper bound to how many times will I have to generate random numbers until I find a unique one.

---

All the above approaches only work, if at all, when the range is constant. The addition of set_range() makes it a lot more complex according to me.

What are the efficient ways of handling both get() and set_range() calls?