«

On Nov 15, 9:50*pm, "Peter Liedermann" <peter09...@hispeed.ch> wrote:
> Hi there,
>
> Let "Jumbo" be the name of a class whose instances consume substantial
> storage.
>
> A vector of typically 1000 such Jumbo-instances is needed. It must be
> sorted by a simple int criterium, but not often.
>
> Is there a substantial performance difference between vector <Jumbo> and
> vector <Jumbo *>, provided that everything else is adapted accordingly? Is
> there a difference at all?

If, once the vector is populated, it does not change much,
one option may be to use an additional vector containing
iterators to the first. The vector containing the iterators
remain sorted (the other one not). It needs to be repopulated
under certain circumstances if items are inserted into the
first or re-allocation happens due to lack of capacity.

Another option is to look at boost:tr_vector.
- It automatically manages memory.
- It uses a indirect interface that could simplify sorting.

Kind regards,

Werner

In article <>,
Peter Liedermann <> wrote:
>On Tue, 15 Nov 2011 21:30:14 +0100, Marcel Müller
><> wrote:
>
>> On 15.11.2011 20:50, Peter Liedermann wrote:
>>> Let "Jumbo" be the name of a class whose instances consume substantial
>>> storage.
>>>
>>> A vector of typically 1000 such Jumbo-instances is needed. It must be
>>> sorted by a simple int criterium, but not often.
>>>
>>> Is there a substantial performance difference between vector <Jumbo> and
>>> vector <Jumbo *>, provided that everything else is adapted accordingly?
>>> Is there a difference at all?
>>
>> In general you need to copy the Jumbo objects to put them into the
>> vector. The copy constructor of Jumbo might be quite expensive if it is
>> not a POD like type. Is that what you want?
>
>I think this is the key to my question: Jumbo * is a POD type and Jumbo
>itself is clearly not. For illustration of the term POD, I found
>http://www.fnal.gov/docs/working-gro...x/doc/POD.html
>useful.
>
>
>> You should also think about the (re)allocations of vector<Jumbo>. A
>> vector will in general allocate more slots than needed. If Jumbo is
>> large, then this might be a reasonable amount of memory. Furthermore, a
>> vector might not start with it's final size. So there are some
>> reallocations necessary before the vector has it's final size. These
>> reallocations copy the entire content.
>
>Since I am now determined to use Jumbo * and can exactly predict the
>number of slots, this is not relevant to my situation although generally
>good to know. Question: If I would use vector <Jumbo> instead and the
>Jumbo objects were of varying length and I would start the vector with all
>NUL entries, could I then get the reallocation/copy problem mentioned?

Typically Jumbo should be more like:

class Jumbo
{
public:
Jumbo();
// etc
private:
data * m_data;
}

So the "size" of Jumbo would not be sizeof(Jumbo) and Jumbo objects
containing containing varying amount of data would all present the
same sizeof(aJumboOject).

for such a class, as mentionned elsewhere, a very efficient swap()
function could be implemented by simply swapping the internal
pointers.

On 11/16/2011 2:55 AM, Peter Liedermann wrote:
> On Tue, 15 Nov 2011 21:30:14 +0100, Marcel Müller
> <> wrote:
>
>> On 15.11.2011 20:50, Peter Liedermann wrote:
>>> Let "Jumbo" be the name of a class whose instances consume substantial
>>> storage.
>>>
>>> A vector of typically 1000 such Jumbo-instances is needed. It must be
>>> sorted by a simple int criterium, but not often.
>>>
>>> Is there a substantial performance difference between vector <Jumbo> and
>>> vector <Jumbo *>, provided that everything else is adapted accordingly?
>>> Is there a difference at all?
>>
>> In general you need to copy the Jumbo objects to put them into the
>> vector. The copy constructor of Jumbo might be quite expensive if it
>> is not a POD like type. Is that what you want?
>
> I think this is the key to my question: Jumbo * is a POD type and Jumbo
> itself is clearly not. For illustration of the term POD, I found
> http://www.fnal.gov/docs/working-gro...x/doc/POD.html
> useful.

