Using own class as key in map causes segmentation fault

Discussion in 'C++' started by nw, Mar 16, 2010.

  1. nw

    nw Guest

    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]++;
    }
    nw, Mar 16, 2010
    #1
    1. Advertising

  2. * 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
    Alf P. Steinbach, Mar 16, 2010
    #2
    1. Advertising

  3. nw

    nw Guest


    > 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.
    nw, Mar 16, 2010
    #3
  4. nw

    Jorgen Grahn Guest

    On Tue, 2010-03-16, nw wrote:
    > 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

    --
    // Jorgen Grahn <grahn@ Oo o. . .
    \X/ snipabacken.se> O o .
    Jorgen Grahn, Mar 16, 2010
    #4
  5. nw

    Guest

    On Mar 16, 5:35 pm, Jorgen Grahn <> wrote:
    > On Tue, 2010-03-16, nw wrote:
    > > 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
    >
    > --
    >   // Jorgen Grahn <grahn@  Oo  o.   .  .
    > \X/     snipabacken.se>   O  o   .


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

    HTH
    , Mar 17, 2010
    #5
  6. wrote:
    >
    > 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)
    Vladimir Jovic, Mar 18, 2010
    #6
  7. On 16 mar, 12:23, "Alf P. Steinbach" <> wrote:
    > * 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).

    >
    >
    > >     return false;
    > >   }

    >
    > >   vector<string> keys;
    > > };

    >

    [snip]
    Michael Doubez, Mar 18, 2010
    #7
  8. nw

    Guest

    On Mar 18, 4:43 am, Vladimir Jovic <> wrote:
    > wrote:
    >
    > > 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)


    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
    , Mar 18, 2010
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Patrick Guio
    Replies:
    6
    Views:
    3,162
    chris
    Oct 20, 2004
  2. Peter Jansson
    Replies:
    5
    Views:
    6,253
    Ivan Vecerina
    Mar 17, 2005
  3. strtok causes Segmentation fault

    , May 11, 2006, in forum: C Programming
    Replies:
    17
    Views:
    791
    void * clvrmnky()
    May 12, 2006
  4. Bryan
    Replies:
    9
    Views:
    606
    Juha Nieminen
    Nov 1, 2007
  5. eliweiq001
    Replies:
    12
    Views:
    792
    Keith Thompson
    Oct 6, 2010
Loading...

Share This Page