Orchid XP v8 wrote:
> OOC, what the hell is this "boost" I keep hearing about?
> 

A set of advanced C++ libraries with varying levels of sanity.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> > Darren New <dne### [at] sanrrcom> wrote:
> >> Warp wrote:
> >>>   Isn't this usually handled with callback interfaces (in OO languages)
> >>> rather than function pointers?
> > 
> >> Only in languages that don't support pointers to member functions.
> > 
> >   C++ supports pointers to member functions, yet using callback interfaces
> > is a rather common idiom.

> How do you declare a pointer to a member function, then?  I thought you 
> had to keep a pointer to the object and then somehow invoke the proper 
> member function, but I don't know the syntax for that latter part?

  Obviously you need an object if you want to call a member function,
be it directly or through a member function pointer. (Member functions
always require an object, as they take one as "hidden" parameter. You
can't call a member function without an object.)

  Member function pointer syntax is rather complicated. If you have,
for example:

class A
{
 public:
    void foo(int i) { std::cout << "foo: " << i << std::endl; }
    void bar(int i) { std::cout << "bar: " << i << std::endl; }
};

then you can create a member pointer named functionPointer, and make it
point to 'foo' like this:

    void (A::*functionPointer)(int) = &A::foo;

  (With the next C++ standard things will get easier, as you will be able
to write simply: "auto functionPointer = &A::foo;")

  You can call it like this:

    A a;
    (a.*functionPointer)(5);

    A* aPtr = &a;
    (aPtr->*functionPointer)(10);

  Note that this will work even if foo() is a virtual function overridden
in a class derived from A, and 'aPtr' (while still being of type A*) was
actually pointing to an object of this derived class.

  Also note that 'functionPointer' is in no way tied precisely to the
foo() function. You can make it point to another member function with
the same signature:

    functionPointer = &A::bar;
    (a.*functionPointer)(5); // Now A::bar() is called

  Curiously, you can even make pointers to member variables. That's
obscure if anything.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   (With the next C++ standard things will get easier, as you will be able
> to write simply: "auto functionPointer = &A::foo;")
> 
>   You can call it like this:
> 
>     A a;
>     (a.*functionPointer)(5);

Oh, I see. No, I was talking about one object/pointer/variable etc that 
pointed to one instance's member function.

For example, in C#, if you have
   class A {
     public float abc;
     public int xyz(int pdq) { return (int) abc; }
     public static mno(int pdq) { return pdq*pdq; }
   }
   int (*point)(int);
   A alpha = new A();
   alpha.abc = 23.75;

then you can do
   point = &(alpha.xyz);
   int x = (*point)(23);
   point = &(A.mno);
   int y = (*point)(75);

/* I might have the syntax mildly wrong, and I'm probably using
    too many parens, but ... */

So the member pointer actually carries around the reference to the 
object, if it needs to. Or it can point to a static (non-member) 
function. I think Python does the same thing.

>   Also note that 'functionPointer' is in no way tied precisely to the
> foo() function. You can make it point to another member function with
> the same signature:
> 
>     functionPointer = &A::bar;
>     (a.*functionPointer)(5); // Now A::bar() is called

Yeah, but invoking it requires both the object and the pointer. *Now* I 
remember what is going on there. It definitely makes it easier to make 
data structures that deal with function pointers if you only care about 
the types of arguments and results, and not which class of object is 
implementing it. It does, obviously, add some overhead, of course. This 
way, you can have (say) an array of pointers to member functions, all of 
which are implemented by unrelated classes. I guess in C++ you could use 
MI to deal with something like that, while C# wouldn't support it the 
same way.

-- 
Darren New / San Diego, CA, USA (PST)

Post a reply to this message

> You're Californian?
>
> Wow... suddenly a whole lot of POV-Ray stuff makes way more sense... ;-)

Huh? I'm not sure I get it. =) I am not on the POV-Ray development team.

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

> Copy...constructor...? x_x
>
> Heh. And I thought figurating out the difference between a const pointer 
> and a pointer to a const was hard!

It seems like you're learning a lot of language features, one after another. 
If I were you I'd slow down a bit, take what you know already, and find 
something fun to do with it. Make a text based adventure game or something. 
The key is to find a hook that keeps you interested, so you start to use the 
language in a more real manner, and then you learn features as you find you 
need (or want) them.

