# Class with a temporary buffer: Tradeoff between memory usage and execution speed [closed]

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
}
};


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?

-

## closed as off-topic by Jamal♦Aug 10 at 0:22

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Questions must involve real code that you own or maintain. Questions seeking an explanation of someone else's code are off-topic. Pseudocode, hypothetical code, or stub code should be replaced by a concrete example." – Jamal
If this question can be reworded to fit the rules in the help center, please edit the question.

I have to drop const in get_foo(int i)

That's why the mutable keyword exists: it enables invisible/just-in-time/lazy initialization from logically-const methods.

-
Cool I totally forgot about mutable –  GradGuy Feb 1 at 2:17

Instead of void get_foo(int i, foo& f) perhaps foo create_foo(int i) const. Otherwise you're returning a reference to f whose value will be overwritten by the next call to get_foo, for example if the user code does

const foo& f1 = bar.get_foo(1);
const foo& f2 = bar.get_foo(2);
// why do f1 and f2 have the same content?


So far as I know, C++ Return value optimization might mean that return-by-value is now as efficient as return-via-non-const-reference.

Furthermore you no longer have a 'mutable' f.

-
Apparently I may be supposed to post this as a multiple answer. –  ChrisW Feb 1 at 2:28
Well but RVO won't kick in if returning from the buffer. –  GradGuy Feb 1 at 2:35
@GradGuy Yes I think you'd need two methods: and the caller would need to know whether it's asking for a one-off value, or a reference to a previously-initialized buffered. –  ChrisW Feb 1 at 2:38
Well the issue I'm having is I like a single API since I'd like to be able to control the behavior from say main and not have to change stuff deep in the code … I thought maybe a separate approach could be deriving 2 separate classes (buffered and non-buffered) from a base class and work with that –  GradGuy Feb 1 at 2:45

If bar holds a vector of pointers to foo (probably std::unique_ptrs) instead of actual foo objects then you can reduce the amount of memory needed for the bar object. You would still be using a ton of memory to store the foos, but passing around bar objects would not be as memory intensive as you currently have it.

-