Sign in to follow this  

std::map ignoring insertions??? [solved]

This topic is 3296 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm having this problem with std::map, where it sometimes seems not to do anything when I insert things into it. I know that's probably not really the issue, but anyway... I'm writing a program that, among other things, retrieves and displays chord diagrams from a file. I have a class to represent a chord, and a chord diagrams. The diagrams will generally be requested by chord name, but since many names may map onto the same basic chord, I construct a chord from the name and use that as a key in a std::map, thus:
std::map<chord, chord_diagram::group>
Where chord_diagram is one of either guitar_chord or piano_chord, and chord_diagram::group is just a typedef for std::vector<chord_diagram>. Without further ado, a small program that reproduces the error:
#include <iostream>
#include <map>
#include <string>

#include "chord.h"
#include "chord_diagram.h"

using std::cout;
using std::endl;
using std::string;
using music::chord;

int main(){
    //typedefs
    typedef guitar_chord curr_chord_t;
    typedef std::map<music::chord, curr_chord_t::group> map_t;
    //make chords
    chord c1("C"), c2("Ddim"), c3("F#7");
    //make diagrams
    curr_chord_t::group g1, g2, g3;
    g1.push_back(curr_chord_t(string("100000")));
    g2.push_back(curr_chord_t(string("110000")));
    g2.push_back(curr_chord_t(string("111000")));
    g3.push_back(curr_chord_t(string("111100")));
    g3.push_back(curr_chord_t(string("111110")));
    //make a test map
    map_t mappy;
    //insert chords
    mappy[c1] = g1;
    mappy[c2] = g2;
    mappy[c3] = g3;
    //test for their existence
    map_t::iterator iter;
    //test for c1
    iter = mappy.find(c1);
    cout << c1.name();
    if(iter == mappy.end())
        cout << " NOT found";
    else
        cout << " IS found";
    cout << endl;
    //test for c2
    iter = mappy.find(c2);
    cout << c2.name();
    if(iter == mappy.end())
        cout << " NOT found";
    else
        cout << " IS found";
    cout << endl;
    //test for c3
    iter = mappy.find(c3);
    cout << c3.name();
    if(iter == mappy.end())
        cout << " NOT found";
    else
        cout << " IS found";
    cout << endl;
}


Output:
C IS found
Ddim NOT found
F#7 IS found
Even though, obviously, I just inserted Ddim. Different things get left out if you vary the order of the insertions. In particular, the first one always makes it in. I'll post all that if someone wants to see it. I'm fairly sure that the problem is with chord::operator<, but I really don't know. Heres the declaration of the class (I sincerely apologize for the huge, ugly member class, and the not entirely helpful comments):
namespace music{
    //chord class
    class chord{
        //member type to indicate a chord type
        class type{
                public:
            //default constructor
            type();
            //general purpose
            std::string name() const;
            bool operator<(const type&) const;
            //accessors for third note
            bool isTwo() const;
            bool isMinor() const;
            bool isMajor() const;
            bool isSus() const;
            bool hasThird() const;
            //accessor for fifth note
            bool isDim() const;
            //seventh and beyond
            bool hasSeventh() const;
            bool hasMajSeventh() const;
            bool hasNinth() const;
            //mutators
            void setTwo(bool);
            void setMinor(bool);
            void setMajor(bool);
            void setSus(bool);
            void setHasThird(bool);
            void setDim(bool);
            void setSeventh(bool);
            void setMajSeventh(bool);
            void setNinth(bool);
                protected:
            std::bitset<4> type_bits;
            enum bit_index{is_dim, seventh, maj_seventh, ninth};//indices for type_bits
            enum {none, two, minor, major, sus} middle_note; //stores the state of the middle note
        };
            public:
        //constructors
        chord(std::string);
        chord(note, type);
        //comparison operator, to use chord as key to a map
        bool operator<(const chord&) const;
        //accessors
        note        get_root() const {return my_root;};
        type        get_type() const {return my_type;};
        std::string name(bool sharp=true) const;
        noteset get_notes() const;
        //string that describes valid formats for a chord
        static const std::string HelpString;
        noteset my_notes;
        static const boost::regex chord_re;
            protected:
        note my_root; //lousy names
        type my_type;
        //constructor helpers, only called once
        static type create_type(boost::smatch&); //lots of nasty switching here.
        void fill_noteset(note root, type t); //operates on the member noteset
    };
}//namespace music

Implementation of operator<'s:
using namespace music;

//comparison operator
bool chord::operator<(const chord& c) const{
    //see if the roots can be compared
    if(my_root < c.get_root()){//notes are stored as numbers: A=1, G#=12
        return true;
    }
    if(my_type < c.get_type()){
        return true;
    }
    return false;
}

...

bool chord::type::operator<(const chord::type& other) const{
    //compare middle note position
    if(middle_note < other.middle_note){
        return true;
    }
    //compare type bits (how come std::bitset doesn't have operator< ?
    for(int i=0; i<4; i++){//!!!CAUTION: magic number alert, not guaranteed to stay at 4
        if(type_bits[i]<other.type_bits[i]){
            return true;
        }
    }
    return false;
}


As you can see, these are mostly just hacks, to support use as keys in std::map. What's going on?? [Edited by - theOcelot on December 4, 2008 5:37:59 PM]

Share this post


Link to post
Share on other sites
One thing that you must make sure when defining operator< is that whenever a < b then b < a cannot be simultaneously true, otherwise the operator doesn't define a "strict weak ordering" and is useless for the map, sorting routines etc.

All in all the operator< for chord seems to be:


return my_root < c.get_root() || my_type < c.get_type();


Is it possible that the first chords my_root is smaller, but the second chord's my_type is larger, in which case operator< would return true both for a < b and b < a.

In general, if you want the comparison to be based on two variables, you need to do something similar to what std::pair::operator< does (perhaps you could use a std::pair internally to get the comparison for free?):


return left.a < right.a || (left.a == right.a && left.b < right.b);


Edit:
The second comparison function seems to suffer from the same problem.


//compare type bits (how come std::bitset doesn't have operator< ?


Yeah, std::bitset seems to be a bit lacking. I have written one program that needed a lot of bit-fiddling and tried to use bitset, but it seemed to lack certain very basic functionality, and as count was the only useful thing that it provided for me I settled for regular unsigned's and wrote the count function myself. (However, it might be more useful if you need bitsets larger than simple integer types can hold.)

However, one way to compare bitsets is to compare a.to_ulong() < b.to_ulong() (might throw if the bitset is too large to be represented by unsigned long, in which case there is also to_string().

[Edited by - visitor on December 4, 2008 3:39:19 PM]

Share this post


Link to post
Share on other sites
Yes...

I feel dumb now. I think the idea for chord::operator< was to only check to check the type only if the roots were equal, but I hadn't thought it through that that clearly until you showed me what I actually did. I added a check for c.get_root() < my_root, and it seems to be working.

*sigh*

Share this post


Link to post
Share on other sites

This topic is 3296 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this