On the other hand, if your motivation is to master the intricacies of the 
language, then do that. Just don't burn yourself out trying to learn one 
thing after another. It's a lot like math - they don't teach fractions to 
first graders because they need to spend time learning addition and 
subtraction to fully master the concepts.

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

Slime wrote:

> It seems like you're learning a lot of language features, one after another. 
> If I were you I'd slow down a bit, take what you know already, and find 
> something fun to do with it. Make a text based adventure game or something. 
> The key is to find a hook that keeps you interested, so you start to use the 
> language in a more real manner, and then you learn features as you find you 
> need (or want) them.

That was kind of my plan. And it went as far as me writing two simple 
C++ programs that actually work.

Now, however, all the programs I can think of that I'd like to write all 
involve constructing dynamic data structures - and the tutorial I'm 
following doesn't seem to cover that in much detail yet. In fact, it now 
seems to have degenerated into more of a categorical reference manual 
than a "tutorial"...

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Slime wrote:
>> You're Californian?
>>
>> Wow... suddenly a whole lot of POV-Ray stuff makes way more sense... ;-)
> 
> Huh? I'm not sure I get it. =) I am not on the POV-Ray development team.

Californians have a reputation for being... uh... "unusual". Which would 
certainly explain... for example... your nick is "slime"? o_O And also 
some of the wacky things you've rendered over the years.

I'm jesting of course... just because the most interesting thing *I* 
ever rendered was a 3D section of the cubic Mandelbrot set... :-(

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> Now, however, all the programs I can think of that I'd like to write all 
> involve constructing dynamic data structures

  What kind of data structures? Are they something which you can't do with
the STL data containers? If you have any questions about using those
containers, just ask.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Orchid XP v8 <voi### [at] devnull> wrote:
>> Now, however, all the programs I can think of that I'd like to write all 
>> involve constructing dynamic data structures
> 
>   What kind of data structures? Are they something which you can't do with
> the STL data containers? If you have any questions about using those
> containers, just ask.

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...)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> I was thinking maybe I'd try implementing a Huffman coder.

  That sounds like a bit advanced... :)

> I need a 
> binary tree for that. Does STL happen to have one already? (That would 
> obviously be the simplest thing...)

  std::set (as well as std::map) is internally implemented as a balanced
binary tree, but if I'm not mistaken, a Huffman coder requires an
unbalanced one, so it may be unusable for that purpose.

  But yeah, if you need to create your own dynamic data containers, it
inevitably means you will have to deal with pointers, 'new' and explicit
memory management. (Although using smart pointers may by possible in
this situation.)

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Orchid XP v8 <voi### [at] devnull> wrote:
>> I was thinking maybe I'd try implementing a Huffman coder.
> 
>   That sounds like a bit advanced... :)

All my programs are! ;-)

>> I need a 
>> binary tree for that. Does STL happen to have one already? (That would 
>> obviously be the simplest thing...)
> 
>   std::set (as well as std::map) is internally implemented as a balanced
> binary tree, but if I'm not mistaken, a Huffman coder requires an
> unbalanced one, so it may be unusable for that purpose.
> 
>   But yeah, if you need to create your own dynamic data containers, it
> inevitably means you will have to deal with pointers, 'new' and explicit
> memory management. (Although using smart pointers may by possible in
> this situation.)

Actually, thinking about it... I don't "really" need the tree, all I 
need is the tree addresses. I could represent each "tree" as just a 
vector of symbol/codeword pairs, and "join trees" by frobbing the 
codewords and joining the vectors.

Oh, er... can you have a vector of vectors? Or would it have to be a 
vector of vector pointers?

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> Oh, er... can you have a vector of vectors? Or would it have to be a 
> vector of vector pointers?

  It's perfectly possible.

std::vector< std::vector<int> > vecvec;
vecvec.resize(10);
vecvec.at(5).push_back(42);

  When you start having nested data containers, it may be useful to abstract
a bit, so that the syntax becomes easier, like this:

typedef std::vector<int> IntCont;
// Now 'IntCont' is a vector of ints

std::vector<IntCont> vecvec;
// 'vecvec' is a vector of vectors of ints

vecvec.push_back(IntCont()); // Put a new IntCont into the vector
vecvec.back().push_back(42);

  Of course there's no limit on how many containers you can nest. You
could just go on:

typedef std::vector<IntCont> IntVecCont;

std::vector<IntVecCont> vecvecvec;
// Now 'vecvecvec' is a vector of vectors of vectors of ints.

  Managing all this in your head might become a bit complicated, though. :)

  In practice when you start needing such deeply nested containers, a good
