lundi 18 mars 2019

STL reverse_iterator errors

I'm trying to build a huffman tree using the algorithm and I've reached a dead end of some sorts. I first took the string as user input, and then found the actual bit representation of the input to compare with the compressed bit sequence. I then used std::map to map the letters to their frequencies. Now what i'm trying to do is, get a reverse iterator and insert the key-value as a node in a huffman tree. But I'm having a huge list of errors for the iterator part.

#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <map>
#include <bitset>
#include <iterator>
#include <algorithm>
#include "htree.cpp"

// utility function to calculate the occurence of 'ith' letter //
const int countChar(const std::string& istring, char key) {
  int n = istring.length(); int iCount = 0;
  for(int i = 0; i < n; ++i) if(istring[i] == key) iCount++; 
  return iCount;
}

// calculates and stores the frequency of each letter in string //
void calcFreq(std::map<char, int>& fMap, const std::string& istring) {
  int n = istring.length();
  for(int i = 0; i < n; ++i) {
    fMap.insert(std::pair <char, int> (istring[i], 
countChar(istring,istring[i])));
  }
}

//prints the binary representation of the input string //
const void bitRep(const std::string& istring) {
  for(std::size_t i = 0; i < istring.size(); ++i) 
    std::cout<<std::bitset<8>(istring[i]);
}

int main() {

  std::string istring;
  getline(std::cin, istring);

  std::cout<<"\n Bit Representation: \n";
  bitRep(istring);
  std::cout<<std::endl;

  std::map <char, int> fMap;
  std::map<char, int>::iterator it;
  calcFreq(fMap, istring);

  std::cout<<"\tCHAR\tVALUE\n";
  for(it = fMap.begin(); it != fMap.end(); ++it) 
    std::cout<<'\t'<<it->first<<'\t'<<it->second<<'\n';
 // auto i = fMap.rbegin();
  std::map<char, int>::const_reverse_iterator i = fMap.rbegin();
  Node* node = (Node*)malloc(sizeof(Node)); 
  while(i != fMap.rend()) {
    for(std::map<char, int>::const_reverse_iterator j = i; j != i + 2; j++) 
      node = newNode(j->first, j->second);
    std::advance(i,2);
  }

  return 0;

}

I get a huge list of unreadable errors, listed below. I really don't know what i'm doing wrong and I've been at it almost a day. Help would be really appreciated.

λ g++ HAL.cpp In file included from c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\stl_algobase.h:67:0, from c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\char_traits.h:39, from c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\ios:40, from c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\ostream:38, from c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\iostream:39, from HAL.cpp:1: c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\stl_iterator.h: In instantiation of 'std::reverse_iterator<_Iterator> std::reverse_iterator<_Iterator>::operator+(std::reverse_iterator<_Iterator>::difference_type) const [with _Iterator = std::_Rb_tree_const_iterator >; std::reverse_iterator<_Iterator>::difference_type = int]': HAL.cpp:52:69: required from here c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\stl_iterator.h:233:41: error: no match for 'operator-' (operand types are 'const std::_Rb_tree_const_iterator >' and 'std::reverse_iterator > >::difference_type {aka int}') { return reverse_iterator(current - __n); } ~~~~~~~~^~~~~ c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\stl_iterator.h:333:5: note: candidate: template decltype ((__x.base() - __y.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_Iterator>&) operator-(const reverse_iterator<_Iterator>& __x, ^~~~~~~~ c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\stl_iterator.h:333:5: note: template argument deduction/substitution failed: c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\stl_iterator.h:233:41: note: 'const std::_Rb_tree_const_iterator >' is not derived from 'const std::reverse_iterator<_Iterator>' { return reverse_iterator(current - __n); } ~~~~~~~~^~~~~ c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\stl_iterator.h:387:5: note: candidate: template decltype ((__y.base() - __x.base())) std::operator-(const std::reverse_iterator<_Iterator>&, const std::reverse_iterator<_IteratorR>&) operator-(const reverse_iterator<_IteratorL>& __x, ^~~~~~~~ c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\stl_iterator.h:387:5: note: template argument deduction/substitution failed: c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\stl_iterator.h:233:41: note: 'const std::_Rb_tree_const_iterator >' is not derived from 'const std::reverse_iterator<_Iterator>' { return reverse_iterator(current - __n); } ~~~~~~~~^~~~~ c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\stl_iterator.h:1186:5: note: candidate: template decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorR>&) operator-(const move_iterator<_IteratorL>& __x, ^~~~~~~~ c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\stl_iterator.h:1186:5: note: template argument deduction/substitution failed: c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\stl_iterator.h:233:41: note: 'const std::_Rb_tree_const_iterator >' is not derived from 'const std::move_iterator<_IteratorL>' { return reverse_iterator(current - __n); } ~~~~~~~~^~~~~ c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\stl_iterator.h:1193:5: note: candidate: template decltype ((__x.base() - __y.base())) std::operator-(const std::move_iterator<_IteratorL>&, const std::move_iterator<_IteratorL>&) operator-(const move_iterator<_Iterator>& __x, ^~~~~~~~ c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\stl_iterator.h:1193:5: note: template argument deduction/substitution failed: c:\mingw\lib\gcc\mingw32\6.3.0\include\c++\bits\stl_iterator.h:233:41: note: 'const std::_Rb_tree_const_iterator >' is not derived from 'const std::move_iterator<_IteratorL>' { return reverse_iterator(current - __n); }

and btw, the function declaration for newNode is in another file:

Node* newNode(char data, int freq);

1 commentaire:

  1. Hi,
    The problem is in for loop in expression: ( j != i + 2; ).
    i iterator is bidirectional iterator.
    There is no operator- for bidirectional iterators,
    but there exist
    operator--
    So you can call the existing operator to get expected result.
    std::advance does that for you.

    Here is example of simple fix:

    template < class T >
    T myAdvance( T a )
    {
    T ret = a;
    std::advance(ret,2); // same as your i + 2
    return ret;
    }

    then instead of
    j != i + 2;
    use:
    j != myAdvance( i )

    RépondreSupprimer