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

Discussion in 'C++' started by James Kanze, Dec 21, 2008.

  1. James Kanze

    James Kanze Guest

    On Dec 20, 3:45 am, "(2b|!2b)==?" <> wrote:
    > I have written a class template to store manage/raw pointers,
    > I want to store pointers to an obects, using a key. I find
    > that find() is not working (after the first insert) - i.e.
    > once the first item is inserted in the map, any key passed to
    > the find() method will return the first item.


    > 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???


    > The code follows below:


    > PointerMap.h
    > =============


    > #pragma once


    > #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)
    > {
    > 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));
    > }


    This is (generally) inconsistent with your erase function.
    Personally, I question the utility of such a class to begin
    with; I've never had a case where a map should delete a pointer
    when it is removed from the map. But if it's going to make
    sense, then either the map has to also allocate the memory, or
    there must be a clear transfer of responsibility, for example by
    insert taking an std::auto_ptr. And some very, very rigorous
    documentation, to the effect that erase may invalidate pointers
    in user code.

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


    This doesn't make sense. What if T isn't comparable with an
    integral type (the usual case when map is being used)?

    > else
    > return m_map[idx] ;


    And this isn't legal: you can't invoke [] on a constant map.

    > }


    If you want to support [] on a constant map (which makes a lot
    of sense if the return value is a pointer), then something like:

    T2* operator[]( T1 idx ) cosnt
    // ^^ no real point in the const here...
    {
    const_iterator result = m_map.find( idx ) ;
    return result == m_map.end()
    ? NULL
    : result->second ;
    }

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


    Same comment as above.

    > else
    > {
    > T2*& ptr = m_map[idx] ;


    Note that this inserts an element, mapping to a null pointer, if
    one isn't already present. You may prefer doing something like
    I suggested for the const [], to avoid this.

    > if (ptr)
    > {
    > delete ptr ;
    > ptr = 0 ;
    > }
    > return m_map[idx] ;


    In otherwords, regardless of the index, you return a null
    pointer:). And if there was something there, you delete it.

    > }
    > }


    I think you have to decide on one policy for [], and stick to
    it. The standard uses the policy that if the element isn't
    there, it gets inserted, with the mapped to entry being
    constructed with a default constructor (for pointers, set to
    null). That can be a useful policy in some cases, but not
    necessarily everywhere. And it introduces two important
    restrictions: you can't use [] on a const map (since it may
    modify the map), and if you use [], the instantiation type must
    support default construction.

    Another frequent policy is to provide a contains(key) function,
    and make it a pre-condition for [].

    Or you can return some sort of "fallible" object, with a status
    which indicates whether the object was found or not. In the
    case of a map, the simplest way to do this is to return a
    pointer to an element, rather than the element itself, returning
    a null pointer if the element didn't exist. If the map
    maintains an invariant which excludes some specific values (e.g.
    a pointer map which doesn't allow null pointer entries), then
    you can return one of the excluded values (a null pointer).
    Otherwise, you can use a true Fallible class (but in this case,
    I find the pointer to the element a better solution---the
    Fallible class is mainly useful when you have to return a
    value.)

    > 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()
    > {
    > }


    > 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;
    > }


    > 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 doesn't establish a partial order. For a partial order,
    a<b || b<a is always true, a<b && b<a implies equality, and (a<b
    && b<c) == a<c. Try the last with a==(1,2...), b==(2,1...) and
    c==(0,2...): a<b, b<c and c<a.

    The canonlical pseudo-code for a comparison operator over n
    fields would be something like:

    bool
    lessThan<n>( Type const& lhs, Type const& rhs )
    {
    return lhs.field<n> < rhs.field<n>
    || (! rhs.field<n> < lhs.field<n>
    && lessThan<n+1>( lhs, rhs ) ;
    // except when n is the last field, of
    // course.
    }

    bool
    operator<( Type const& lhs, Type const& rhs )
    {
    return lessThan<0>( lhs, rhs ) ;
    }

    (Note that this is pseudo-code, and the <n> notation shouldn't
    be meant to imply templates. Although with the upcoming
    standard, and variadic template arguments, it is probably
    possible to implement such a template. Otherwise, you actually
    have to manually implement all of the lessThan<n> functions.)

    If your type supports ==, as well as <, then it is sometimes
    preferable to replace the (! rhs.field<n> < lhs.field<n>) with
    rhs.field<n> != lhs.field<n>. For a lot of types, it may even
    be interesting to provide a single compare function, which
    returns a value <, == or > 0, depending on the results of the
    comparison. In that case, you get:

    bool
    lessThan<n>( Type const& lhs, Type const& rhs )
    {
    int result
    = compare( lhs.field<n>, rhs.field<n> ) ;
    return result < 0
    || (result == 0 && lessThan<n+1>( lhs, rhs )) ;
    }

    In a very real sense, think of it in the same way you would
    compare strings, character by character, except that the fields
    are your 'characters'.

    --
    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 21, 2008
    #1
    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:
    997
    Howard Hinnant
    Apr 20, 2005
  2. Replies:
    1
    Views:
    480
  3. Replies:
    1
    Views:
    456
    red floyd
    Dec 21, 2008
  4. Thomas J. Gritzan
    Replies:
    6
    Views:
    1,051
    James Kanze
    Dec 22, 2008
  5. Ricardo
    Replies:
    8
    Views:
    449
    Joe Greer
    Jul 8, 2009
Loading...

Share This Page