idea is to start abstracting even more. The inner containers will usually
have a specific role, so you should make a class out of them, rather than
using the directly, and use some simple public interface with that class.

  For example, if you want a vector of huffman trees, it would be a bad
idea to try to manage them directly. Instead, it's a much better idea to
abstract the whole huffman tree concept, and then use that as the element
of the outermost vector. In other words, something like:

class HuffmanTree
{
 public:
    // A nice and easy-to-use interface here

 private:
    typedef std::vector<int> IntCont;
    std::vector<IntCont> theTree; // Or whatever

    // Other possible private members
};

  Now you can do this:

std::vector<HuffmanTree> trees; // A vector of huffman trees

  So here you have three levels of nesting of vectors, but they are so
well abstracted that it's easily manageable. In the outermost layer you
only see the HuffmanTree class and its simple public interface.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Orchid XP v8 <voi### [at] devnull> wrote:
>> Oh, er... can you have a vector of vectors? Or would it have to be a 
>> vector of vector pointers?
> 
>   It's perfectly possible.

OK. I just wasn't sure if it's permissible for the element type to be of 
variable size, that's all.

>   When you start having nested data containers, it may be useful to abstract
> a bit.

Agreed.

>   Of course there's no limit on how many containers you can nest.
>   Managing all this in your head might become a bit complicated, though. :)

Hence the abstraction. ;-)

Presumably I'm going to do something like define a struct that holds all 
the data I need about each symbol (what the symbol is, its probability, 
its current codeword, etc), and then define a typedef for a vector of 
symbol info structs. Then it'll be quite clear that vector<tree> is a 
vector of Huffman trees.

>   For example, if you want a vector of huffman trees, it would be a bad
> idea to try to manage them directly. Instead, it's a much better idea to
> abstract the whole huffman tree concept, and then use that as the element
> of the outermost vector. In other words, something like:
> 
> class HuffmanTree
> {
>  public:
>     // A nice and easy-to-use interface here
> 
>  private:
>     typedef std::vector<int> IntCont;
>     std::vector<IntCont> theTree; // Or whatever
> 
>     // Other possible private members
> };
> 
>   Now you can do this:
> 
> std::vector<HuffmanTree> trees; // A vector of huffman trees
> 
>   So here you have three levels of nesting of vectors, but they are so
> well abstracted that it's easily manageable. In the outermost layer you
> only see the HuffmanTree class and its simple public interface.

...or I could do that, yes. That would provide an obvious place to put 
the "tree merge" functionallity, as well as symbol lookup, etc.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

On Sat, 27 Sep 2008 12:37:13 +0200, Orchid XP v8 <voi### [at] devnull> wrote:
> Warp wrote:
>> Orchid XP v8 <voi### [at] devnull> wrote:
>>> Oh, er... can you have a vector of vectors? Or would it have to be a  
>>> vector of vector pointers?
>>    It's perfectly possible.
>
> OK. I just wasn't sure if it's permissible for the element type to be of  
> variable size, that's all.

It is not. In fact, there is no such thing as a variably sized type in C++.



-- 
FE

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> Warp wrote:
> > Orchid XP v8 <voi### [at] devnull> wrote:
> >> Oh, er... can you have a vector of vectors? Or would it have to be a 
> >> vector of vector pointers?
> > 
> >   It's perfectly possible.

> OK. I just wasn't sure if it's permissible for the element type to be of 
> variable size, that's all.

  As Fredrik pointed out, a type in C++ always has the same size.
"std::vector<int>" is an example of a type, and each instance of it
will have the same size.

  In fact, there's a keyword in C++ (and C) which can be used to get
the size (in bytes) of a type, at compile time: sizeof(YourType)

  The std::vector class itself consists of a pointer and maybe a few
data members. Its contents do not change. What the vector does is that
it allocates memory dynamically. That allocated memory does not affect
the size of the std::vector object.

  Anyways, these are technical details you don't have to worry about.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

>   The std::vector class itself consists of a pointer and maybe a few
> data members. Its contents do not change. What the vector does is that
> it allocates memory dynamically. That allocated memory does not affect
> the size of the std::vector object.

OK, that's pretty neat.

>   Anyways, these are technical details you don't have to worry about.

That's what's so neat about it. ;-)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

