Warp wrote:

>   I think that paper is a joke.

I really, *really* hope you're right about that...

Especially the use of multicoloured identifiers, and the use of dingbats 
as names!

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

Post a reply to this message

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. In 
languages with closures or pointers to member functions, no. Just like 
in a language without pointers at all, the way you do callbacks is to 
redefine the function at link-time and then do a big switch statement.

C#, for example, has the "observer" design pattern built into the 
language as "delegates" or "events", accepting multiple pointers to 
member functions and letting the owner "invoke" all the methods pointed to.

Ruby and Smalltalk and all those pass around "blocks" for this 
functionality. Python passes around lambdas. LISP passes around 
closures. They're all essentially the same sort of thing, with ever so 
slightly different implementations, but all basically "a block of code 
with a pointer to an object's context".

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

Post a reply to this message

Orchid XP v8 wrote:
> Yeah, but if the Haskell runtime has code to handle printing out a 
> human-readable error message on an unhandled exception, why can't it 
> also run some finalisers? This is pretty basic stuff!

Yep, true. I didn't realize you meant "exited cleanly due to an 
unhandled exception." I thought you meant "crashed out due to a signal, 
or running out of memory, or some such."

I suppose you could theoretically do a final GC and finalize before you 
exited (but perhaps before you printed the exception stack?), but I 
think at that point you're already pretty screwed. :-)

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

Post a reply to this message

Warp wrote:
>   I don't know how it is today, 

Usually a thousand or so, where such things are actually limited by 
something other than the amount of memory available.

>   If a program is constantly opening files, doing something to them, and
> then closing them, a file handle leak (which would happen if it fails to
> close them for some reason, eg. because of a bug or a suprising exception)
> can cause the program to malfunction. And this might not be caught on
> testing, if the testing fails to stress the program in the same way as
> it happens in actual usage...

Yep. That's exactly what was happening to me in my Tcl code. When I 
could get the socket connection but it failed before it finished 
flushing the first buffer, I failed to close the socket. After a couple 
weeks of running, the program would bomb out with a file handle leak. 
That was very annoying to debug. I probably should have just tossed that 
whole function and started over.

>   OTOH, I could imagine that if Java detects that a file cannot be opened
> because of too many file handles being open, it could automatically try
> to run the GC and then try again.

It could. That's what I like to recommend, but oddly few language 
designers listen to me. >8)

>   OTOH, file handles are just *one* possible resource which can leak.
> Java can't be prepared for all of them.

Well, it knows when something fails due to a lack of resources. It's 
even not unreasonable that (for example) opening a file could fail from 
lack of memory to put the stdio buffer in, or something, in which case a 
GC and a retry could correct it.

>> And it might not run if you exit 
>> the program before the GC runs, but that's true of C++ also.
> 
>   It's true of C++ only if your stream has been allocated dynamically
> (directly or indirectly). If it's stack-allocated then there's no way
> its destructor won't be called.

Yeah. And a sufficiently smart compiler for Java or whatever could do 
escape analysis, see that the stream isn't used outside the function, 
and stack allocate it and explicitly clean it up afterwards. Not that 
compilers quite do that yet.

>   (Ok, there is a way: If you call abort() the program is immediately
> terminated without any stack unwinding, in which case no destructors
> are called at all. However, abort() is such a harsh way of terminating
> the program that it shouldn't happen in normal code.

That's what I was talking about, yes. I thought Andrew was referring to 
exiting Haskell with a core dump, basically, rather than simply an 
exception caught at the top level.

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

Post a reply to this message

>> Yeah, but if the Haskell runtime has code to handle printing out a 
>> human-readable error message on an unhandled exception, why can't it 
>> also run some finalisers? This is pretty basic stuff!
> 
> Yep, true. I didn't realize you meant "exited cleanly due to an 
> unhandled exception." I thought you meant "crashed out due to a signal, 
> or running out of memory, or some such."
> 
> I suppose you could theoretically do a final GC and finalize before you 
> exited (but perhaps before you printed the exception stack?), but I 
> think at that point you're already pretty screwed. :-)

Basically, all you have to do is write a Haskell program that calls the 
"error" function somewhere, and your program will exit without closing 
anything behind it. Unless *you* remembered to take steps to prevent that.

That seems... a little unsafe to me.

Still, at least the code to do it isn't that hard.

   bracket
     (openFile "Foo.txt" ReadMode)
     (hClose)
     (\file_handle -> ...do stuff...)

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

Post a reply to this message

Orchid XP v8 wrote:
> Warp wrote:
> 
>>   I think that paper is a joke.
> 
> I really, *really* hope you're right about that...

""
Because this project relies of the ability
to fool the brain into accepting a projected image as 3D and because we 
don't take delivery of the 3D
projection device until next spring, this project is usually referred to 
as "Project April Fool."
""

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

Post a reply to this message

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.

-- 
                                                          - Warp

Post a reply to this message

Darren New wrote:

> ""
> Because this project relies of the ability
> to fool the brain into accepting a projected image as 3D and because we 
> don't take delivery of the 3D
> projection device until next spring, this project is usually referred to 
> as "Project April Fool."
> ""

Oh thank *God*!

Damn, he writes so convincingly...

[...says the guy who mistakenly took HGTTG seriously! o_O ]

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

Post a reply to this message

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?

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

Post a reply to this message

Invisible wrote:
> (E.g., apparently you can overload the "->" operator... GAH! >_< OK, I
> am *so* not trying that out!)

You can overload the comma operator!

boost::assign does some nasty stuff with it, to let you add stuff to STL
containers like this:

std::vector<int> mylist;
mylist += 1,2,3,4; // uses overloaded += and , operators

Post a reply to this message

Warp wrote:
>   Unless I'm completely mistaken, this is not something you can achieve
> in Java. (In Java you have to close files explicitly and catch all
> possible exceptions which might otherwise bypass that closing.)

You don't have to *catch* the exception, but you do need extra code. I don't
even remember how to open a file in Java, so here's some pseudo-code:

FileStream fs = /* open a file */;
try {
    fs.write("Hello\n");
    String data = getData(); //may throw exception
    fs.write(data);
} finally {
    fs.close();
}

Post a reply to this message

Nicolas Alvarez wrote:

> You can overload the comma operator!

Oh yeah - that too! :-S

> boost::assign does some nasty stuff with it, to let you add stuff to STL
> containers like this:
> 
> std::vector<int> mylist;
> mylist += 1,2,3,4; // uses overloaded += and , operators

...da hell? That's just mental!

OOC, what the hell is this "boost" I keep hearing about?

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

Post a reply to this message

On Fri, 26 Sep 2008 23:21:57 +0200, Orchid XP v8 <voi### [at] devnull> wrote:
>
> OOC, what the hell is this "boost" I keep hearing about?

www.boost.org



-- 
FE

Post a reply to this message

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