suggestion for pre-c++11 two item container compatible with vector?

[Shriramana Sharma]

Hello. In my app I am having to return short arrays of doubles frequently from utility functions, the max length being 2. I am concerned whether using vector would involve excessive memory usage and unneeded copying at function return.

It would have to be a container type compatible with vector in the sense of providing [] access and compatible with the algorithms applicable to containers and so std:air is not feasible.

In C++11 I suppose I could use array, but that's not an option for me because I don't want to require C++11 support on my users' compilers. (It's open-source and people with old compilers should be able to compile it.)

Should I just roll my own simple class or can I just re-use vector confident that it won't use too much memory?

Thanks!

 

[Victor Bazarov]

In my app I am having to return short arrays of doubles
frequently from utility functions, the max length being 2. I am
concerned whether using vector would involve excessive memory usage
and unneeded copying at function return.

It would have to be a container type compatible with vector in the
sense of providing [] access and compatible with the algorithms
applicable to containers and so std:air is not feasible.

Algorithms are not applicable to containers. Algorithms expect
iterators. You could provide your own adapter functions to define your
own iterators to the pair's "first" and "second" members. You don't
need to create your own type for the container, though.

In C++11 I suppose I could use array, but that's not an option for me
because I don't want to require C++11 support on my users' compilers.
(It's open-source and people with old compilers should be able to
compile it.)

Should I just roll my own simple class or can I just re-use vector
confident that it won't use too much memory?

Do not use std::vector; it will manage dynamic memory and it's not a
good thing - too slow for such a simple application as you seem to need
this for. It's much better to roll your own and provide whatever traits
you think are needed. Again, think of what exactly your users will need
and see if you can adapt std:air for that. Read up on standard
adapters, std::stack for instance.

V

 

[Nobody]

In C++11 I suppose I could use array, but that's not an option for me
because I don't want to require C++11 support on my users' compilers.
(It's open-source and people with old compilers should be able to compile
it.)

How about std::tr1::array? Or failing that, Boost.Array?

 

[Jorgen Grahn]

Hello. In my app I am having to return short arrays of doubles
frequently from utility functions, the max length being 2. I am
concerned whether using vector would involve excessive memory usage
and unneeded copying at function return.

The thing I think of is not memory usage, but design.
std::vector<double> is a bad fit for "0, 1 or 2 doubles"; that sounds
to me more like a dedicated class.

E.g. does it really make sense to iterate through these? Do you add
to or remove doubles from these objects? Do you want it to be
impossible to end up with three doubles? And so on.

/Jorgen

 

[James Kanze]

Hello. In my app I am having to return short arrays of doubles
frequently from utility functions, the max length being 2. I am
concerned whether using vector would involve excessive memory usage
and unneeded copying at function return.
It would have to be a container type compatible with vector in the
sense of providing [] access and compatible with the algorithms
applicable to containers and so std:air is not feasible.
In C++11 I suppose I could use array, but that's not an option for me
because I don't want to require C++11 support on my users' compilers.
(It's open-source and people with old compilers should be able to
compile it.)
Should I just roll my own simple class or can I just re-use vector
confident that it won't use too much memory?

You can measure sizeof(std::vector<double>) easily yourself. It is
probably much more than 2*sizeof(double) (in my compiler it is 40 bytes,
plus the 2-double array is probably allocated dynamically, probably
meaning another 40 bytes or so) (and the dynamic allocation/deallocation
probably causes the largest performance hit here).

If debugging isn't active, the sizeof a vector will almost
certainly be 3 * sizeof(T*). 12 on a 32 bit implementation, 24
on a 64 bit machine. However...

Does it matter? It depends. How many of those objects you are passing
aroud? Are the copies optimized away by RVO?

If the number of those objects is in tens or hundreds, you shouldn't
worry. If there are millions of those passed around, then yes, I would
feel a quite strong desire to write my own class with minimal needed
interface. But actually one should profile first and see if this is a
bottleneck or not.

That's the only correct answer. If std::vector provides the
desired interface, then the only reason to use something else is
that the profiler says you must.

On the other hand, does it really make sense to provide an
array-like interface when there can be a maximum of two
elements?

 

[James Kanze]

Then why, exactly, are you even considering using std::vector for this?

If std::vector provides the interface and the behavior he wants,
why should he consider anything else?

 

[Jorgen Grahn]

That's the only correct answer. If std::vector provides the
desired interface, then the only reason to use something else is
that the profiler says you must.

On the other hand, does it really make sense to provide an
array-like interface when there can be a maximum of two
elements?

That's more or less what I asked several days ago, and I don't think I
got a reply.

