Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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?

share|improve this question

3 Answers 3

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.

share|improve this answer
    
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.

share|improve this answer
1  
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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.