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