![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Orchid XP v8 wrote:
> I was thinking maybe I'd try implementing a Huffman coder. I need a
> binary tree for that. Does STL happen to have one already? (That would
> obviously be the simplest thing...)
Oooh, one of my first toy projects :) IIRC once I learned the concept,
it was deceptively simple to write.
--
~Mike
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On Mon, 29 Sep 2008 07:53:51 -0500, Mike Raiford <"m[raiford]!at"@gmail.com> wrote:
>Ummm... They do teach basic fractions to first graders nowadays.
... and now algebra in sixth grade.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> What I was really interested to know is whether trying to construct a
>> set without a comparison operator yields a compile-time error, a runtime
>> error, or simply undefined behaviour.
>
> We are talking about templates here. Everything happens at compile
> time. :)
In my book, finding out at compile time that you did something wrong
beats the **** out of finding that out at runtime. ;-)
Unfortunately, C tends to be a language that says "hey, you wanna do
something crazy? Who am I to stop you? You know what you're doing, right?"
It's nice to see that C++ moves away from that a little.
> (Although the error message will probably be quite obfuscated. With
> the next C++ standard compilers will have means to directly say "your
> type has no operator< but one is required".)
That's nice to have too...
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible wrote:
> It's nice to see that C++ moves away from that a little.
C++ is still a wonderful tool to shoot yourself in the foot.
I forget who said it, but I remember a quote:
"C allows you to shoot yourself in the foot. C++ allows you to shoot
yourself in the foot and reuse the bullet"
--
~Mike
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Mike Raiford wrote:
> I forget who said it, but I remember a quote:
>
> "C allows you to shoot yourself in the foot. C++ allows you to shoot
> yourself in the foot and reuse the bullet"
...and Haskell allows you to pretend to shoot yourself in the foot but
actually remain unharmed although nobody else really understands why? ;-)
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Mike Raiford <"m[raiford]!at"@gmail.com> wrote:
> "C allows you to shoot yourself in the foot. C++ allows you to shoot
> yourself in the foot and reuse the bullet"
OTOH C++ allows much better than C to build automatic or semi-automatic
safeguards which will prevent or at least diminish the danger of shooting
yourself in the foot (at least as long as you use those safeguards properly).
Of course one limiting factor in making C++ more secure is its policy
that you don't have to pay for what you don't use, and that there should
be as little hidden overhead in correct code as possible (in other words,
adding automatic checks to *correct* code is basically a waste).
On the other hand, the C++ standard doesn't forbid compilers from adding
additional checks (eg. in debug mode) if they want. In fact, most of the
better compilers *do* add additional checks to things when they compile
in debug mode.
Very unfortunately gcc is *not* one of those compilers... :(
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Mike Raiford wrote:
> Orchid XP v8 wrote:
>
>> I was thinking maybe I'd try implementing a Huffman coder. I need a
>> binary tree for that. Does STL happen to have one already? (That would
>> obviously be the simplest thing...)
>
> Oooh, one of my first toy projects :) IIRC once I learned the concept,
> it was deceptively simple to write.
I usually do Jotto first. It's got more twisty ways you can take it.
http://darren.s3.amazonaws.com/functional.txt
--
Darren New / San Diego, CA, USA (PST)
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Hmm, so vectors seem to be able to do some pretty death-defying stuff!
They're variable size, but they manage their memory automatically.
Now in a GC language, you can just pass anything anywhere. Usually in a
language with manual memory management you have to be extremely careful
about doing that.
However, vectors seem to make this surprisingly safe. Indeed, it appears
that you can pass a vector in any way that you could pass something like
an integer, and it will just do The Right Thing(tm). The only difference
is that throwing a large vector around by value probably isn't a good idea.
Is that about right?
Here's another question: Suppose you have a function that's supposed to
create a new vector and return it to the caller. What's the best way to
do that?
Obviously the ideal thing to do would be to return a reference. However,
if I create a vector in an auto variable, presumably when the function
returns that variable will vanish, making the reference to it unusable.
(If I'm understanding how this works.)
I guess if I return it by value the problem goes away. But that doesn't
seem terribly efficient.
Maybe the thing to do would be to have the caller pass in a reference to
an empty vector created outside?
Just trying to get my head round this stuff so I don't do anything dumb...
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible <voi### [at] dev null> wrote:
> Hmm, so vectors seem to be able to do some pretty death-defying stuff!
> They're variable size, but they manage their memory automatically.
> Now in a GC language, you can just pass anything anywhere. Usually in a
> language with manual memory management you have to be extremely careful
> about doing that.
> However, vectors seem to make this surprisingly safe. Indeed, it appears
> that you can pass a vector in any way that you could pass something like
> an integer, and it will just do The Right Thing(tm). The only difference
> is that throwing a large vector around by value probably isn't a good idea.
> Is that about right?
That's the whole idea in C++ class design. If you write a class which is
not safe to use like that, then your design is bad.
C++ classes have been designed to allow you to do that. As long as
you just create local instances of them and pass them by value (in other
words, as long as you don't use the keyword 'new' nor store pointers which
last longer than the object), if the class has been implemented properly
it's completely safe. (Ok, there are some exceptions, but basically.)
It would be perfectly possible to implement a dynamic vector class which
has all the properties as std::vector, and which is efficient to pass by
value. The vector class could basically work like a reference-counted
handle to the array (in which case all the copies share the same array).
Or it could use the copy-on-write mechanism (in which case each copy has
its own array, but it's still very efficient to pass copies around).
The reason why std::vector doesn't implement copy-on-write is that it
would add overhead to the []-indexing, which is usually something people
don't want. However, if you don't mind that overhead, or it's enough for
all the copies to share the same array, then you can implement your own
dynamic vector which uses reference counting and thus becomes much more
efficient to pass around by value.
The nice thing about this is that whether copying the vector object
causes a deep-copy of the array, whether it's reference-counted, or
whether it uses copy-on-write, the interface doesn't change in any way.
In other words, the internal implementation is completely transparent and
its usage is exactly the same regardless.
> Here's another question: Suppose you have a function that's supposed to
> create a new vector and return it to the caller. What's the best way to
> do that?
> Obviously the ideal thing to do would be to return a reference. However,
> if I create a vector in an auto variable, presumably when the function
> returns that variable will vanish, making the reference to it unusable.
> (If I'm understanding how this works.)
> I guess if I return it by value the problem goes away. But that doesn't
> seem terribly efficient.
Actually if you have a function like:
std::vector<int> createVector(whatever) { ... }
and then call it like:
std::vector<int> myVector = createVector(whatever);
the compiler will most probably be able to optimize the copying away.
Basically the 'createVector()' function will build its return value right
onto that 'myVector' variable (rather than building a local copy which it
then returns by value).
Of course there are limits to this. For example, if you have something
like this:
std::vector<int> myVector;
// ...some code using myVector here...
myVector = createVector(whatever);
then the compiler has no choice: It must build the return value of
'createVector()' into a temporary and then copy it to 'myVector'.
One common idiom is for the function to take the vector as reference:
void createVector(whatever, std::vector<int>& result) { ... }
and then you give your vector as parameter, and the function will then
add the data to it.
Btw, there's a trick to avoid the copying of that temporary in the first
case:
std::vector<int> myVector;
// ...some code using myVector here...
std::vector<int> tempVector = createVector(whatever);
myVector.swap(tempVector);
What this does is that the result of 'createVector' is built onto
'tempVector', and then its contents swapped with 'myVector'. Swapping of
vectors is an O(1) operation and avoids the needless copying.)
--
- Warp
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
>> Is that about right?
>
> That's the whole idea in C++ class design. If you write a class which is
> not safe to use like that, then your design is bad.
>
> C++ classes have been designed to allow you to do that. As long as
> you just create local instances of them and pass them by value (in other
> words, as long as you don't use the keyword 'new' nor store pointers which
> last longer than the object), if the class has been implemented properly
> it's completely safe. (Ok, there are some exceptions, but basically.)
That's certainly a big step up from C, where as soon as you touch
something that's dynamically allocated, basically your program is almost
guaranteed to segfault. But then, C doesn't provide any way for a
library designer to control what happens with their stuff at the
caller's end. That's very machine efficient, but not terribly safe...
> The nice thing about this is that whether copying the vector object
> causes a deep-copy of the array, whether it's reference-counted, or
> whether it uses copy-on-write, the interface doesn't change in any way.
> In other words, the internal implementation is completely transparent and
> its usage is exactly the same regardless.
That's a good property.
>> Here's another question: Suppose you have a function that's supposed to
>> create a new vector and return it to the caller. What's the best way to
>> do that?
>
> One common idiom is for the function to take the vector as reference:
>
> void createVector(whatever, std::vector<int>& result) { ... }
>
> and then you give your vector as parameter, and the function will then
> add the data to it.
That seems like the simplest thing to do then. The allocation and
lifetime of the object is quite obvious by looking at the caller, and
it's simple to implement at the called end.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |