Re: Problems with std::map.insert() and std::map.find()

Discussion in 'C++' started by Thomas J. Gritzan, Dec 21, 2008.

  1. (2b|!2b)==? schrieb:
    > Additionally, once the first item has been stored, no additional items
    > can be stored - its driving me nuts, and I cant work outt why this is
    > happening. I have included both my classes (i.e class template and key
    > class here - hopefully, someone can spot what is causing things to go
    > awry). To summarize the problem - every - i.e. find() and insert() work
    > as expected, UNTIL the first item is inserted into the map - which seems
    > to suggest that somehow, the Keys are considered non-unique???


    How does find() and insert() both work "as expected" while you haven't
    inserted any items?

    > The code follows below:
    >
    > PointerMap.h
    > =============
    >
    > #pragma once


    This is non-standard. Unless you want to use this exclusively on
    compilers that support it (i.e. Visual C++), you should use a regular
    include guard here.

    > #include <string>
    > #include <map>
    > #include <stdexcept>
    >
    >
    > template<class T1, class T2>
    > class PointerMap
    > {
    > public:
    > typedef typename std::map<T1, T2*>::reference reference;
    > typedef typename std::map<T1, T2*>::const_reference const_reference;
    > typedef typename std::map<T1, T2*>::const_iterator const_iterator;
    > typedef typename std::map<T1, T2*>::iterator iterator;
    >
    > PointerMap()
    > {
    > }
    >
    > ~PointerMap()
    > {
    > clear();
    > }
    >
    > iterator begin() { return m_map.begin(); }
    > iterator end() { return m_map.end(); }
    > const_iterator begin() const { return m_map.begin(); }
    > const_iterator end() const { return m_map.end(); }
    > iterator find(T1 key) { return m_map.find(key) ; }
    > const_iterator find(T1 key) const { return m_map.find(key) ; }
    >
    >
    > iterator erase(iterator where)
    > {
    > if(where != m_map.end() && *where)
    > {
    > T*& ptr = *where;
    > delete ptr;
    > ptr = 0;
    > }
    >
    > return m_map.erase(where);
    > }
    >
    > iterator erase(iterator begin, iterator end)
    > {
    > while(begin != end)
    > {
    > T2*& ptr = begin->second ;
    > if ( ptr != 0)
    > {


    You don't need to test a pointer for NULL before deleting it. deleting
    null pointers is well defined. Same above in the other erase function.

    > delete ptr ;
    > ptr = 0;
    > }
    >
    > begin++;
    > }
    >
    > return m_map.erase(begin, end);
    > }
    >
    > void clear() { erase(begin(), end()); }
    >
    > bool empty() const { return m_map.empty(); }
    > size_t size() const { return m_map.size(); }
    >
    > void insert(T1 key, T2* val)
    > {
    > m_map.insert(std::pair<T1, T2*>(key, val));
    > }
    >
    > T2* operator[] (const T1 idx) const
    > {
    > if (idx > m_map.size())
    > throw std::logic_error("Array bounds exceeded");


    Why? m_map is not an array, it is a map. You can have a key, that is
    larger than the size(). To test if a key is in the map, use find() and
    check if it returns end().

    > else
    > return m_map[idx] ;


    This shouldn't compile. You cannot use op[] on a const map!

    > }
    >
    > T2*& operator[] (const T1 idx)
    > {
    > if (idx > m_map.size())
    > throw std::logic_error("Array bounds exceeded");


    Same as above.

    > else
    > {
    > T2*& ptr = m_map[idx] ;
    > if (ptr)
    > {
    > delete ptr ;
    > ptr = 0 ;
    > }


    Why, WHY, *Why* do you delete the pointer when you want to get it?

    > return m_map[idx] ;


    Using the returned pointer is undefined behaviour because it is null.

    > }
    > }
    >
    > private:
    > PointerMap(const PointerMap& source);
    > PointerMap& operator=(const PointerMap& source);
    >
    > std::map<T1, T2*> m_map;
    > };
    >
    >
    > RepositoryKey.h
    > ================
    >
    > class RepositoryKey
    > {
    > public:
    > RepositoryKey(const unsigned char xch, const long ic, const
    > std::string& syb, const long fq = 0):
    > m_xch(xch), m_ic(ic), m_syb(syb), m_fq(fq)
    > {
    > }
    >
    > RepositoryKey(const RepositoryKey& key):
    > m_xch(key.m_xch), m_syb(key.m_syb), m_ic(key.m_ic), m_fq(key.m_fq)
    > {
    > }
    >
    > ~RepositoryKey()
    > {
    > }


    Non needed.

    > RepositoryKey& operator=(const RepositoryKey& key)
    > {
    > if (this != &key)
    > {
    > m_xch = key.m_xch;
    > m_syb = key.m_syb;
    > m_ic = key.m_ic ;
    > m_fq = key.m_fq ;
    > }
    > return *this;
    > }


    Better to use the swap idiom here.

    > bool operator==(const RepositoryKey& key) const
    > {
    > return ( (m_xch == key.m_xch) && (m_syb == key.m_syb) &&
    > (m_ic == key.m_ic) && ((long)m_fq == (long)key.m_fq) );
    > }
    >
    > bool operator < (const RepositoryKey& key) const
    > {
    > return ( (m_xch < key.m_xch) && (m_ic < key.m_ic) && ((long)m_fq
    > < (long)key.m_fq)
    > && (_stricmp(m_syb.c_str(), key.m_syb.c_str()) < 0));
    > }


    This is not a valid op< for sorting.

    For comparing two keys, it goes like this:

    {
    if (key1 < other.key1)
    return true;
    else if (other.key1 < key1)
    return false;
    else
    return key2 < other.key2;
    }

    > unsigned char Id() const { return m_xch; }
    > long Ic() const { return m_ic; }
    > std::string Symbol() const { return m_syb; }
    > long Freq() const { return m_fq ; }
    >
    > private:
    > unsigned char m_xch ;
    > long m_ic ;
    > std::string m_syb ;
    > long m_fq;
    > };


    You should also provide some code that shows how you use these classes.

    --
    Thomas
     
    Thomas J. Gritzan, Dec 21, 2008
    #1
    1. Advertising

  2. (2b|!2b)==? schrieb:
    > Thomas J. Gritzan wrote:
    >>> T2* operator[] (const T1 idx) const
    >>> {
    >>> if (idx > m_map.size())
    >>> throw std::logic_error("Array bounds exceeded");

    >>
    >> Why? m_map is not an array, it is a map. You can have a key, that is
    >> larger than the size(). To test if a key is in the map, use find() and
    >> check if it returns end().
    >>
    >>> else
    >>> return m_map[idx] ;

    >>
    >> This shouldn't compile. You cannot use op[] on a const map!

    >
    > Hmm, it does compile though, on VS2005... care to explain why it
    > shouldn't compile?


    It compiles, because you don't use this function yet. Template functions
    (or member functions of template classes) are fully error checked only
    when used.

    It won't compile when used, because op[] is non-const in a std::map (it
    modifies the map; the key is inserted if it is not found), but m_map is
    const in this const member function.

    >>> RepositoryKey& operator=(const RepositoryKey& key) {
    >>> if (this != &key)
    >>> {
    >>> m_xch = key.m_xch;
    >>> m_syb = key.m_syb;
    >>> m_ic = key.m_ic ;
    >>> m_fq = key.m_fq ;
    >>> }
    >>> return *this;
    >>> }

    >>
    >> Better to use the swap idiom here.


    Better, because it makes the operator= exception safe.

    --
    Thomas
     
    Thomas J. Gritzan, Dec 21, 2008
    #2
    1. Advertising

  3. (2b|!2b)==? schrieb:
    > Thomas J. Gritzan wrote:
    >
    >>> bool operator < (const RepositoryKey& key) const
    >>> {
    >>> return ( (m_xch < key.m_xch) && (m_ic < key.m_ic) && ((long)m_fq
    >>> < (long)key.m_fq)
    >>> && (_stricmp(m_syb.c_str(), key.m_syb.c_str()) < 0));
    >>> }

    >>
    >> This is not a valid op< for sorting.
    >>
    >> For comparing two keys, it goes like this:
    >>
    >> {
    >> if (key1 < other.key1)
    >> return true;
    >> else if (other.key1 < key1)
    >> return false;
    >> else
    >> return key2 < other.key2;
    >> }
    >>

    >
    > Not following the logic here - why is there key2 and other.key2, I
    > thought we are comparing key1 and other.key1 - could you please explain
    > how I can rewrite my op< to implement the logic above?


    The routine is for comparing two keys per object. You have four keys
    (m_xch, m_ic, m_fq and m_syb).

    Lets see how a op< look like, if RepositoryKey would contain only one key:

    bool operator< (const RepositoryKey& other) const
    {
    return key1 < other.key1;
    }

    Now for two keys:

    bool operator< (const RepositoryKey& other) const
    {
    if (key1 < other.key1)
    return true;
    else if (other.key1 < key1)
    return false;
    return key2 < other.key2;
    }

    Three keys:

    bool operator< (const RepositoryKey& other) const
    {
    if (key1 < other.key1)
    return true;
    else if (other.key1 < key1)
    return false;
    {
    if (key2 < other.key2)
    return true;
    else if (other.key2 < key2)
    return false;
    return key3 < other.key3;
    }
    }

    Four keys:

    Your homework. :)
    It's like comparing two keys in a dictionary.

    --
    Thomas
     
    Thomas J. Gritzan, Dec 21, 2008
    #3
  4. (2b|!2b)==? schrieb:
    > Thomas J. Gritzan wrote:
    >
    >>>>> RepositoryKey& operator=(const RepositoryKey& key) {
    >>>>> if (this != &key)
    >>>>> {
    >>>>> m_xch = key.m_xch;
    >>>>> m_syb = key.m_syb;
    >>>>> m_ic = key.m_ic ;
    >>>>> m_fq = key.m_fq ;
    >>>>> }
    >>>>> return *this;
    >>>>> }
    >>>> Better to use the swap idiom here.

    >>
    >> Better, because it makes the operator= exception safe.
    >>

    >
    > Thomas, could you explain how to use the swap idiom here?. I tried using
    > std::swap, and even overloaded (i.e. provided my own swap implementation
    > - but I got compliation errors (I have since reverted the code back to
    > the simple field by field swap, so cant remember/post the compilation
    > errors)


    You know Google, don't you?

    RepositoryKey& operator=(const RepositoryKey& other)
    {
    RepositoryKey temp(other); // copy to temporary; might throw
    swap(temp); // no-throw guarantee
    return *this;
    } // temp destructs old contents

    In the copy assignment operator, the source object is copied to a
    temporary, which might throw, but the assigned object is left untouched.
    After the copy has been made, the contents are exchanged into the
    assigned object. The temporary now has the old contents, which will be
    destroyed at the end of the function.
    The swap member function of RepositoryKey must not throw, otherwise op=
    is not exception safe.

    void swap(RepositoryKey& other) throw()
    {
    // include header <algorihm>
    std::swap(m_xch, other.m_xch);
    std::swap(m_syb, other.m_syb);
    // swap other members...
    }

    --
    Thomas
     
    Thomas J. Gritzan, Dec 21, 2008
    #4
  5. Thomas J. Gritzan

    Guest

    On Sun, 21 Dec 2008 02:35:06 +0100, "Thomas J. Gritzan"
    <> wrote:

    >(2b|!2b)==? schrieb:
    >> Thomas J. Gritzan wrote:
    >>
    >>>> bool operator < (const RepositoryKey& key) const
    >>>> {
    >>>> return ( (m_xch < key.m_xch) && (m_ic < key.m_ic) && ((long)m_fq
    >>>> < (long)key.m_fq)
    >>>> && (_stricmp(m_syb.c_str(), key.m_syb.c_str()) < 0));
    >>>> }
    >>>
    >>> This is not a valid op< for sorting.
    >>>
    >>> For comparing two keys, it goes like this:
    >>>
    >>> {
    >>> if (key1 < other.key1)
    >>> return true;
    >>> else if (other.key1 < key1)
    >>> return false;
    >>> else
    >>> return key2 < other.key2;
    >>> }
    >>>

    >>
    >> Not following the logic here - why is there key2 and other.key2, I
    >> thought we are comparing key1 and other.key1 - could you please explain
    >> how I can rewrite my op< to implement the logic above?

    >
    >The routine is for comparing two keys per object. You have four keys
    >(m_xch, m_ic, m_fq and m_syb).
    >
    >Lets see how a op< look like, if RepositoryKey would contain only one key:
    >
    >bool operator< (const RepositoryKey& other) const
    >{
    > return key1 < other.key1;
    >}
    >
    >Now for two keys:
    >
    >bool operator< (const RepositoryKey& other) const
    >{
    > if (key1 < other.key1)
    > return true;
    > else if (other.key1 < key1)
    > return false;
    > return key2 < other.key2;
    >}
    >
    >Three keys:
    >
    >bool operator< (const RepositoryKey& other) const
    >{
    > if (key1 < other.key1)
    > return true;
    > else if (other.key1 < key1)
    > return false;
    > {
    > if (key2 < other.key2)
    > return true;
    > else if (other.key2 < key2)
    > return false;
    > return key3 < other.key3;
    > }
    >}
    >
    >Four keys:
    >
    >Your homework. :)
    >It's like comparing two keys in a dictionary.


    I'm curious as to why you don't do the following:

    bool operator< (const RepositoryKey& other) const
    {
    if ( (key1 < other.key1) &&
    (key2 < other.key2) &&
    (key3 < other.key3) &&
    (key4 < other.key4) )
    {
    return true;
    }
    else
    {
    return false;
    }
    }

    I would think that this implementation would remove many of your "if"
    statements, and basically shows you that all conditions must be true
    in order to have a match. Plus, it has the added benefit of leaving
    room for additional key matches without the convolution of adding
    additional "if" statements.

    So, is it a matter of style, or do I have some incorrect logic in this
    example?
     
    , Dec 22, 2008
    #5
  6. Thomas J. Gritzan

    Kai-Uwe Bux Guest

    wrote:
    [lexicographic order snipped]
    > I'm curious as to why you don't do the following:
    >
    > bool operator< (const RepositoryKey& other) const
    > {
    > if ( (key1 < other.key1) &&
    > (key2 < other.key2) &&
    > (key3 < other.key3) &&
    > (key4 < other.key4) )
    > {
    > return true;
    > }
    > else
    > {
    > return false;
    > }
    > }
    >
    > I would think that this implementation would remove many of your "if"
    > statements, and basically shows you that all conditions must be true
    > in order to have a match. Plus, it has the added benefit of leaving
    > room for additional key matches without the convolution of adding
    > additional "if" statements.


    Huh?

    > So, is it a matter of style,


    No, it's a matter of meaning of operator<. Your code does not implement the
    lexicographic order on a tuple.

    > or do I have some incorrect logic in this example?


    Well, in most cases, your code will _not_ do the RightThing(tm). Let's see
    that with just two keys:

    if ( ( key1 < other.key1 ) &&
    ( key2 < other.key2 ) ) {
    return true;
    }
    return false;

    We have

    (3,5) not < (5,3) and (5,3) not < (3,5)

    In particular, (3,5) and (5,3) will be considered equivalent, which is
    usually not desired.

    The dictionary order has (3,5) < (5,3).


    Best

    Kai-Uwe Bux
     
    Kai-Uwe Bux, Dec 22, 2008
    #6
  7. Thomas J. Gritzan

    James Kanze Guest

    On Dec 22, 7:25 am, wrote:
    > On Sun, 21 Dec 2008 02:35:06 +0100, "Thomas J. Gritzan"
    > <> wrote:
    > >(2b|!2b)==? schrieb:
    > >> Thomas J. Gritzan wrote:


    > I'm curious as to why you don't do the following:


    > bool operator< (const RepositoryKey& other) const
    > {
    > if ( (key1 < other.key1) &&
    > (key2 < other.key2) &&
    > (key3 < other.key3) &&
    > (key4 < other.key4) )
    > {
    > return true;
    > }
    > else
    > {
    > return false;
    > }
    >
    > }


    Just a question of style, but there's really no point in your
    if. Just return the expression.

    > I would think that this implementation would remove many of
    > your "if" statements, and basically shows you that all
    > conditions must be true in order to have a match.


    Which, of course, is wrong if you need a strict weak ordering
    (e.g. for sorting or as a key in std::set or std::map). The
    basic algorithm is easiest expressed recursively: compare the
    first key: if it is less than, return true, otherwise if it is
    greater than, return false, otherwise compare the rest of the
    keys in the same way.

    > Plus, it has the added benefit of leaving room for additional
    > key matches without the convolution of adding additional "if"
    > statements.


    IMHO, the only solution which is really readable is the recurive
    one:

    bool operator<(
    RepositoryKey const& other ) const
    {
    return key1 < other.key1
    || ( !( other.key1 < key1 && lessThan_keys2to4
    ( other ) ) ) ;
    }

    Thomas' list of if's isn't too much of a problem, either.

    > So, is it a matter of style, or do I have some incorrect logic
    > in this example?


    Some very incorrect logic.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
     
    James Kanze, Dec 22, 2008
    #7
    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. Replies:
    3
    Views:
    966
    Howard Hinnant
    Apr 20, 2005
  2. Replies:
    1
    Views:
    465
  3. Replies:
    1
    Views:
    442
    red floyd
    Dec 21, 2008
  4. James Kanze
    Replies:
    0
    Views:
    2,046
    James Kanze
    Dec 21, 2008
  5. Ricardo
    Replies:
    8
    Views:
    438
    Joe Greer
    Jul 8, 2009
Loading...

Share This Page