Using own class as key in map causes segmentation fault

[nw]

Hi,

I'm trying to use my own class as a map key. However something strange
seems to be happening to the map which causes my program to segfault.
I'm at a loss as to what this might be. Can anyone help?

The complete example below segfaults for me under g++ 4.1.2. Using a
debugger it seems that one of the MultiDimKey objects the map is
holding becomes corrupt.

#include <vector>
#include <map>
#include <string>
#include <iostream>

using namespace std;

class MultiDimKey {
public:

MultiDimKey() : keys() {
}

MultiDimKey(const vector<string> keys_in) : keys(keys_in) {
}

bool operator<(const MultiDimKey &other) const {

const vector<string> other_keys = other.keys;

for(size_t n=0;n<keys.size();n++) {
if(keys[n] < other_keys[n]) return true;
}

return false;
}

vector<string> keys;
};

int main() {

map<MultiDimKey,int> test;

vector<string> s1;
s1.push_back("3");
s1.push_back("6");
MultiDimKey k1(s1);
test[k1]++;

vector<string> s2;
s2.push_back("5");
s2.push_back("3");
MultiDimKey k2(s2);
test[k2]++;

vector<string> s3;
s3.push_back("6");
s3.push_back("2");
MultiDimKey k3(s3);
test[k3]++;

vector<string> s4;
s4.push_back("1");
s4.push_back("2");
MultiDimKey k4(s4);
test[k4]++;
}

 

[Alf P. Steinbach]

* nw:

Hi,

I'm trying to use my own class as a map key. However something strange
seems to be happening to the map which causes my program to segfault.
I'm at a loss as to what this might be. Can anyone help?

The complete example below segfaults for me under g++ 4.1.2. Using a
debugger it seems that one of the MultiDimKey objects the map is
holding becomes corrupt.

#include <vector>
#include <map>
#include <string>
#include <iostream>

using namespace std;

class MultiDimKey {
public:

MultiDimKey() : keys() {
}

MultiDimKey(const vector<string> keys_in) : keys(keys_in) {
}

bool operator<(const MultiDimKey &other) const {

const vector<string> other_keys = other.keys;

for(size_t n=0;n<keys.size();n++) {
if(keys[n] < other_keys[n]) return true;
}

By this criterion ["3","6"] < ["5","3"] and ["5","3"] < ["3","6"].

std::map will have a really hard time ordering those keys...

return false;
}

vector<string> keys;
};

Cheers & hth.,

- Alf

 

[nw]

By this criterion ["3","6"] < ["5","3"] and ["5","3"] < ["3","6"].

std::map will have a really hard time ordering those keys...

Doh! Thanks Alf.

 

[Jorgen Grahn]

Hi,

I'm trying to use my own class as a map key. However something strange
seems to be happening to the map which causes my program to segfault.
I'm at a loss as to what this might be. Can anyone help? ....

bool operator<(const MultiDimKey &other) const {

const vector<string> other_keys = other.keys;

Not a good place to copy a whole vector<string>, if you want an
efficient map! (It also doesn't simplify the code or even save
any typing.)

for(size_t n=0;n<keys.size();n++) {
if(keys[n] < other_keys[n]) return true;
}

return false;
}

/Jorgen

 

[AnonMail2005]

Hi,

I'm trying to use my own class as a map key. However something strange
seems to be happening to the map which causes my program to segfault.
I'm at a loss as to what this might be. Can anyone help?
...

  bool operator<(const MultiDimKey &other) const {

    const vector<string> other_keys = other.keys;

Not a good place to copy a whole vector<string>, if you want an
efficient map!  (It also doesn't simplify the code or even save
any typing.)

    for(size_t n=0;n<keys.size();n++) {
      if(keys[n] < other_keys[n]) return true;
    }

    return false;
  }

/Jorgen

There is also a copy of the entire vector in the constructor!!!

HTH

 

[Vladimir Jovic]

There is also a copy of the entire vector in the constructor!!!

No, there isn't. That is the copy constructor that is copying the vector
(which it should)

 

[Michael Doubez]

* nw:

I'm trying to use my own class as a map key. However something strange
seems to be happening to the map which causes my program to segfault.
I'm at a loss as to what this might be. Can anyone help? {snip]
  bool operator<(const MultiDimKey &other) const {

    const vector<string> other_keys = other.keys;

    for(size_t n=0;n<keys.size();n++) {
      if(keys[n] < other_keys[n]) return true;
    }

By this criterion ["3","6"] < ["5","3"] and ["5","3"] < ["3","6"].

std::map will have a really hard time ordering those keys...

And if other.keys.size() < keys.size(), there is UB (and certainly a
segfault).
[snip]

 

[AnonMail2005]

No, there isn't. That is the copy constructor that is copying the vector
(which it should)

There are *two* copies - only one is needed. If you notice, the
argument to the copy constructor is passed by *value* which makes an
extra (unneeded) copy. After that copy, there's another "copy" which
initializes the data member.

HTH