STL sort not working??

[Aaron Broad]

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

std::list<HuffmanNode> forest;

float ftotal = (float)total;

for(int i = 0; i < 256; ++i)
if(frequency != 0)
forest.push_back(HuffmanNode(frequency/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

 

[Rob Williscroft]

Aaron Broad wrote in

std::list<HuffmanNode> forest;

float ftotal = (float)total;

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

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

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

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.

 

[Karl Heinz Buchegger]

std::list<HuffmanNode> forest;

float ftotal = (float)total;

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

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

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

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.

 

[Chris Theis]

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:
[SNIP]
Thanks in advance,
Aaron Broad

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

 

[Shane Beasley]

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

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

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

You should instead use

forest.sort(huffmanSortCriterion);

- Shane

 

[Stewart Tootill]

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

< 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

 

[Aaron Broad]

Well don't I feel stupid now

Thanks, all.

--Aaron Broad
(e-mail address removed)

Aaron Broad wrote in

std::list<HuffmanNode> forest;

float ftotal = (float)total;

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

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

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

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.