STL sort not working??

I can't get STL sort to work for this little huffman encoding program
i'm writing. I get a whole whack of errors eminating from the line
that call sthe sort. They all look like the following error:

main.cpp:44: instantiated from here
/usr/include/c++/3.2.2/bits/stl_algo.h:2004: no match for `
std::_List_iterator<HuffmanNode, HuffmanNode&, HuffmanNode*>& +
int'
operator
/usr/include/c++/3.2.2/bits/stl_algo.h:2079: instantiated from `void
std::__final_insertion_sort(_RandomAccessIter, _RandomAccessIter,
_Compare) [with _RandomAccessIter = std::_List_iterator<HuffmanNode,
HuffmanNode&, HuffmanNode*>, _Compare = bool (*)(const HuffmanNode&,
const HuffmanNode&)]'
/usr/include/c++/3.2.2/bits/stl_algo.h:2210: instantiated from `void
std::sort(_RandomAccessIter, _RandomAccessIter, _Compare) [with
_RandomAccessIter = std::_List_iterator<HuffmanNode, HuffmanNode&,
HuffmanNode*>, _Compare = bool (*)(const HuffmanNode&, const
HuffmanNode&)]'
main.cpp:44: instantiated from here
/usr/include/c++/3.2.2/bits/stl_algo.h:2008: no match for `
std::_List_iterator<HuffmanNode, HuffmanNode&, HuffmanNode*>& +
int'
operator


here is my code:

#include "HuffmanNode.h"

bool huffmanSortCriterion(const HuffmanNode& h1, const HuffmanNode&
h2);

/*main.cpp*/
int main(int argc, char *argv[]) {
//validate arguments

//create array
char frequency[256];
for(int i = 0; i < 256; ++i)
frequency[i] = 0;

//open file for input
std::fstream input_file("test.txt", std::ios::in |
std::ios::binary);

int total = 0;
while(!input_file.eof()) {
++frequency[input_file.get()];
++total;
}
for(int i = 0; i < 256; ++i)
std::cout << (int)frequency[i];

std::list<HuffmanNode> forest;

float ftotal = (float)total;

for(int i = 0; i < 256; ++i)
if(frequency[i] != 0)
forest.push_back(HuffmanNode(frequency[i]/ftotal, (char)i));

std::cout << forest.size();

std::sort(forest.begin(), forest.end(), huffmanSortCriterion);

/* ... */
}

bool huffmanSortCriterion(const HuffmanNode& h1, const HuffmanNode&
h2) {
return h1.getWeight() < h2.getWeight();
}

/*HuffmanNode.h*/
#ifndef HuffmanNode_H
#define HuffmanNode_H

class HuffmanNode {
private:
float weight;
char character;
HuffmanNode *zeroChild;
HuffmanNode *oneChild;

public:
HuffmanNode() {}
HuffmanNode(const float Weight, const char Character);
HuffmanNode(HuffmanNode *ZeroChild, HuffmanNode *OneChild);
inline float getWeight() const;
inline char getChar();
};

#endif

/*HuffmanNode.cpp*/

#include "HuffmanNode.h"

HuffmanNode::HuffmanNode(const float Weight, const char Character) {
weight = Weight;
character = Character;
zeroChild = 0;
oneChild = 0;
}

HuffmanNode::HuffmanNode(HuffmanNode *ZeroChild, HuffmanNode
*OneChild) {
zeroChild = ZeroChild;
oneChild = OneChild;
weight = zeroChild->getWeight() + oneChild->getWeight();
}

inline float HuffmanNode::getWeight() const {
return (weight);
}

inline char HuffmanNode::getChar() {
return (character);
}

/* end of code */

Thanks in advance,
Aaron Broad

re: STL sort not working??

Aaron Broad wrote in news:427af6fd.0310092112.eae63dd@posting.google.co m:
[color=blue]
>
> std::list<HuffmanNode> forest;
>
> float ftotal = (float)total;
>
> for(int i = 0; i < 256; ++i)
> if(frequency[i] != 0)
> forest.push_back(HuffmanNode(frequency[i]/ftotal, (char)i));
>
> std::cout << forest.size();
>
> std::sort(forest.begin(), forest.end(), huffmanSortCriterion);
>
>[/color]

std::sort() requires a random access sequence to sort, std::list<>
dosen't provide this, use a different container, std::vector<> or
std::deque<> , or use std::list<>'s sort( F ) member function.

HTH

Rob.
--
http://www.victim-prime.dsl.pipex.com/

re: STL sort not working??

Aaron Broad wrote:[color=blue]
>[/color]
[color=blue]
>
> std::list<HuffmanNode> forest;
>
> float ftotal = (float)total;
>
> for(int i = 0; i < 256; ++i)
> if(frequency[i] != 0)
> forest.push_back(HuffmanNode(frequency[i]/ftotal, (char)i));
>
> std::cout << forest.size();
>
> std::sort(forest.begin(), forest.end(), huffmanSortCriterion);
>[/color]

std::list is a special container. You can't apply std::sort on it.
If you think of it, most sorting algorithms depend on direct access
to each container element, as can be done with eg. std::vector. This
will not work for lists. In a list accessing the 6-th element is a pain
in the ass.

But std::list has it's own sort method:

forest.sort( ... );

Or of course you could change the data type of forest to a std::vector
instead of a std::list. You decide.

--
Karl Heinz Buchegger
kbuchegg@gascad.at

re: STL sort not working??

"Aaron Broad" <oube@myrealbox.com> wrote in message
news:427af6fd.0310092112.eae63dd@posting.google.co m...[color=blue]
> I can't get STL sort to work for this little huffman encoding program
> i'm writing. I get a whole whack of errors eminating from the line
> that call sthe sort. They all look like the following error:
>[/color]
[SNIP][color=blue]
> Thanks in advance,
> Aaron Broad[/color]

If you take a look at the signature of the standard library's sort function
you'll see that it expects RandomAccessIterators. This is an iterator type
that is not supported by lists. However, lists provide a special member
function to sort elements. On the other hand you could also change the
container type.

HTH
Chris

re: STL sort not working??

oube@myrealbox.com (Aaron Broad) wrote in message news:<427af6fd.0310092112.eae63dd@posting.google.c om>...
[color=blue]
> I can't get STL sort to work for this little huffman encoding program
> i'm writing. I get a whole whack of errors eminating from the line
> that call sthe sort. They all look like the following error:
>
> main.cpp:44: instantiated from here
> /usr/include/c++/3.2.2/bits/stl_algo.h:2004: no match for `
> std::_List_iterator<HuffmanNode, HuffmanNode&, HuffmanNode*>& +
> int'
> operator[/color]

std::sort requires a random-access iterator, like the kind you'd get
from std::vector or std::deque. std::list only has a bidirectional
iterator, so you can't use std::sort on it. (The error you're getting
is that std::sort is trying to do *(iterator + offset), but that
functionality is unique to random-access iterators.) However,
std::list has its own .sort() member function which does roughly the
same thing. That is, instead of
[color=blue]
> std::sort(forest.begin(), forest.end(), huffmanSortCriterion);[/color]

You should instead use

forest.sort(huffmanSortCriterion);

- Shane

re: STL sort not working??

<snip>
[color=blue]
> main.cpp:44: instantiated from here
> /usr/include/c++/3.2.2/bits/stl_algo.h:2004: no match for `
> std::_List_iterator<HuffmanNode, HuffmanNode&, HuffmanNode*>& +
> int'
> operator
> /usr/include/c++/3.2.2/bits/stl_algo.h:2079: instantiated from `void
> std::__final_insertion_sort(_RandomAccessIter, _RandomAccessIter,
> _Compare) [with _RandomAccessIter = std::_List_iterator<HuffmanNode,
> HuffmanNode&, HuffmanNode*>, _Compare = bool (*)(const HuffmanNode&,
> const HuffmanNode&)]'
> /usr/include/c++/3.2.2/bits/stl_algo.h:2210: instantiated from `void
> std::sort(_RandomAccessIter, _RandomAccessIter, _Compare) [with
> _RandomAccessIter = std::_List_iterator<HuffmanNode, HuffmanNode&,
> HuffmanNode*>, _Compare = bool (*)(const HuffmanNode&, const
> HuffmanNode&)]'
> main.cpp:44: instantiated from here
> /usr/include/c++/3.2.2/bits/stl_algo.h:2008: no match for `
> std::_List_iterator<HuffmanNode, HuffmanNode&, HuffmanNode*>& +
> int'
> operator
>
>[/color]

< snip the code >

I haven't looked at the docs to check this, but it appears from the
errors that sort requires a random access iterator, and that list
iterators are not random access. I can't remember from your code
whether you need a list specifically, but try a vector, where the
iterators are definitely random access.

Yours,

Stewart Tootill

re: STL sort not working??

Well don't I feel stupid now:P

Thanks, all.

--Aaron Broad
oube@myrealbox.com

Rob Williscroft <rtw@freenet.REMOVE.co.uk> wrote in message news:<Xns94105CE3A9268ukcoREMOVEfreenetrtw@195.129 .110.204>...[color=blue]
> Aaron Broad wrote in news:427af6fd.0310092112.eae63dd@posting.google.co m:
>[color=green]
> >
> > std::list<HuffmanNode> forest;
> >
> > float ftotal = (float)total;
> >
> > for(int i = 0; i < 256; ++i)
> > if(frequency[i] != 0)
> > forest.push_back(HuffmanNode(frequency[i]/ftotal, (char)i));
> >
> > std::cout << forest.size();
> >
> > std::sort(forest.begin(), forest.end(), huffmanSortCriterion);
> >
> >[/color]
>
> std::sort() requires a random access sequence to sort, std::list<>
> dosen't provide this, use a different container, std::vector<> or
> std::deque<> , or use std::list<>'s sort( F ) member function.
>
> HTH
>
> Rob.[/color]