Original Post
Hello, I think I spotted a bug in std::sort or my GCC binary On Ubuntu Hardy 8.04: Using built-in specs. Target: x86_64-linux-gnu Configured with: ../src/configure -v --enable-languages=c,c++,fortran,objc,obj-c++,treelang --prefix=/usr --enable-shared --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --enable-nls --with-gxx-include-dir=/usr/include/c++/4.2 --program-suffix=-4.2 --enable-clocale=gnu --enable-libstdcxx-debug --enable-objc-gc --enable-mpfr --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu Thread model: posix gcc version 4.2.3 (Ubuntu 4.2.3-2ubuntu7) Running the following code gives me a wrong output: Compiled with g++ -o huffman main.cpp main.cpp huffman.h The output is: ./huffman 1, 1, 2, 2, 2, 3, 4, 3 2, 3, 1, weight: 6 2, weight: 3 3, 1, weight: 3 3, weight: 1 1, weight: 2 the first line should be: 1, 1, 2, 2, 2, 3, 3, 4, So either I did something wrong in my code or I just discovered a bug. Could some of you try to compile this source snipped and compare the results? Please also provide information about your compiler and OS. thx in advance.
1 #include "huffman.h"
2
3 int main( int argc, char** argv)
4 {
5 std::vector< unsigned int> symbols;
6 symbols.push_back(1);
7 symbols.push_back(2);
8 symbols.push_back(3);
9 symbols.push_back(4);
10 symbols.push_back(2);
11 symbols.push_back(2);
12 symbols.push_back(1);
13
14 const Node* root = BuildHuffmanTree(symbols);
15 root->Print();
16 return 0;
17 };
1 #ifndef HUFFMAN_H
2 #define HUFFMAN_H
3 #include <deque>
4 #include <vector>
5 #include <algorithm>
6 #include <iostream>
7 #include <iterator>
8
9 typedef unsigned int uint;
10 typedef std::vector< uint > SymbolVector;
11
12 class Node
13 {
14 public:
15 typedef std::deque< Node* > Queue;
16 public:
17 const uint weight;
18 SymbolVector symbol;
19 const Node* left;
20 const Node* right;
21 public:
22 Node(const uint _weight, const uint _symbol) : weight(_weight),symbol(1,_symbol),left(0),right(0) {};
23 Node(const Node* _left, const Node* _right)
24 :
25 weight(_left->weight + _right->weight),
26 left(_left),right(_right)
27 {
28 symbol.insert(symbol.end(),left->symbol.begin(),left->symbol.end());
29 symbol.insert(symbol.end(),right->symbol.begin(),right->symbol.end());
30 };
31 void Print() const
32 {
33 std::ostream_iterator<uint> ot(std::cout,", ");
34 std::copy(symbol.begin(),symbol.end(),ot);
35 std::cout<<"weight: "<<weight<<std::endl;
36 if(left) left->Print();
37 if(right) right->Print();
38 };
39 };
40
41 inline const bool queue_pred(const Node* a, const Node* b)
42 {
43 return a->weight < b->weight;
44 };
45
46 inline const Node* BuildHuffmanTree(const SymbolVector& csymbols)
47 {
48 SymbolVector uniquesymbols(csymbols);
49 std::sort(uniquesymbols.begin(),uniquesymbols.end());
50
51 std::ostream_iterator<uint> ot(std::cout,", ");
52 std::copy(uniquesymbols.begin(),uniquesymbols.end(),ot);
53 {
54 SymbolVector::iterator i = std::unique(uniquesymbols.begin(),uniquesymbols.end());
55 uniquesymbols.resize(uniquesymbols.end()-i);
56 }
57 std::cout<<uniquesymbols.size()<<std::endl;
58 Node::Queue queue;
59
60 for(SymbolVector::iterator i=uniquesymbols.begin();i!=uniquesymbols.end();++i)
61 {
62 const uint weight = std::count(csymbols.begin(),csymbols.end(),*i);
63 queue.push_back( new Node(weight,*i) );
64 }
65
66 while(queue.size() > 1)
67 {
68 std::sort(queue.begin(),queue.end(),queue_pred);
69 const Node* left = queue.front(); queue.pop_front();
70 const Node* right = queue.front(); queue.pop_front();
71 queue.push_back( new Node(left,right) );
72 }
73
74 const Node* result = queue.front();
75 return result;
76 };
77
78
79 #endif
