Learn how easy it is to sync an existing GitHub or Google Code repo to a SourceForge project! See Demo

Close

std::map equalrange returns just 1 element

2007-07-04
2013-05-13
  • Sean Zlatnik
    Sean Zlatnik
    2007-07-04

    Question- should a map really only return a single element to an equalrange query?

    Example-

    Say you have a sort that is based on three different pieces of data.  You can then equal range for just one of those pieces of data, giving some kind of null value for the other two.  By designing your sort carefully, this is easy enough to accomplish.  None of the entries in the map would have null values, just the search object.  I think this should be okay.  Yet, as best as I can tell, your map only returns the first matching element.  Am I write in saying this is a bug?

     
    • A map can only contains non equivalent values so equal_range can only return 1 element.

      Your description of the way your want to compare the values is rather suspect. You should activate _STLP_DEBUG mode, STLport will tell you if it is correctly implemented.

       
    • Sean Zlatnik
      Sean Zlatnik
      2007-07-24

      I don't think you are understanding me.  The values in the container are not equavalent to each other in the sort.  However, multiple values can be equavalent to a single value.  Example-

      class __declspec(dllexport) viewElement
      {
          objectType _type;
          Adesk::Int16 floorNumber;
          AcDbObjectId _id;
         
      public:
          viewElement(void);
          viewElement(objectType __type, int _floorNumber, AcDbObjectId __id);
          ~viewElement(void);
          objectType getType() const
          {
              return _type;
          }
          int getFloor() const
          {
              return floorNumber;
          }
          AcDbObjectId getObjectId() const
          {
              return _id;
          }
      };

      class viewElementSorter
      {
      public:

          bool operator()(const viewElement& lhs, const viewElement& rhs) const
          {
              if (lhs.getType() == nullType || rhs.getType() == nullType)
              {
                  assert((lhs.getType() == nullType && lhs.getFloor() == -1) || (rhs.getType() == nullType && rhs.getFloor() == -1));
                  return lhs.getObjectId() != rhs.getObjectId();       
              }
              else if (lhs.getType() == rhs.getType())
              {   
                  if (lhs.getFloor() == rhs.getFloor())
                  {
                      assert(lhs.getFloor() != -1 || rhs.getFloor() != -1);
                      if (lhs.getObjectId() != AcDbObjectId::kNull && rhs.getObjectId() != AcDbObjectId::kNull)
                      {
                          return lhs.getObjectId() < rhs.getObjectId();
                      }
                      else
                      {
                          assert(lhs.getObjectId() != AcDbObjectId::kNull || rhs.getObjectId() != AcDbObjectId::kNull);
                          return false;
                      }
                  }
                  else if (lhs.getFloor() != -1 && rhs.getFloor() != -1)
                  {
                      return lhs.getFloor() < rhs.getFloor();
                  }
                  else
                  {
                      assert(lhs.getFloor() != -1 || rhs.getFloor() != -1);
                      return false;
                  }
              }
              else return lhs.getType() < rhs.getType();
          }   
      };

      If you look at this code, you see it is possible- given that nullType is not a type used by any of the objects and -1 not used as the floor number for any of the objects in the container, none of the objects are equavalent to each other, but the search object can be equivalent to multiple objects.  I think this code should work with a map...

       
      • Do you see the difference between map and multimap?

         
    • Sean Zlatnik
      Sean Zlatnik
      2007-07-25

      Of course I can get most of what I want with a Multimap.  However, I really don't need the ability to have multiple values in the object that are directly equavalent to each other.  Besides, what is the point of the equalrange function if it just returns the same thing as the find function?  Truth is, I think this might be what they call a strict weak ordering, in which case what I am trying to do should be legal without having to go to a multimap.

       
      • In short: map require biunique correspondence between key and value, but you can't provide this.

        Compare it with question on interview:

        template <class _T>
        struct not_less {
          bool operator() (const _T& __x, const _T& __y) const { return !(__x < __y); }
        };

        map<int, char, not_less<int> > imap;

        Is this code ok?

         
    • Sean Zlatnik
      Sean Zlatnik
      2007-07-26

      Of course that code doesn't work.  Nevertheless, in the code I gave, items within the map don't have ObjectId::kNull as a value.  They don't have nullType as a type.  Those types are reserved for a search object.

      Is what I am doing really so difficult that you guys can't get it? 

      Let's say that I have a map with object Car.  Every car has a nonzero id, and a type (such as chevy) and the year it was made in.  Obviously entries in the map itself are all going to be unique- no car will be the same.  However, it would be nice to be able to find all the chevys, so for the search object you give it an id that doesn't exist in the map- in this case zero.  Your equal range will return all chevys.  The sort above does that.  What is wrong with that?

       
    • What you are trying to do is not difficult, it is impossible.

      The map container is based on clear mathematical definition of what is a strict weak ordering comparison, see this link to get description from original SGI STL:

      http://www.sgi.com/tech/stl/StrictWeakOrdering.html

      What you have to write is something like a < operator implementation and your viewElementSorter is far from that. Writing things like != or arbitrary 'return false' in a strict weak ordering implementation is showing that there are problems in your implementation.

      STL implementations are trying to be as efficient as possible and to do so they are using strong hypothesis like what a strict weak ordering definition is. If you want to use STL containers you have to follow the rules that are really clear.

      You can of course do something very similar to what you want. Lets say for instance that you have written a good strict weak ordering functor that order cars based on their type first then on their year and then on their id. You will be able using algos like lower_bound or upper_bound to get the begin and end iterator for all Chevy' cars or even all Checy' cars of 2000 year. Bu if you want all cars with ids between 2 values then you will have to use an other container or find it manually.

      STL containers are flexible but perhaps not flexible enough for you.