Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > STL sort not working??

Reply
Thread Tools

STL sort not working??

 
 
Aaron Broad
Guest
Posts: n/a
 
      10-10-2003
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
 
Reply With Quote
 
 
 
 
Rob Williscroft
Guest
Posts: n/a
 
      10-10-2003
Aaron Broad wrote in news:(E-Mail Removed) m:

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


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/
 
Reply With Quote
 
 
 
 
Karl Heinz Buchegger
Guest
Posts: n/a
 
      10-10-2003


Aaron Broad wrote:
>


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


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
http://www.velocityreviews.com/forums/(E-Mail Removed)
 
Reply With Quote
 
Chris Theis
Guest
Posts: n/a
 
      10-10-2003

"Aaron Broad" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed) m...
> 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


 
Reply With Quote
 
Shane Beasley
Guest
Posts: n/a
 
      10-10-2003
(E-Mail Removed) (Aaron Broad) wrote in message news:<(E-Mail Removed) om>...

> 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
 
Reply With Quote
 
Stewart Tootill
Guest
Posts: n/a
 
      10-10-2003
<snip>

> 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
 
Reply With Quote
 
Aaron Broad
Guest
Posts: n/a
 
      10-10-2003
Well don't I feel stupid now

Thanks, all.

--Aaron Broad
(E-Mail Removed)

Rob Williscroft <(E-Mail Removed)> wrote in message news:<Xns94105CE3A9268ukcoREMOVEfreenetrtw@195.129 .110.204>...
> Aaron Broad wrote in news:(E-Mail Removed) m:
>
> >
> > 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);
> >
> >

>
> 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.

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: When will Thunderbird support sort in place (in context sort)? Ron Natalie Firefox 0 02-02-2006 04:38 AM
Array sort function sorts on chars not numbers ... help ! how to sort numbers GIMME Javascript 5 07-26-2004 01:28 AM
xsl:sort lang="es" modern vs. tradidional Spanish sort order nobody XML 0 06-01-2004 06:25 AM
To STL or not to STL Allan Bruce C++ 41 10-17-2003 08:21 PM
Ado sort error-Ado Sort -Relate, Compute By, or Sort operations cannot be done on column(s) whose key length is unknown or exceeds 10 KB. Navin ASP General 1 09-09-2003 07:16 AM



Advertisments