a basic question about STL

[Robert Rotstein]

o.k., I'm totally new to the Standard Template Library and am having
difficulty figuring it out.

I want to insert a user-defined structure into a STL set, and then do
various compare and delete operations, something like this:

#include <set>

struct FU
{
...
};
set<FU> things;

void main ()
{
struct FU rec;
things.insert(rec);
}

The Microsoft Visual Studio 6.0 C++ compiler flags a bunch of errors, but
not in this code, rather, in
c:\program files\microsoft visual studio\vc98\include\functional. What is
the correct way to do this?

[Pete Becker]

Robert Rotstein wrote:

The Microsoft Visual Studio 6.0 C++ compiler flags a bunch of errors, but
not in this code, rather, in
c:\program files\microsoft visual studio\vc98\include\functional. What is
the correct way to do this?

What are the first few error messages?

--

Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)

[Mike Wahler]

"Robert Rotstein" <rr*******@verizon.net> wrote in message
news:t1Snd.1664$356.1233@trndny04...

o.k., I'm totally new to the Standard Template Library and am having
difficulty figuring it out.

I want to insert a user-defined structure into a STL set, and then do
various compare and delete operations, something like this:

#include <set>

struct FU
{
...
};
set<FU> things;

void main ()
{
struct FU rec;
things.insert(rec);
}

The Microsoft Visual Studio 6.0 C++ compiler flags a bunch of errors, but
not in this code, rather, in
c:\program files\microsoft visual studio\vc98\include\functional. What is
the correct way to do this?

#ifdef _MSC_VER
#pragma warning (disable : 4786)
#endif

#include <iostream>
#include <ostream>
#include <set>

struct FU
{
int i;

public:
FU(int arg = 0) : i(arg)
{
}

bool operator<(const FU& other) const
{
return i < other.i;
}

int value() const
{
return i;
}

};

std::ostream& operator<<(std::ostream& os, const FU& f)
{
return os << f.value();
}
int main ()
{
std::set<FU> things;

things.insert(FU(3));
things.insert(FU(4));
things.insert(FU(1));
things.insert(FU(5));
things.insert(FU(2));

std::set<FU>::const_iterator it(things.begin());
std::set<FU>::const_iterator en(things.end());

while(it != en)
std::cout << *it++ << '\n';

return 0;
}

-Mike

[Peter Koch Larsen]

"Robert Rotstein" <rr*******@verizon.net> skrev i en meddelelse
news:t1Snd.1664$356.1233@trndny04...

o.k., I'm totally new to the Standard Template Library and am having
difficulty figuring it out.

I want to insert a user-defined structure into a STL set, and then do
various compare and delete operations, something like this:

#include <set>

struct FU
{
...
};
set<FU> things;

void main ()
{
struct FU rec;
things.insert(rec);
}

The Microsoft Visual Studio 6.0 C++ compiler flags a bunch of errors, but
not in this code, rather, in
c:\program files\microsoft visual studio\vc98\include\functional. What is
the correct way to do this?

The problem most likely is that you must be able to compare two FUs. It is
this comparison that enables each object to be placed correctly into the
set. Thus you need a

bool operator<(FU const& lhs,FU const& rhs);

Kind regards
Peter

[Matthias Käppler]

Robert Rotstein wrote:

I want to insert a user-defined structure into a STL set, and then do
various compare and delete operations, something like this:
That's the problem. You want to do comparison of FU objects. And how does
such a comparison look like? The compiler doesn't know, so you have to tell
him by overloading operator== for FU objects.
set<FU> things;
Please anyone correct me if I'm wong here, but my impression is that it
could be a bad idea to store actual objects in the container. I'd rather
store pointers or references, for performance reasons.
Again, tell me if I'm wrong here, but I think if you're storing objects,
each time you get() an object from your container, you're in fact getting a
copy of that object (means, the copy contructor is called). Depending on
how complex your FU class is, this can be expensive.

set<FU*> things; // now you're only storing 4-byte objects and copying is
cheap :)
void main ()
{
struct FU rec;
things.insert(rec);
}

Just a note: "void main()" is illegal, this should be "int main()",
conforming to the standard. If your compiler allows this, dump it and get a
better one.