It has never happened to me. I have sometimes needed this though

struct Foo {
optional<double> bar;
optional<double> baz;
}

and I kind of suspect something like that is what he's after. There
are a few cases where (for a newbie) it's not obvious if the best fit
is a struct or a vector, and the "bar might not be present" idea can
easily make you think you need the latter.

/Jorgen

 

[Jeb]

Hello. In my app I am having to return short arrays of doubles
frequently from utility functions, the max length being 2. I am
concerned whether using vector would involve excessive memory usage
and unneeded copying at function return.

It would have to be a container type compatible with vector in the
sense of providing [] access and compatible with the algorithms
applicable to containers and so std:air is not feasible.

In C++11 I suppose I could use array, but that's not an option for me
because I don't want to require C++11 support on my users' compilers.
(It's open-source and people with old compilers should be able to
compile it.)

Should I just roll my own simple class or can I just re-use vector
confident that it won't use too much memory?

Thanks!

Never use "std"-anything if you can "roll your own". Now I say that like I
am being facetious, but I really do know what I am talking about (wow,
that's a lot of "I"s! I realy should learn how to speak your language, or at
least TYPE it!).

Seriously, did you go to "programming school" (for instance, Comp Sci @
USA.college?). Well, you do know how to code at least THAT (?) (!)?

I never did anything (publicly) significant with C++. Though I could have.
As I am not a "quick study", now that "I know" C++, I reevaluate and think
that it's probably not worthwhile to deploy anything (for me).

As much as I try (what is "to try"?) to be able to go out and find people,
in "not having a handle" on that, surely it is "a personal problem". (This
may be a question. Did you recognize that possibility?).

There are a few really good programmers in these groups, i.e., I assume
that. I can make them better and more accomplished. I'm not saying that they
are defficient or need or want to be better or more accomplished, mind you,
I am just saying that I can do that, because it is really simple, not
necessarily easy (for me).

I wonder "if there is anyone out there", maybe with whom I have "conflicted"
or conflicted in the past that actually I could work with to achieve a
synergystic good. What is good? What's good for the goose is good for the
gander?

I think that just maybe, where I would want there to be a question, to a lot
of people, there is no question, no need for a question, never considered
that there may be a question...

OK, "alrighty then", for those who "have heard it all", don't want that,
don't need that, prefer to "get away with it", etc., but what about those
who need help or want help and "can't have it"? And who is MAKING all these
people who need help?