What would be the correct way to iterate over a vector of integers and 
find + remove the lowest element?

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> What would be the correct way to iterate over a vector of integers and 
> find + remove the lowest element?

  Do you want the imperative solution, or the template metaprogramming
solution? ;)

  There are two ways of iterating a vector: By indexing it and by using
iterators. The latter method can also be used for any other STL container
as well. The indexing method might be a bit clearer:

size_t smallestIndex = 0;
for(size_t ind = 1; ind < theVector.size(); ++ind)
    if(theVector[ind] < theVector[smallestInd])
        smallestIndex = ind;

  When the loop ends, smallestIndex will be an index to the (first)
smallest value inside the vector. Now the only trick is how to remove it:

theVector.erase(theVector.begin() + smallestIndex);

  (The erase() function requires an iterator. It doesn't work directly with
index values. The begin() function returns an iterator to the first element
in the vector. The reason why you can get an iterator to the nth element
with an addition like that is that std::vector iterators are random access
iterators and they support jumping to any location in the vector by adding
an index value to them.)

  Note that erase() is an O(n) operation.

  You can also implement the same thing using iterators. The advantage is
that the exact same code will work with any STL data container, not just
vectors. For example, if you wanted to use an std::list instead, the
iterator solution would work with that too.

  To simplify the syntax it's usually a good idea to typedef the data
container type:

typedef std::vector<int> Cont; // Could also be eg. an std::list<int> etc.

  Then you can perform the operation like this:

Cont::iterator smallestIter = theVector.begin();
for(Cont::iterator iter = theVector.begin(); iter != theVector.end(); ++iter)
    if(*iter < *smallestIter)
        smallestIter = iter;

theVector.erase(smallestIter);

  Iterators work a bit like pointers. The prefix-* operator dereferences
the iterator, ie. returns the value it's pointing to. The ++ operator
changes the iterator to point to the next element in the container.
The iterator returned by the end() function is a special iterator which
points "past the end" (ie. to an imaginary element which is after the
last element in the data container). When the iterator gets to the end()
iterator, it means that the data container has no more values.

  If the type stored in the data container was a class with member
functions, you could call such a member function with iter->function();
(in the same way as with pointers).

  Iterators are used a lot in STL containers and algorithms because they
are a good way of abstracting away the actual container: An algorithm
usually doesn't need to even know what type of container it's dealing
with, nor does it need the container itself. It's enough for it to deal
with the iterators.

  Also iterators are a handy way of specifying sub-ranges of values inside
the container. There are also special iterators, for example reverse
iterators which work like regular ones, but act like the entire container
had been reversed. (Also more exotic iterators exist, such as stream
iterators, insert iterators, etc.)

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:

>   Do you want the imperative solution, or the template metaprogramming
> solution? ;)

Hmm... should I even get into this at 10:30 PM on a Saturday night? ;-)

>   There are two ways of iterating a vector: By indexing it and by using
> iterators. The latter method can also be used for any other STL container
> as well. The indexing method might be a bit clearer:
> 
> size_t smallestIndex = 0;
> for(size_t ind = 1; ind < theVector.size(); ++ind)
>     if(theVector[ind] < theVector[smallestInd])
>         smallestIndex = ind;
> 
>   When the loop ends, smallestIndex will be an index to the (first)
> smallest value inside the vector. Now the only trick is how to remove it:
> 
> theVector.erase(theVector.begin() + smallestIndex);
> 
>   (The erase() function requires an iterator. It doesn't work directly with
> index values. The begin() function returns an iterator to the first element
> in the vector. The reason why you can get an iterator to the nth element
> with an addition like that is that std::vector iterators are random access
> iterators and they support jumping to any location in the vector by adding
> an index value to them.)

Right, I see. So erase() is the function for removing stuff. (VC++ 
kindly tells me all the available members functions, but not what the *do*.)

I presume the reason for iterators is that some collections might be 
"unordered", and without iterators there would therefore be no way to 
iterate all elements? (And, similarly, that's why erase() wants an 
iterator.)

>   Note that erase() is an O(n) operation.

Yeah, that's kind of unavoidable.

>   You can also implement the same thing using iterators. The advantage is
> that the exact same code will work with any STL data container, not just
> vectors. For example, if you wanted to use an std::list instead, the
> iterator solution would work with that too.

Is there a "set" type laying around somewhere? The thing I'm processing 
*is* notionally a set, not an ordered collection.

