StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POIs this use of nested vector/multimap/map okay?
text
Body
copied!<p>I am looking for the perfect data structure for the following scenario:</p> <p>I have an index <code>i</code>, and for each one I need to support the following <strong>operation 1</strong>: Quickly look up its <code>Foo</code> objects (see below), each of which is associated with a <code>double</code> value.</p> <p>So I did this:</p> <pre><code>struct Foo { int a, b, c; }; typedef std::map<Foo, double> VecElem; std::vector<VecElem> vec; </code></pre> <p>But it turns out to be inefficient because I also have to provide very fast support for the following <strong>operation 2</strong>: Remove all <code>Foo</code>s that have a certain value for <code>a</code> and <code>b</code> (together with the associated double values).</p> <p>To perform this operation 2, I have to iterate over the maps in the vector, checking the <code>Foo</code>s for their <code>a</code> and <code>b</code> values and erasing them one by one from the map, which seems to be very expensive. </p> <p>So I am now considering this data structure instead:</p> <pre><code>struct Foo0 { int a, b; }; typedef std::multimap<Foo0, std::map<int, double> > VecElem; std::vector<VecElem> vec; </code></pre> <p>This should provide fast support for both operations 1 and 2 above. Is that reasonable? Is there lots of overhead from the nested container structures? </p> <p>Note: Each of the multimaps will usually only have one or two keys (of type <code>Foo0</code>), each of which will have about 5-20 values (of type <code>std::map<int,double></code>).</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload