473,225 Members | 1,500 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,225 software developers and data experts.

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
Jul 19 '05 #1
6 5947
Aaron Broad wrote in news:42*************************@posting.google.co 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/
Jul 19 '05 #2


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
kb******@gascad.at
Jul 19 '05 #3

"Aaron Broad" <ou**@myrealbox.com> wrote in message
news:42*************************@posting.google.co 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
Jul 19 '05 #4
ou**@myrealbox.com (Aaron Broad) wrote in message news:<42*************************@posting.google.c 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
Jul 19 '05 #5
<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
Jul 19 '05 #6
Well don't I feel stupid now:P

Thanks, all.

--Aaron Broad
ou**@myrealbox.com

Rob Williscroft <rt*@freenet.REMOVE.co.uk> wrote in message news:<Xn**********************************@195.129 .110.204>...
Aaron Broad wrote in news:42*************************@posting.google.co 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.

Jul 19 '05 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
by: its me | last post by:
Let's say I have a class of people... Public Class People Public Sex as String Public Age as int Public Name as string end class And I declare an array of this class...
40
by: Elijah Bailey | last post by:
I want to sort a set of records using STL's sort() function, but dont see an easy way to do it. I have a char *data; which has size mn bytes where m is size of the record and n is the...
4
by: Grahamo | last post by:
Hi I'm working with deployed code and am looking for ways to optimise it and clean up memory leaks etc. I'm working with a template ContainerOfPointers, which is exactly that. It has methods...
7
by: ritchie | last post by:
Hi all, I am new to this group and I have question that you may be able to help me with. I am trying to learn C but am currently stuck on this. First of all, I have a function for each sort...
3
by: Bob Dankert | last post by:
Is there any way to maintain the sort order of a sort on a 2D array? For example: I have the array: 1,a 2,a 3,f 4,a 5,s 6,a 7,z 8,b and sort it by the second column, and I...
7
by: DC Gringo | last post by:
I have a datagrid that won't sort. The event handler is firing and return label text, just not the sort. Here's my Sub Page_Load and Sub DataGrid1_SortCommand: -------------------- Private...
4
by: IGotYourDotNet | last post by:
I'm trying to sort my grid and its working halfway, I can only sort the grid once and it puts everything in ASC order (1234555666) and i can't sort it again to display as DESC order (6665554321), ...
0
by: TM | last post by:
I was able to find the code to list the name and email from the contacts in Outlook 2003, but the sort property is not working. Here is my sample code. For now I am just adding an item to a...
5
by: Neil Chambers | last post by:
Hi All, I'm looking to see if it's feasible to use the SortObjectCommand included in the Microsoft.Powershell.Commands assembly. I have a Dictionary Dictionary<string, intd = new...
13
by: Vbbeginner07 | last post by:
its about Sorting a list view but its not working. please help....... Private Sub ListView1_ColumnClick(ByVal ColumnHeader As MSComctlLib.ColumnHeader) 'Determine whether the column is the same...
1
isladogs
by: isladogs | last post by:
The next online meeting of the Access Europe User Group will be on Wednesday 6 Dec 2023 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, Mike...
0
by: VivesProcSPL | last post by:
Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for...
0
by: jianzs | last post by:
Introduction Cloud-native applications are conventionally identified as those designed and nurtured on cloud infrastructure. Such applications, rooted in cloud technologies, skillfully benefit from...
0
by: abbasky | last post by:
### Vandf component communication method one: data sharing ​ Vandf components can achieve data exchange through data sharing, state sharing, events, and other methods. Vandf's data exchange method...
2
by: jimatqsi | last post by:
The boss wants the word "CONFIDENTIAL" overlaying certain reports. He wants it large, slanted across the page, on every page, very light gray, outlined letters, not block letters. I thought Word Art...
0
by: fareedcanada | last post by:
Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like...
0
Git
by: egorbl4 | last post by:
Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ...
1
by: davi5007 | last post by:
Hi, Basically, I am trying to automate a field named TraceabilityNo into a web page from an access form. I've got the serial held in the variable strSearchString. How can I get this into the...
0
by: MeoLessi9 | last post by:
I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.