>   To simplify the syntax it's usually a good idea to typedef the data
> container type:
> 
> typedef std::vector<int> Cont; // Could also be eg. an std::list<int> etc.
> 
>   Then you can perform the operation like this:
> 
> Cont::iterator smallestIter = theVector.begin();
> for(Cont::iterator iter = theVector.begin(); iter != theVector.end(); ++iter)
>     if(*iter < *smallestIter)
>         smallestIter = iter;
> 
> theVector.erase(smallestIter);

So... does that mean the iterator is a nested class then? (Just trying 
to understand the syntax.) Clearly each container type would end up 
needing a completely different iterator implementation...

>   Iterators work a bit like pointers. The prefix-* operator dereferences
> the iterator, ie. returns the value it's pointing to. The ++ operator
> changes the iterator to point to the next element in the container.
> The iterator returned by the end() function is a special iterator which
> points "past the end" (ie. to an imaginary element which is after the
> last element in the data container). When the iterator gets to the end()
> iterator, it means that the data container has no more values.
> 
>   If the type stored in the data container was a class with member
> functions, you could call such a member function with iter->function();
> (in the same way as with pointers).

OK.

>   Iterators are used a lot in STL containers and algorithms because they
> are a good way of abstracting away the actual container: An algorithm
> usually doesn't need to even know what type of container it's dealing
> with, nor does it need the container itself. It's enough for it to deal
> with the iterators.
> 
>   Also iterators are a handy way of specifying sub-ranges of values inside
> the container. There are also special iterators, for example reverse
> iterators which work like regular ones, but act like the entire container
> had been reversed. (Also more exotic iterators exist, such as stream
> iterators, insert iterators, etc.)

Sounds good... ;-)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

> Californians have a reputation for being... uh... "unusual". Which would 
> certainly explain... for example... your nick is "slime"? o_O And also 
> some of the wacky things you've rendered over the years.

Hah, well, in my defense I've only lived here 3 years. "Slime" comes from 
the Dragon Warrior games.

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

>  Anyways, these are technical details you don't have to worry about.

On the other hand, my computer science 2 class focused almost entirely on 
the STL data structures and how to implement them yourself. It was a good 
way to learn the intricacies of making a class that has to deal with 
cleaning itself up, thus needing copy constructors and assignment operators 
and destructors. Understanding how this all works gets you closer to 
understanding how your code is compiled and the sort of things that are 
allowed (such as how a vector of vectors works internally).

Another way to learn that sort of thing is to do it the C way first, where 
you have a struct with some pointers in it, and you write your own functions 
to initialize the data, copy the data, and destroy the data. Then you learn 
why those functions are necessary and what happens if you try to avoid using 
them. Finally you see why C++'s approach is so nice, even though it's so 
hard to learn. The POV-Ray source was helpful when I was learning this, but 
I don't know how well it's split between C and C++ anymore.

However, all of this should wait until you're comfortable with pointers.

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

Orchid XP v8 wrote:
> Is there a "set" type laying around somewhere? The thing I'm processing
> *is* notionally a set, not an ordered collection.

Yes: std::set.

> So... does that mean the iterator is a nested class then? (Just trying
> to understand the syntax.) Clearly each container type would end up
> needing a completely different iterator implementation...

Yes, each container has its own iterator. For a vector, it could even be a
plain old pointer instead of a class. And you don't even have to worry
about that :)

Post a reply to this message

> Is there a "set" type laying around somewhere? The thing I'm processing 
> *is* notionally a set, not an ordered collection.

std::set, I believe. Internally it uses a binary tree so it can quickly 
search for things. This means that whatever type you use it on has to work 
with the < operator; it uses < to know how to order the tree. (This is 
relevant because it means you have to define the < operator if you want to 
use it with your own class.)

You can google "std set" for documentation. This works for most or all STL 
types. The useful member function here is find( value ), which returns an 
iterator to the element with the given value, or returns yourset.end() 
otherwise. (Oh, insert() is useful too.)

 - Slime
 [ http://www.slimeland.com/ ]

Post a reply to this message

Slime wrote:
>> Is there a "set" type laying around somewhere? The thing I'm processing 
>> *is* notionally a set, not an ordered collection.
> 
> std::set, I believe. Internally it uses a binary tree so it can quickly 
> search for things. This means that whatever type you use it on has to work 
> with the < operator; it uses < to know how to order the tree. (This is 
> relevant because it means you have to define the < operator if you want to 
> use it with your own class.)

Heh. Exactly like Haskell's Data.Set ;-)

Question: What happens if your class doesn't have the comparison operator?

> You can google "std set" for documentation. This works for most or all STL 
> types. The useful member function here is find( value ), which returns an 
> iterator to the element with the given value, or returns yourset.end() 
> otherwise. (Oh, insert() is useful too.)

I'm more likely to be iterating the whole set and removing elements from 
it, but yeah. ;-)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