Furthermore "struct FU rec;" to construct a FU object is C syntax. If you're
programming C++, don't do that. "FU rec;" or "FU rec();" is sufficient.
Keep in mind, that in C++ the semantics of a struct is NOT the same as in C.
In C++, a struct is merely a class which is public by default.
Thus:

struct Bar { int x; };

and

class Bar { public: int x; };

are equivalent.

Hope that helps,
Matthias

[Michiel Salters]

Matthias Käppler <no****@digitalraid.com> wrote in message news:<cn*************@news.t-online.com>...

Robert Rotstein wrote:

I want to insert a user-defined structure into a STL set, and then do
various compare and delete operations, something like this:
That's the problem. You want to do comparison of FU objects. And how does
such a comparison look like? The compiler doesn't know, so you have to tell
him by overloading operator== for FU objects.

No.
Technically, you need std::less<FU> although the compiler will happily
use the default std::less<T> if you don't provide one. The default
std::less<T>(T t1, T t2) simply tries return t1<t2, so you should
provide an operator<

The reason is that std::set sorts its elements in increasing order,
and operator== doesn't give you an order.

set<FU> things;

Please anyone correct me if I'm wong here, but my impression is that it
could be a bad idea to store actual objects in the container.

Actually, the STL pretty much assumes you will store values.
I'd rather store pointers or references, for performance reasons.
In fact, you can't even store references, and pointers may cause
memory leaks. You should use a smart pointer, but std::auto_ptr
can't be used either. boost::shared_ptr<FU> does work.
Again, tell me if I'm wrong here, but I think if you're storing objects,
each time you get() an object from your container, you're in fact getting a
copy of that object (means, the copy contructor is called). Depending on
how complex your FU class is, this can be expensive.
There's no get(), but the iterators return references. (24.1.3)
set<FU*> things; // now you're only storing 4-byte objects and copying is
cheap :)

Yes, but who deletes the pointers in things? Do they need to be
deleted? Besides, you now store a FU* and the FU object it points to,
so it may even cause increased memory consumption :|

Regards,
Michiel Salters

[Matthias Käppler]

Michiel Salters wrote:

Technically, you need std::less<FU> although the compiler will happily
use the default std::less<T> if you don't provide one. The default
std::less<T>(T t1, T t2) simply tries return t1<t2, so you should
provide an operator<
Oh okay, but it boils down to a missing comparison operator, which was the
whole point. I'm not an STL expert, I told you I might be wrong :)
Yes, but who deletes the pointers in things? Do they need to be
deleted? Besides, you now store a FU* and the FU object it points to,
so it may even cause increased memory consumption :|

Well, the increase is minimal.

But I have a question to the copying thing:
Suppose I have a class, which objects are say 800 byte each. You're storing
1000 of them in an std::list. You say working with this list is not slower
than working with 1000 4-byte pointers?

Regards,
Matthias

[Richard Herring]

In message <cn*************@news.t-online.com>, Matthias Käppler
<no****@digitalraid.com> writes

Michiel Salters wrote:

Technically, you need std::less<FU> although the compiler will happily
use the default std::less<T> if you don't provide one. The default
std::less<T>(T t1, T t2) simply tries return t1<t2, so you should
provide an operator<

Oh okay, but it boils down to a missing comparison operator, which was the
whole point. I'm not an STL expert, I told you I might be wrong :)

Yes, but who deletes the pointers in things? Do they need to be
deleted? Besides, you now store a FU* and the FU object it points to,
so it may even cause increased memory consumption :|

Well, the increase is minimal.

But I have a question to the copying thing:
Suppose I have a class, which objects are say 800 byte each. You're storing
1000 of them in an std::list. You say working with this list is not slower
than working with 1000 4-byte pointers?

Depends what you do with the list. Constructing the list requires (in
principle - a good compiler may optimize them away) 1000 copy
operations, but thereafter, if you use the STL iterator paradigm
properly, you'll be using references to the objects, and you may not
need to make any further copies. Unless populating the list makes your
program *significantly* slower - and the only way to determine that is
to profile it - the gain in simplicity may well outweigh the slight
increase in time.

If you do find it necessary to use pointers, you need to determine
_before starting to code_ whether pointers represent ownership, and if
so, decide on an ownership model and use smart pointers to enforce it.
--
Richard Herring