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