On Sun, 28 Sep 2008 10:41:43 +0200, Orchid XP v8 <voi### [at] devnull> wrote:
>
> Heh. Exactly like Haskell's Data.Set ;-)
>
> Question: What happens if your class doesn't have the comparison  
> operator?

You create a set with some other predicate as comparator.

I wonder: Do you not have access to documentation that explains this?



-- 
FE

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> >   Note that erase() is an O(n) operation.

> Yeah, that's kind of unavoidable.

  If the vector doesn't need to preserve the order of the elements then
you can remove the element in O(1) like this:

theVector[smallestInd] = theVector.back();
theVector.pop_back();

  In other words, copy the last element over the element to be removed,
and then remove the last element.

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> Question: What happens if your class doesn't have the comparison operator?

  If there's no way you can add an operator<() for your class, then you
can give std::set a comparator. A comparator is a functor used to compare
two elements of the same type (it takes two parameters of the type in
question, and returns a boolean telling if the first parameter is less
than the second parameter). This happens, for example, like this:

struct MyComparator
{
    // Note that this member function must be of 'const' type:
    bool operator()(const MyClass& lhs, const MyClass& rhs) const
    {
        return /* is lhs less than rhs? */;
    }
};

int main()
{
    // Make a type alias, to simplify the usage:
    typedef std::set<MyClass, MyComparator> TheSetType;

    TheSetType theSet;
    ...
}

  If your comparator has some state which may be different between sets,
you can give an initialized instance of your comparator to the set:

    TheSetType theSet(MyComparator(initialization, values));

  It is also possible to create a comparison function and use as a functor
(as you might remember). However, the syntax of the TheSetType definition
becomes a bit complicated.

  By the way, std::set (as well as std::map) *always* takes a comparator
(rather than using the < operator directly). When none is specified, the
default comparator used is std::less which, by template magic, makes it
completely equivalent to comparing the elements with the < operator
directly.

  This is good to know because you might sometimes want the elements
sorted in some other way. For example, if you want to sort them in
decreasing order, you can use the std::greater comparator (provided
by the standard C++ library). For example:

    typedef std::set<int, std::greater<int> > TheSetType;

  All integers added to this set will be in decreasing order rather than
in increasing one.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Orchid XP v8 <voi### [at] devnull> wrote:
>> Question: What happens if your class doesn't have the comparison operator?
> 
>   If there's no way you can add an operator<() for your class, then you
> can give std::set a comparator.

>   It is also possible to create a comparison function and use as a functor
> (as you might remember). However, the syntax of the TheSetType definition
> becomes a bit complicated.
> 
>   By the way, std::set (as well as std::map) *always* takes a comparator
> (rather than using the < operator directly). When none is specified, the
> default comparator used is std::less which, by template magic, makes it
> completely equivalent to comparing the elements with the < operator
> directly.
> 
>   This is good to know because you might sometimes want the elements
> sorted in some other way.

Sounds quite flexible.

