0

I am running an algorithm in C++ based on a binary tree computation with iteration and induction.

For this purpose I nested map like this 

typedef map<double, bool> b1d;
typedef map<double, b1d> mb2d;
typedef vector<mb2d> vb3d;

typedef map<double, double> m1d;
typedef map<double, m1d> m2d;
typedef vector<m2d> v3d;

m2d ZY;
v3d * V = new v3d (n+1, m2d(ZY));

mb2d ZYb;
vb3d * Vb = new vb3d (n+1, mb2d(ZYb));

and I change the values like that 

(*J_tab)[K+1.0][Z+y][W - 1.0/sqrt((double) n)] = V_tmp;
(*J_bool)[K+1.0][Z+y][W - 1.0/sqrt((double) n)] = true;

The problem is I obtain many duplication and it is strange for an std::map as you can see in this picture I have obtained with my debugger Debugger In this picture you can see in the second degree many duplication 0.6 or 0.7 for instance and at the third degree in 0.3.

The only way to get rid of the duplication I have found is to change double to string i.e. 

typedef map<string, bool> b1d;
typedef map<string, b1d> mb2d;
typedef vector<mb2d> vb3d;

and making those operations

            std::string strZy, strWm, strWp;
            std::ostringstream strsZy, strsWm, strsWp;
            int precision = 5;
            strsZy << fixed << setprecision(precision) << Z+y;
            strsWp << fixed << setprecision(precision) << W + 1.0/sqrt((double) n);
            strsWm << fixed << setprecision(precision) << W - 1.0/sqrt((double) n);
            strZy = strsZy.str();
            strWm = strsWm.str();strWp = strsWp.str();

However I think it takes more memory than a double and more time, so it is not the most efficient solution.

Someone know how to correct it ? or another elegant way to do it ?

Al Bundy
  • 184
  • 1
  • 12
  • 4
    Floating points cannot always perfectly represent the real numbers, therefor they are not suitable for a key. See [this question](https://stackoverflow.com/questions/21895756/why-are-floating-point-numbers-inaccurate). I reccommend implementing a custom comparator that takes note of this inaccuracy. – Neijwiert Apr 04 '19 at 08:43
  • And you may consider using a single map with a `struct`or a `tuple` as a key, and a `struct`or a `tuple`as a value. You would then get all the benefits of the map. – Laurent LA RIZZA Apr 04 '19 at 08:45
  • @Neijwiert And why I have some duplicated elements with only one digit (0.6 for instance). Maybe because it is a shortcut of the debugger rather than writing 0.60000...many 0...01 ? – Al Bundy Apr 04 '19 at 08:46
  • @AlBundy I cannot answer that question, for I don't know how-why the debugger handles doubles that way. Maybe somebody else can. Try searching for it or asking a new question if it does not exists yet. – Neijwiert Apr 04 '19 at 08:49
  • Looking at the values in your sample, you might want to think about a fixed precision type. You could roll your own, or there are problably libraries you could use. – john Apr 04 '19 at 08:49
  • 1
    @AlBundy I'm sure that is because your debugger is truncating the displayed value. You will not get duplicates if the value is exactly the same. – john Apr 04 '19 at 08:51
  • 2
    You may round your keys before using then on map, this should give similar result to your string solution where you use precision of 5 – marcinj Apr 04 '19 at 08:56
  • 2
    @Neijwiert I would like to see how you want to implement a custom comparator that compares slightly-different floats as equal while upholding transitivity of equality... Consider `x`, `x-eps` and `x+eps`, where `x == x-eps` and `x == x+eps`, so `x-eps == x+eps`? Do you see the problem? – Max Langhof Apr 04 '19 at 09:27
  • @MaxLanghof yeah you're right it would be a naive implementation – Neijwiert Apr 04 '19 at 09:57

0 Answers0