Inserting Objects containing three numbers into a std::map

[lostprophet]

Hello!

I tried to implement a map, which uses an object of a certain class as key. This class contains three numbers (phi, theta, norm). I've implemented the < operator as follows:

int operator<(const MyClass &left, const MyClass &right){
  return ((left.phi<right.phi) || (left.norm<right.norm) || (left.theta<right.theta));
}

When I insert some elements into the map everything works fine. I checked this by iterating over all elements.

Unfortunately, when adding elements and in the meanwhile accessing sometimes the map like in the example below (with myClasses[p]) additional elements are inserted automatically into the map. These elements have the same key as other earlier inserted elements but value=0.

const MyClass p(norm,phi,theta);
success=myClasses.insert(std::pair<MyClass, int>(p,counter));
if (success.second){
  counter++;
}else{
  std::cout << myClasses[p] << std::endl;
}

Does anybody have an idea what could be wrong with my code? Is the operator < implemented correctly?

Many thanks for your help!


lp

[writetonsharma]

your operator looks fine. you can have the return type as bool also.. as you are just returning a bool only.

return (left.phi<right.phi); //this will return a bool i think

your second part i am not able to understand, how is MyClass declared and its insert function?
because it could be like this also:

const MyClass p(norm,phi,theta);
std::map a_map;
retval = a_map.insert(std::pair<MyClass, int>(p,counter));
if (retval .second)
{
  counter++;
}
else
{
  std::cout << myClasses[p] << std::endl;
}

[lostprophet]

Sorry for the confusion. What I meant is exactly the way you stated:

for (int k=0; k<SomeNumber; k++){

// ... generate norm, phi, theta (which can be the same) ...

const MyClass p(norm,phi,theta);
std::map<MyClass, int> myClasses;
std::pair<std::map<MyClass, int>::iterator,bool> success;
success = myClasses.insert(std::pair<MyClass, int>(p,counter));
if (success.second)
{
  counter++;
}
else
{
  // when already an object p with specific values norm, theta, phi has been inserted then this values will be displayed just for testing 
  std::cout << myClasses[p] << std::endl;
}

}

std::map<MyClass, int>::iterator it;
for (it = myClasses.begin(); it!=myClasses.end(); it++){
  std::cout << it->first << ", " << it->second << std::endl;
}

The result of the second for loop is, that sometimes keys (it->first) occur two or more times with value (it->second) 0. Hopefully this is clearer now. Actually I am really confused, why this could be.

thx

lp

[writetonsharma]

i think you are doing it otheway round..
try doing it this way:

std::map<int, MyClass> myClasses;
std::pair<std::map<int, MyClass>::iterator,bool> success;
success = myClasses.insert(std::pair<int, MyClass>(counter, p));

i said this because 'p' is your value and conter is your position. and if you see the signatures of map::insert it like this:
iterator insert ( iterator position, const value_type& x );

now for different values of counter you are putting some redundant values of 'p' and when you see the result they show duplicate values.

its just a thought and it may work for you. try it.

[lostprophet]

Actually I don't understand what you mean. I need the value of myClass as a key. Because different objects of myClass should be assigned to different counters (which i need further down in the code). For equivalent objects I should get equivalent counters in the end.

What I found out now is, that my map contains keys, which have the same values (ie same norm, theta, phi). Since I use double numbers with a special number of decimal places (rounded to 8 decimal places), there shouldn't be any floating point problems. The only thing which I can think of is, that the operator< might be implemented incorrectly. Probably one of the necessary axioms are not fulfilled?

Irreflexivity f(x, x) must be false.
Antisymmetry f(x, y) implies !f(y, x)
Transitivity f(x, y) and f(y, z) imply f(x, z).
Transitivity of equivalence Equivalence (as defined above) is transitive: if x is equivalent to y and y is equivalent to z, then x is equivalent to z. (This implies that equivalence does in fact satisfy the mathematical definition of an equivalence relation.)

http://www.sgi.com/tech/stl/StrictWeakOrdering.html

[kempofighter]

@lostprophet: You have not shown us the full declaration of MyClass. What else is in it? You could be on to something about your operator <. Something seems strange about the way that you are using the logical or to test all 3 conditions. The function will not always test all 3 values to determine if one object is less than the other. I think that the operator should be defined more definitively. Shouldn't all 3 values of one be less than the other for the function to return true?

You could have a situation where
a < b
b < c
c < a

couldn't you?

What if objects had these values
                             a                 b                  c
phi                          7                 21                25
norm                        10                 15                 5
theta                       20                 25                27

In the above case, a < c will return true but so will c < a. How can the two objects be less than each other? It is possible using the operator< that you defined. Think about it.

@lostprophet: you seem to have found the answer. yes your operator< fails the strict weak ordering requirement. Plus you haven't given us a declaration of MyClass so who knows what else might be wrong.

