Class with a temporary buffer: Tradeoff between memory usage and execution speed

Consider the following two classes

class foo{
 // huge data structure - 400-500 bytes per instance
};

class Bar{
    void get_foo(int  n, foo& f);
}

In my application I need to work with N different instances of foo (with N being on the order of few millions at most). The algorithm to compute foo is implemented by Bar::get_foo() and has a complexity of O(log(N)). Since an instance of foo may be used in several places, I'd like to be able to buffer them and reuse the structure. My first attempt was something very simple:

class Bar{
    std::vector<foo> buffer;
public:
    Bar(int N): buffer(N) {
        for (int i=0; i<N; i++)
            get_foo(i, buffer[i]);
    }

    inline const foo& get_foo(int i) const {return buffer[i];}
    void get_foo(int i, foo& f) {
        // actual implementation
    }
};

Problem with this is that in some parts of my code Bar amounts to a huge amount of memory. Moreover, for several cases, each instance is only used once and then recomputed due to change in the state of other variables. Thus I need a single API to work with both buffered and non-buffered Bar. This was my second implementation

class Bar{
    std::vector<foo> buffer;
    foo f;
    bool is_initialized;
public:
    Bar(int N): buffer(N), is_initialized(false) {}

    void init() {
        for (int i=0; i<N; i++)
            get_foo(i, buffer[i]);
        is_initialized = true;
    }

    void clear() {buffer.clear();}

    inline const foo& get_foo(int i) {
        if (is_initialized)
            return buffer[i];
        else {
            get_foo(i, f);
            return f;
        }
    }
    void get_foo(int i, foo& f) {
        // actual implementation
    }
};

However, there are a couple of things I do not like about this implementation:

1. I have to drop const in get_foo(int i)
2. In case buffer is allocated, I might still pay some penalty due branch mis-prediction.

What is a better way to implement this class and solve these problems?