Depending on what Jumbo looks like, you could still sort a
vector<Jumbo> efficiently if you can define an efficient swap()
overload. For instance, suppose Jumbo is implemented as follows:

struct Jumbo
{
std::string foo;
std::vector<double> bar;
} ;


Then you can define swap() by first defining a public swap() member
function:

void swap(Jumbo &rhs)
{
//Almost all the types in the standard library have efficient
swap() overloads
swap(foo, rhs.foo);
swap(bar, rhs.bar);
}


Then, define a global swap function in the same namespace as Jumbo (this
is important!)

inline void swap(Jumbo &lhs, Jumbo &rhs)
{
lhs.swap(rhs);
}


If you follow these two steps, and Jumbo consists solely of built-in
types and standard library types, then sorting a vector of Jumbo becomes
extremely efficient, with no need to ever allocate or deallocate memory
for a temporary object.

Joe Gottman

On Wed, 16 Nov 2011 15:02:44 +0100, Leigh Johnston <> wrote:

> On 15/11/2011 19:50, Peter Liedermann wrote:

> If you are going to allocate the Jumbo objects separately for use in
> vector<Jumbo*> then you might as well just use std::set<Jumbo>; std::set
> will keep the items sorted.
>

Thank you for the suggestion. However, I am not going to use set because
I occasionally have to re-sort. In my case, this resort would be quite
intense, that is, almost everything is repositioned each time. This is
definitely not a hot spot in the algorithm, but I do not want to swear
that it occurs at most so and so often. For this reason, I want to avoid
tree-like structures, which an STL set essentially is.

But BTW, this takes us back to a variation the original question: Would
you, given the use of a set, really use std::set<Jumbo> or std::set<Jumbo
*> instead and does it make a difference
(that is, does replacing "vector" by "set" in the original question make a
difference)

Regards.
Peter

On Nov 17, 7:45*am, "Peter Liedermann" <peter09...@hispeed.ch> wrote:
> On Wed, 16 Nov 2011 15:02:44 +0100, Leigh Johnston <le...@i42.co.uk> wrote:
> > On 15/11/2011 19:50, Peter Liedermann wrote:
> > If you are going to allocate the Jumbo objects separately for use in
> > vector<Jumbo*> then you might as well just use std::set<Jumbo>; std::set
> > will keep the items sorted.
>
> Thank you for the suggestion. *However, I am not going to use set because
> I occasionally have to re-sort.
>
> In my case, this resort would be quite
> intense, that is, almost everything is repositioned each time. *This is
> definitely not a hot spot in the algorithm, but I do not want to swear
> that it occurs at most so and so often. *For this reason, I want to avoid
> tree-like structures, which an STL set essentially is.
>
> But BTW, this takes us back to a variation the original question: Would
> you, given the use of a set, really use std::set<Jumbo> or std::set<Jumbo
> *> instead and does it make a difference
> (that is, does replacing "vector" by "set" in the original question make a
> difference)

It depends on a lot of things. You really haven't given me enough
information to determine the answer.

If you question is "Given a pre-existing list of stuff that's
expensive to copy, how do I figure out what is the sorted sequence of
those objects?", then the answer is pretty straightforward. Define the
following class:
struct JumboPointerSortRule
{
bool operator() (Jumbo* x, Jumbo* y) const { return *x < *y; }
};
Then create a std::set<Jumbo*, JumboPointerSortRule>, and insert a
pointer of each element in the unsorted sequence to this set. Voila,
you now have a view on your original objects, where the view is in
sorted order, all with a minimum of fuss and CPU/memory usage. Unless
a profiler tells you differently, or you know up front some very
specific facts (you would know what those facts are if you knew them),
then don't worry about it and do it this way.

The answer may change if you have C++11. I'm currently too ignorant of
such things to comment.

If your question is more of a architecture question, then you haven't
given me enough information to work through how I'd do it.