[lostprophet]

You are right. This might be the problem. So I don't know how to formulate the condition for the less than operator. Do you have an idea how to do a better job?

class MyClass {
public:
  MyClass(double norm, double phi);
  MyClass(double norm, double phi, double theta);
  virtual ~MyClass();

  double getNorm() const { return norm; }
  double getPhi() const { return phi; }
  double getTheta() const { return theta; }

  friend int operator<(const MyClass& left, const MyClass& right);
  friend int operator==(const MyClass& left, const MyClass& right);

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


protected:
  double norm;				// rounded with 8 digits
  double phi;				// angle between y and x (in 2d)
  double theta;				// angle between z and r (in 3d)
};

[kempofighter]

@lostphrophet: what is MyClass supposed to be? Why do you need to use it as a key? I can't answer your question because I don't know what the class means. It seems pretty rare to see someone trying to use a complicated class like this as a key. A lot of times keys tend to be things like strings or integers. You really have to have to analyze your class's purpose and figure out what it means for one object to be less than another.

[writetonsharma]

ok..got it.

but the thing is by not implementing a < operator,how can you have duplicate values in map.
remove the < op for a while and see, if still you have duplicates that means < op dont have any effect.

ok..i've writtent this and the output is coming out correctly. tell me is this the output should come?
check the next post.

[writetonsharma]

#include <iostream>
#include <vector>
#include <string>
#include <map>
using namespace std;


class MyClass
{
public:
	MyClass(int x, int y, int z) : m_x(x), m_y(y), m_z(z)
	{}

	int m_x, m_y, m_z;
	void set(int x, int y, int z)
	{
		m_x = x;
		m_y = y;
		m_z = z;
	}

private:

};
int operator<(const MyClass &left, const MyClass &right)
{
  return ((left.m_x < right.m_x) || (left.m_y < right.m_y) || (left.m_z < right.m_z));
}


void main()
{
	int norm = 1, phi = 2, theta = 3;
	int counter = 0;
	std::map<MyClass, int> myClasses;
	MyClass p(norm,phi,theta);

	for (int k=0; k < 3; k++)
	{

		std::pair<std::map<MyClass, int>::iterator,bool> success;
		success = myClasses.insert(std::pair<MyClass, int>(p,counter));
		p.set(k + 10,k + 20,k + 30);

		
		if (success.second)
		{
		  counter++;
		}
		else
		{		  
		  //std::cout << myClasses[p] << std::endl;
			cout << "Exists" << endl;
		}
	}

	
	std::map<MyClass, int>::iterator it;
	for (it = myClasses.begin(); it!=myClasses.end(); it++)
	{
		std::cout << it->first.m_x << ", " << it->first.m_y << ", " << it->first.m_z << endl;
	}
}

output:

1, 2, 3
11, 21, 31
12, 22, 32

[writetonsharma]

is the problem that you are getting duplicates?? or is the problem that you have implemented < op incorrectly. I am now confused regarding the problem!!!

[lostprophet]

my class represents a coordinate in 2d or 3d space. When I have to compute something for new coordinates. First i will check, whether these coordinates are already in my map. If they are, then i just get an index, which tells me something of the further data.

I implemented it now with a std::vector. This worked well, since I can use the operator ==, which is properly defined. The drawback is, that i don't have any ordering in a tree (but this is not so time critical, thus its no real problem).

@writetonsharma: the problem was that i got duplicates, since I wasn't able to implement the < operator in a correct way (as said by kempofighter). Your code should sometimes as well insert duplicates, since this way of implementing the less than operator does not fullfill the transitivity criteria.

Thanks to all for your fast and kind help!

lp

[kempofighter]

I believe that the map is always using operator< to determine where to insert a new key, not operator==. If the new key isn't less than or greater than anything in the map then it must be already there and can't be inserted. The operator less can't allow both a < b and b < a to be true. writeonsharma's example worked only because of the values chosen for the keys but one could easily break that implementation simply by creating objects with different values. If the values represent a coordinate together, then somehow you have to use that meaning to provide an operator< that performs a calculation using the three values in a way that would always result in a different number for any variation in any of the 3 values. I don't have time to sort through the math and am not clear on what the "norm" parameter represents. You seem to have the idea though.

[Gumbercules]

shouldn't it look like this?

bool operator<(const MyClass &left, const MyClass &right){
    if (left.phi < right.phi)
        return true;
    if (right.phi < left.phi)
        return false
    if (left.norm < right.norm)
        return true;
    if (right.norm < left.norm)
        return false;
    return left.theta < right.theta;
}

[lostprophet]

Thank you very much. Of course you are right. One has to introduce a hierarchy to the several member variables. With your operator< everything works fine!