(In particular, Haskell's own Data.Set provides no way to specify an 
alternate comparison operator. But then again, it only needs *a* 
comparison operator; which one you use doesn't really affect anything 
user-visible. The "sort" function allows you to specify a comparison 
operator manually though...)

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.

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> 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. :)

  (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".)

-- 
                                                          - Warp

Post a reply to this message

Slime wrote:
> thing after another. It's a lot like math - they don't teach fractions to 
> first graders because they need to spend time learning addition and 
> subtraction to fully master the concepts.

Ummm... They do teach basic fractions to first graders nowadays.

-- 
~Mike

Post a reply to this message

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

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

>> 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

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

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

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

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

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

Invisible <voi### [at] devnull> 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

>> 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

Warp <war### [at] tagpovrayorg> wrote:
>   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.

  Oh, and I forgot to say: The compiler doesn't even need to see the
implementation of 'createVector()' in order to do this optimization.
In other words, the compiler doesn't require to be able to inline that
function to do the optimization. The implementation of that function
could be in another compilation unit, or it could even be in a
precompiled library.

-- 
                                                          - Warp

Post a reply to this message

Invisible 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.

	And they let you go out of bounds, too!


-- 
Vultures only fly with carrion luggage.


                    /\  /\               /\  /
                   /  \/  \ u e e n     /  \/  a w a z
                       >>>>>>mue### [at] nawazorg<<<<<<
                                   anl

Post a reply to this message

Mueen Nawaz <m.n### [at] ieeeorg> wrote:
> Invisible 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.

>         And they let you go out of bounds, too!

  Well, you could use the at() member function if you want it to perform
bounds checks.

-- 
                                                          - Warp

Post a reply to this message

Mike Raiford wrote:
> "C allows you to shoot yourself in the foot. C++ allows you to shoot
> yourself in the foot and reuse the bullet"

I remember it differently.

"C makes it easy to shoot yourself in the foot. C++ makes it harder, but
when you do it blows the whole leg off."

Post a reply to this message

Warp wrote:
> Mueen Nawaz <m.n### [at] ieeeorg> wrote:
>> Invisible 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.
> 
>>         And they let you go out of bounds, too!
> 
>   Well, you could use the at() member function if you want it to perform
> bounds checks.

	Well, if we're dealing with vectors, why not just check its size? Is at
more efficient?

	Anyway, I wasn't complaining - I just wanted to make sure he knew that
in C++, nothing stops you from going out of bounds (probably to maintain
efficiency of lookups). Many other popular languages will die if you try
that.

-- 
When you die, you lose a very important part of your life.
                -- Brooke Shields


                    /\  /\               /\  /
                   /  \/  \ u e e n     /  \/  a w a z
                       >>>>>>mue### [at] nawazorg<<<<<<
                                   anl

Post a reply to this message

Nicolas Alvarez <nic### [at] gmailcom> wrote:
> "C makes it easy to shoot yourself in the foot. C++ makes it harder, but
> when you do it blows the whole leg off."

  I honestly don't understand what that is trying to say. I have no
experience (either personal or indirect) in C++ bugs being more severe
than C bugs.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   I honestly don't understand what that is trying to say. I have no
> experience (either personal or indirect) in C++ bugs being more severe
> than C bugs.
> 

"C makes it easy to shoot yourself in the foot; C++ makes it harder, but
when you do it blows your whole leg off".

"Yes, I said something like that (in 1986 or so). What people tend to miss,
is that what I said there about C++ is to a varying extent true for all
powerful languages. As you protect people from simple dangers, they get
themselves into new and less obvious problems. Someone who avoids the
simple problems may simply be heading for a not-so-simple one. One problem
with very supporting and protective environments is that the hard problems
may be discovered too late or be too hard to remedy once discovered. Also,
a rare problem is harder to find than a frequent one because you don't
suspect it."

from Bjarne Stroustrup's C++ FAQ.

Post a reply to this message

Nicolas Alvarez wrote:
> Mike Raiford wrote:
>> "C allows you to shoot yourself in the foot. C++ allows you to shoot
>> yourself in the foot and reuse the bullet"
> 
> I remember it differently.
> 
> "C makes it easy to shoot yourself in the foot. C++ makes it harder, but
> when you do it blows the whole leg off."

...and by a spine-tingling twist of coincidence...

http://www-users.cs.york.ac.uk/susan/joke/foot.htm

(Because somebody way trying to figure out the appropriate translation 
for Haskell.)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message

Orchid XP v8 wrote:

> http://www-users.cs.york.ac.uk/susan/joke/foot.htm
> 
> (Because somebody way trying to figure out the appropriate translation 
> for Haskell.)
> 

I know you're a fan of Perl, so I couldn't help but quote this one:

PERL
     You stab yourself in the foot repeatedly with an incredibly large 
and very heavy Swiss Army knife.

-- 
~Mike

Post a reply to this message

Mike Raiford wrote:

> I know you're a fan of Perl, so I couldn't help but quote this one:
> 
> PERL
>     You stab yourself in the foot repeatedly with an incredibly large 
> and very heavy Swiss Army knife.

My favourite Haskell suggestion so far:

     No instance for (Target Foot)
       arising from use of `shoot' at SelfInflictedInjury.hs:1:0
     Possible fix: add an instance declaration for (Target Foot)
     In the expression: shoot foot

(For those of you who aren't Haskell experts, this is pretty much 
_exactly_ what certain compiler errors look like.)

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message