What if a requirement of Comp Sci completion was that you would be equally
adept at humanities (how long can you ponder at an Ed Hopper print? (I know,
that was cliche. The thing is, I don't think it is an either/or thing, but I
am sure that most people pick one or the other (?). How would I know... I've
never even been to Montana.).

 

[Jeb]

In my app I am having to return short arrays of doubles
frequently from utility functions, the max length being 2. I am
concerned whether using vector would involve excessive memory usage
and unneeded copying at function return.

It would have to be a container type compatible with vector in the
sense of providing [] access and compatible with the algorithms
applicable to containers and so std:air is not feasible.

Algorithms are not applicable to containers.

Ha! I like when there are easy things to type back at.

Algorithms expect
iterators.

How would you know? No one has ever studied it. Maybe you should/wanna? I
consider Stepanov and Stroustrup as a starting point: they did a lot of work
to get it (whatever "it" is) to that point, most of y'all are ... something
(incapable, lazy, looking for a job...?).

You could provide your own adapter functions to define
your own iterators to the pair's "first" and "second" members. You
don't need to create your own type for the container, though.

Stepped in what? That said, I want Bjarne Stroustrup to create a clean-slate
replacement for STL. That is, of course, a lie. I don't want him to do that,
because I've been wanting to do that for a long time. So long that I find
C++ as limiting as I think he found C to be.

I don't know how much Bjarne received in compensation for his invention. I
don't know what he sacrificed to create it. Aside, I know there is no
stdcompensation.h, but we are programmers of software that "runs the world"?
Things that make you say 'hmm'.

It's there all the time. You don't know what it is or exactly what it is,
but you FEEL it.

Oh, whoa, is it just me? Maybe Barack Oclinton should chime in and get
$10k/hr to .... umm, : why do people pay to listen to your mouth, and what
is you M.O.? "Put up or shut up bitch" (Bill Obama). You got the PR, but I
have A LOT OF BOOZE. You can't hang, bitch.

 

[Öö Tiib]

I think you forgot to take your medication.

Is there really medication that cures someones urge to discuss
himself?

 

[Melzzzzz]

Is there really medication that cures someones urge to discuss
himself?

There is medication for everything these days

 

[Öö Tiib]

Is this Dihedral ver 2? Associations seem to be fine and content is not
needed anyway nowadays, but the style still seems lacking. Maybe we should
wait for ver 3...

You suspect that it is Turing test instead of trolling? On that case these versions
will fail forever (dead end idea). Constructing sentences is pointless when it don't
care to understand what others said.

 

[James Kanze]

Because it consumes twenty times the memory and is a hundred times slower
for this particular purpose?

If the profiler says that performance is a problem, then of
course, you solve it. Otherwise, why bother? Extra work, and
the results are more difficult to read, since the reader needs
to learn your solution. (Of course, if part of the class
invariant is "coord.size() == 3", you might want to consider a
type where this is guaranteed: std::array if you have C++11, or
even double[3] if you don't.)

 

[James Kanze]

Because if it would become a problem in the future, it's much harder and
more laborious to change after tons of code use that routine, than doing
it right from the start.

Only if you ignore encapsulation, which creates a number of
other problems as well.

 

[Shriramana Sharma]

Hello people and tahnks for hyour replies.

Suggestion to profile: The most pedantically correct answer, but I don't hvae the data to do it yet -- just writing the library right now -- the app producing the data will come later.

Why I can't roll my own class: There are some functions I need to use both with these mini-vectors as well as some full vectors which will also occur in other parts and I don't want to duplicate those functions. Basically that's what I had in mind when asking for a class "compatible with vector", but I now realize that I'll even then have to use template functions which instantiate once for each container/value combination anyway. Just the manualcoding is reduced which should be sufficient, I guess.

So anyway I tried finding out whether a vector would be copied in the kind of situations I encounter, so I produced the following minimal example and the output of the program compiled by either Clang 3.2 or GCC 4.8.1 seems to indicate that the copy-constructor or copy-assignment operator is never called. So I guess in such situations a good compiler would be smart enough to just construct the vector directly at the location it will finally end up in (which seems to indicate that RVO is in effect even without -O options).

# include <iostream>
using std::cout ;
using std::endl ;

# include <vector>
using std::vector ;

struct intVec : public vector<int>
{
intVec()
{
cout << "intVec default constructor" << endl ;
for ( int i = 0 ; i < 10 ; ++i ) this->push_back (i) ; // trying to make the constructor non-trivial
}
intVec ( const intVec & a ) : vector<int>(a) { cout << "intVec copy constructor" << endl ; }
intVec & operator = ( const intVec & a )
{
this->vector<int>:perator=(a) ;
cout << "intVec copy assignment" << endl ;
return *this ;
}
} ;

intVec makeIntVec ()
{
intVec result ;
for ( int j = 10 ; j < 20 ; ++j ) result.push_back(j) ; // trying to make the function non-trivial
return result ;
}

std:stream & operator << ( std:stream & s, const intVec & iv )
{ for ( int i = 0 ; i < iv.size() ; ++i ) s << iv << ' ' ; return s ;}

int main ()
{
intVec a ;
intVec b ( makeIntVec() ) ;
intVec c = makeIntVec() ;
}

Output:

intVec default constructor
intVec default constructor
intVec default constructor

i.e. no mention of copy constructor or assignment at all.

 

[Shriramana Sharma]

People will say something about "premature optimization". This is an
irrelevant objection in this particular case because it requires no
significant additional effort to do it right compared to using std::vector,
while the potential benefits can be significant.

OK thanks for that advice. I'll see about optimizing. I suppose a good lightweight (means other than Boost, which seems to bring in too many #include-s as dependencies) array-type class is http://i42.co.uk/stuff/vecarray.htm.

 

[Jorgen Grahn]

OK thanks for that advice. I'll see about optimizing. I suppose a
good lightweight (means other than Boost, which seems to bring in too
many #include-s as dependencies) array-type class is
http://i42.co.uk/stuff/vecarray.htm.

I asked some time last week but I'll ask again: what operations do you
really need this "0, 1 or 2 doubles" object to support? Does the
simple solution I suggested fit your needs? If not, what more do you
need?

/Jorgen

 

[Shriramana Sharma]

Hello people and thanks very much for all your replies. I read through (andlearnt something from) all of them even though I didn't reply to each.

I asked some time last week but I'll ask again: what operations do you
really need this "0, 1 or 2 doubles" object to support? Does the
simple solution I suggested fit your needs? If not, what more do you
need?

Um -- by "simple" solution are you referring to the one with optional?

Anyhow, my needs are like this: I am writing a set of utility functions forcomputing properties of bezier splines and these (for each curved segment)call delegates which do the same for the component curves i.e. the pieces.For instance, a query is to know the points on a spline where the slope equals a given value, and a cubic bezier has a given slope at most only twiceor at least not at all. This is so since the (real) roots of a quadratic equation (within the range [0,1] )are involved in this and other properties of cubic beziers, and there can be 0, 1 or 2 such roots. So I'll be returning either 0, 1 or 2 t values per curved segment.

Certainly the number of calls to the function is not in the millions, so performance may not be the biggest problem here but I see your point about bad design, vector using dynamic allocation not being appropriate. I could use a simple struct encapsulating a double[2] with a single int8 being there to hold the actual number of values returned. I presume this is what you would suggest I do? The thing is I've used front() and back() a bit to refer to the first and last t values but I guess I can write simple inlines for that.

 

[Jorgen Grahn]

Hello people and thanks very much for all your replies. I read through (and learnt something from) all of them even though I didn't reply to each.



Um -- by "simple" solution are you referring to the one with optional?

The one with the three-element struct, yes. I think it's the only
suggestion I've made in this thread.

Anyhow, my needs are like this: I am writing a set of utility
functions for computing properties of bezier splines and these (for
each curved segment) call delegates which do the same for the
component curves i.e. the pieces. For instance, a query is to know the
points on a spline where the slope equals a given value, and a cubic
bezier has a given slope at most only twice or at least not at all.
This is so since the (real) roots of a quadratic equation (within the
range [0,1] )are involved in this and other properties of cubic
beziers, and there can be 0, 1 or 2 such roots. So I'll be returning
either 0, 1 or 2 t values per curved segment.

Ok. I appreciate the very detailed explanation, but it's a bit /too/
detailed for me -- it's been decades since I last did any algebra :-/

If I understand correctly your objects need to be (apologies if Roots
is the wrong name):

struct Roots {
Roots(); // the one without values
explicit Roots(double x); // one value
Roots(double x, double y); // two values
};

and you never need to change such an object, right? For example, you
don't need a Roots:ush_back(double).

Certainly the number of calls to the function is not in the
millions, so performance may not be the biggest problem here but I see
your point about bad design, vector using dynamic allocation not being
appropriate.

Well, some of the others discussed performance and whether that was
important or not. My own worry was more that std::vector does so much
more than you need.

I like to design my programs by identifying types or classes, and then
map them to C++ constructs. Then I want a C++ construct which
guarantees that my values don't go out of range (invariants, or
whatever they call it). And that's what disturbs me with a raw vector
-- you can do a lot of things to a vector which doesn't make sense for
a Root.

I could use a simple struct encapsulating a double[2]
with a single int8 being there to hold the actual number of values
returned. I presume this is what you would suggest I do?

Yes, something like that. I used optional<double> in my example,
but that would allow { n/a, 3.14159 } as a value and that doesn't
make sense in your design.

The thing is
I've used front() and back() a bit to refer to the first and last t
values but I guess I can write simple inlines for that.

Yes, I do such things all the time -- borrow naming conventions from
the standard library. front() and back() seem like a good fit; the
only thing that's strange is you don't have any way to reach the
elements in the middle, but that's because there /is/ nothing between
front() and back()!

(You could even fake iterators by providing begin() and end(), but you
probably have little use for iterator-based algorithms here.)

I assume this means that today, you process a Roots (a vector<double>)
with a combination of

- empty()
- size()
- front() and back()

You have to make sure not to call the latter two in the empty() case,
and also check size() -- unless you don't care that front() and back()
might give you the same value. Seems like an ok interface to me. The
problem from my point of view was that vector<double> gives you this
interface /plus/ a lot of things which don't make sense.

/Jorgen

 

[Shriramana Sharma]

You have to make sure not to call the latter two in the empty() case,
and also check size() -- unless you don't care that front() and back()
might give you the same value. Seems like an ok interface to me. The
problem from my point of view was that vector<double> gives you this
interface /plus/ a lot of things which don't make sense.

Hello Jorgen -- that is exactly what I ended up implementing -- a "minivec"class having a data member "T data[N]". However apart from size(), front()and back(), I also added operator[], push_back(), operator<< to chain push_back() calls, and pop_back() -- to make it convenient so I can use the class for not-only quadratic roots but also a few more elements. (For the "excessive" detail: another utility function returns a max of four values -- times on a bezier curve corresponding to X-Y-extrema.)

So thank you very much for your suggestion. Now I've implemented the class (and tested it) I can rewrite my utility functions to use it. I suppose I could still use neolib::vecarray (http://i42.co.uk/stuff/vecarray.htm) whichprovides still more functionality (like insert, erase and iterators) but Ijust wanted the exercise for myself!