How to overload insertion operator >> in for std::map C++?

Question

I have a class Poly which is a class for polynomials basically. Poly has a private member of type std::map<int, int> called values_. I managed to overload the shift left operator << to be able to print my polynomial. for example if values_ have {(2,4), (1,0), (-1,-1)}, where the first is the exponent and second is the multiplier, the printed string to the ostream shall be 4x2+0x1-1x-1.

Now I am trying to find a way to overload the insertion operator >> so that if the user inputs 4x2+0x1-1x-1 the polynomial should be stored as {(2,4), (1,0), (-1,-1)}

What are the steps to handle std::istringstream to translate the input to be a polynomial?

class Poly {
public:
    typedef std::map<int, int> Values;
    typedef Values::const_reverse_iterator const_iterator;
    typedef Values::reverse_iterator iterator;

    const_iterator begin() const { return values_.rbegin(); }
    const_iterator end() const { return values_.rend(); }
    iterator begin() { return values_.rbegin(); }
    iterator end() { return values_.rend(); }
}



    int operator[](int exp) const;
    int& operator[](int exp) { return values_[exp]; }

private:
    Values values_;
};

std::istream& operator>>(std::istream& is, Poly& p);

std::ostream& operator<<(std::ostream& os, const Poly& p);

int Poly::operator[](int exp) const {
    Values::const_iterator it = values_.find(exp);
    return it == values_.end() ? 0 : it->second;
}

I suggest you start with the simplest case: a string with no spaces, like you currently output. You will need to first create parser code for mathematical polynomial expressions, which should be easy to find here or on Google. — Botje, Oct 04 '19 at 09:19
Are you asking about [parsing](https://en.wikipedia.org/wiki/Parsing)? The topic is quite complex and way too big for simple SO answer. — freakish, Oct 04 '19 at 09:47
You say that in your map that "the first is the exponent and second is the multiplier." However, in your example, you also have the key-value pair `(-1,-1)` even though you have no term with a negative power (e.g no `-1/x` term). — jjramsey, Oct 04 '19 at 12:32

Redgis · Answer 1 · 2019-10-04T23:24:31.757

The most efficient way to do the parsing would be to write your own parser (a state machine using nested switches could be enough for that simple grammar).

The easiest way I see is to use regex.

Here is how you could go about it :

std::istream& operator>>(std::istream& is, Poly& p) {

   std::regex rx("([+-]?[[:digit:]]+)x([+-]?[[:digit:]]+)");

   std::string line;
   int coef, exponent;

   std::getline(is, line);

   for (std::smatch m; std::regex_search(line, m, rx); line = m.suffix()) {
      coef = std::atoi(m[1].str().c_str());
      exponent = std::atoi(m[2].str().c_str());
      p.values_.insert(p.values_.end(), { exponent, coef });
   }

   return is;
}

std::ostream& operator<<(std::ostream& os, const Poly& p) {

   auto it = p.values_.begin();
   auto end = p.values_.end();
   while (it != end) {
      os << it->first << "x" << it->second;
      it++;
      if (it != end) {
         if (it->first >= 0)
            os << "+";
      }
   }

   return os;
}

Note you need to add those operators as friends of your Poly class in order for them to be allowed to access Poly members.

class Poly
{
public:
   typedef std::map<int, int> Values;
   typedef Values::const_reverse_iterator const_iterator;
   typedef Values::reverse_iterator iterator;

   const_iterator begin() const { return values_.rbegin(); }
   const_iterator end() const { return values_.rend(); }
   iterator begin() { return values_.rbegin(); }
   iterator end() { return values_.rend(); }

   int operator[](int exp) const;
   int& operator[](int exp) { return values_[exp]; }

   private:
      Values values_;

      friend std::istream& operator>>(std::istream& is, Poly& p);
      friend std::ostream& operator<<(std::ostream& os, const Poly& p);
};

A test :

int main(int argc, char * argv[]) {

   Poly poly;

   std::stringstream str("4x2+0x1-1x-1");
   str >> poly;
   std::cout << std::endl << poly << std::endl;

   return 0;
}

results in :

-1x-1+0x1+4x2

The keys are sorted in increasing order (thus the input order can't be retained):

Keys are sorted by using the comparison function Compare.

If you want to have your keys sorted in decreasing order, you can provide a custom compare operator (see this example).

If you don't care about the ordering of your keys, instead of using an std::map, you might want to use a std::unordered_map. unordered_map is implemented as a hash table, whereas the std::map is usually implemented as a red-black tree. Hash table has better access complexity.

If you want to retain input order you will want to use another data structure, like vector or list (e.g. : std::vector<std::pair<int, int> >), but then you will have to rewrite your access operator[].

"Using a std::map to store the coefficient pairs doesn't make much sense, since each key is unique. Thus if you have two polynomials beginning with same number." The key is the *exponent* not the multiplier. Aside from using a map rather than a vector, in principle, it's not much different than how Octave or Matlab encode polynomials: https://octave.org/doc/v4.2.1/Polynomial-Manipulations.html — jjramsey, Oct 04 '19 at 12:35
Ah I see, I get it now, thanks for the clarification. Edited my answer accordingly. — Redgis, Oct 04 '19 at 13:37

How to overload insertion operator >> in for std::map C++?

1 Answers1