STL sort not working??

Discussion in 'C++' started by Aaron Broad, Oct 10, 2003.

  1. Aaron Broad

    Aaron Broad Guest

    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
    Aaron Broad, Oct 10, 2003
    #1
    1. Advertising

  2. Aaron Broad wrote in news::

    >
    > 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.
    --
    http://www.victim-prime.dsl.pipex.com/
    Rob Williscroft, Oct 10, 2003
    #2
    1. Advertising

  3. Aaron Broad wrote:
    >


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

    --
    Karl Heinz Buchegger
    Karl Heinz Buchegger, Oct 10, 2003
    #3
  4. Aaron Broad

    Chris Theis Guest

    "Aaron Broad" <> wrote in message
    news:...
    > 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
    Chris Theis, Oct 10, 2003
    #4
  5. (Aaron Broad) wrote in message news:<>...

    > 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
    Shane Beasley, Oct 10, 2003
    #5
  6. <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
    Stewart Tootill, Oct 10, 2003
    #6
  7. Aaron Broad

    Aaron Broad Guest

    Well don't I feel stupid now:p

    Thanks, all.

    --Aaron Broad


    Rob Williscroft <> wrote in message news:<Xns94105CE3A9268ukcoREMOVEfreenetrtw@195.129.110.204>...
    > Aaron Broad wrote in news::
    >
    > >
    > > 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.
    Aaron Broad, Oct 10, 2003
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. nobody
    Replies:
    0
    Views:
    535
    nobody
    Jun 1, 2004
  2. Allan Bruce

    To STL or not to STL

    Allan Bruce, Oct 16, 2003, in forum: C++
    Replies:
    41
    Views:
    1,042
    Christopher Benson-Manica
    Oct 17, 2003
  3. JerryJ
    Replies:
    11
    Views:
    1,402
    Dave Moore
    Apr 28, 2004
  4. Navin
    Replies:
    1
    Views:
    690
    Ken Schaefer
    Sep 9, 2003
  5. GIMME
    Replies:
    5
    Views:
    185
    Thomas 'PointedEars' Lahn
    Jul 26, 2004
Loading...

Share This Page