4

I have a 3 component vector struct called Vector3 with 3 int representing X, Y and Z. For each 3D point (I have more or less 200-300 different 3D points) I have a string.

What I want to do is to have a data structure that checks if there is a string for that location. I wanted to use a std::map and I made this code without good results:

The error it has is that It just runs the else part once, and keeps returning the same string over and over.

My Vector3 class is the one in Ogre3D: http://www.ogre3d.org/docs/api/html/classOgre_1_1Vector3.html

String WorldGenerator::createPlatformBorder(Vector3 size)
{
    static std::map<Vector3, String> generatedBorders;

    if (generatedBorders.find(size) != generatedBorders.end())
    {
        return generatedBorders[size];
    }
    else
    {
        String blockName = requestNewPlatformBorderName();
        generatedBorders.insert(std::pair<Vector3, String>(size, blockName));
        // some logic
        return blockName;
    }
}

Could you help me out, please?

Note that the function requestNewPlatformBorderName() works perfectly fine, so the bug isn't there. Here is the code for it:

String requestNewPlatformBorderName()
{
    static int counter = 0;
    return StringConverter::toString(++counter) + "-platform-border";
}
hyde
  • 60,639
  • 21
  • 115
  • 176
Pacha
  • 1,438
  • 3
  • 23
  • 46
  • 3
    What is the `operator <` of Vector3? – Neil Kirk Aug 27 '13 at 04:52
  • 5
    What does "without good results" mean? Compiler error? Crash? Wrong results? – nneonneo Aug 27 '13 at 04:52
  • 2
    Need to see the code for Vector3, especially the operator< (if any). – john Aug 27 '13 at 04:54
  • 1
    take a look at http://stackoverflow.com/questions/1102392/stl-maps-with-user-defined-objects – Karthik T Aug 27 '13 at 04:55
  • @nneonneo Oh sorry. It doesn't work properly and it always returns the same string (it just runs the second part of the `if` clause and then returns the same string over and over). Going to edit it now. – Pacha Aug 27 '13 at 04:55
  • 2
    You may also find it useful to save the iterator returned from `generatedBorders.find(size)` call, check that against `generatedBorders.end()` and if not equal, return `it->second`. No sense in doing the lookup *twice*. Especially if that `Vector3::operator<()` operator is what I think it is. – WhozCraig Aug 27 '13 at 04:57
  • What's `operator==` for `Vector3`? Are you certain you are passing different `size` each time? – nneonneo Aug 27 '13 at 04:57
  • What is vector3 - is it made up of floats/doubles or integers? If it is made up of floats/doubles, you will need an equality operator, probably with some tolerances. – cup Aug 27 '13 at 04:58
  • @NeilKirk http://www.ogre3d.org/docs/api/html/classOgre_1_1Vector3.html – Pacha Aug 27 '13 at 04:58
  • @nneonneo Yes, I put some breakpoints and I am sending different `Vector3`s each time – Pacha Aug 27 '13 at 04:58
  • Oh dear, `<` is a partial order. I wonder if that invalidates `map` (you can have two `Vector3`s `u,v` such that `!(uv)`) – nneonneo Aug 27 '13 at 05:00
  • And fix your typos for future viewers (ex: `std::pair` um.. `String` ?? – WhozCraig Aug 27 '13 at 05:01
  • @WhozCraig I don't see any typos there – Pacha Aug 27 '13 at 05:02
  • 1
    Your question title mentions a "hash map", but I don't see anything like that in the question body. Is there a mistake somewhere? – ruakh Aug 27 '13 at 05:03
  • @Pacha you don't see `` in your pair-insertion, and `` in your map declaration? (look at the case). – WhozCraig Aug 27 '13 at 05:05
  • 1
    `std::map` is not a hash map. If you want a hash map (and you probably *should*, for best overall performance, unless there's a specific reason not to), use `std::unordered_map`. – hyde Aug 27 '13 at 05:32

2 Answers2

5

You have two alternatives:

  1. Define the < operator for class Vector3, or
  2. Create a function that compares 2 Vector3s and specify it when declaring the map. This one is particularly useful when there is no natural (intuitive, common, default, etc) ordering for the class acting as key, or when you want to order/map by a criterion different than it. IMHO, the first is the case in your example, so I would be inclined for it.

1. < operator

bool operator < (const Vector3 &that) const {
    if( this.x != that.x )
        return this.x < that.x ;
    else if( this.y != that.y )
        return this.y < that.y ;
    else if( this.z != that.z )
        return this.z < that.z ;
    else
        return false ;
}

2. Comparison function

class Vector3Comparator {
    public:
    bool operator () (const Vector3 &a,const Vector3 &b) const {
        if( a.x != b.x )
            return a.x < b.x ;
        else if( a.y != b.y )
            return a.y < b.y ;
        else if( a.z != b.z )
            return a.z < b.z ;
        else
            return false ;
    }
}
...
static std::map<Vector3,string,Vector3Comparator> generatedBorders;
Mario Rossi
  • 7,651
  • 27
  • 37
2

The Vector3 operator< is not suitable for use in a map. You need to define your own custom version.

struct Vector3Cmp
{
    bool operator()(const Vector3& v1, const Vector3& v2)
    {
        if (v1.x < v2.x)
            return true;
        if (v1.x > v2.x)
            return false;
        if (v1.y < v2.y)
            return true;
        if (v1.y > v2.y)
            return false;
        if (v1.z < v2.z)
            return true;
        if (v1.z > v2.z)
            return false;
        return false;
    }
};

static std::map<Vector3, string, Vector3Cmp> generatedBorders;
john
  • 85,011
  • 4
  • 57
  • 81
  • +1 I just read that doc as well, Yuck. Two vectors with even a single value greater *and* likewise at least one less than all content in the other guarantees breaking strict weak ordering. Nice catch. – WhozCraig Aug 27 '13 at 05:02
  • @WhozCraig: does it actually break strict weak ordering? It's a *weak* ordering, not a strong ordering; it doesn't have to order all elements. – nneonneo Aug 27 '13 at 05:04
  • The definition at [sgi.com](http://www.sgi.com/tech/stl/StrictWeakOrdering.html) suggests that the Vector3 `<` is perfectly OK for use in a map. @john: mind elaborating why the operator is not suitable? – nneonneo Aug 27 '13 at 05:05
  • 1
    @john: Might I suggest `std::lexicographical_compare` ? :) – Billy ONeal Aug 27 '13 at 05:06
  • @nneonneo Because it breaks strict weak ordering, it's perfectly possible that a < b is false and b < a is false. – john Aug 27 '13 at 05:07
  • 1
    But that's OK! It just means that `a` and `b` are equivalent, but the doc explicitly says that this doesn't have to imply equality. – nneonneo Aug 27 '13 at 05:07
  • @nneonneo You're right I think, but clearly it's not what the OP was expecting. – john Aug 27 '13 at 05:12
  • @BillyONeal Vector3 doen't appear to have any iterators so I'm not sure how std::lexicographical_compare would work. – john Aug 27 '13 at 05:13
  • @john: Well, if `operator<` doesn't break strict weak ordering, then `std::map` should have functioned properly. It did not. Perhaps there is some other problem... – nneonneo Aug 27 '13 at 05:13
  • @nneonneo ok. perhaps I misunderstood as well. according to the docs on the website, "Returns true if the vector's scalar components are ***all*** greater that the ones of the vector it is compared against." (emphasis added). Thus (1,3,5) and (2,4,6) would return false for `(lhs < rhs)` and `(rhs < lhs))`. But `std::map` will require sow, and therefore if (!(lhs < rhs) && !(rhs < lhs)) they are deemed *equal*. (or please tell me where I'm wrong, because if I am, I truly need to know. I will totally admit if I missed something. – WhozCraig Aug 27 '13 at 05:14
  • @WhozCraig: According to the definition of Strict Weak Ordering, they are deemed **equivalent**. This doesn't imply equality. The `map` still has to check for equality, I think... – nneonneo Aug 27 '13 at 05:14
  • @nneonneo The OP says that it always returned the same string. He doesn't say what values he was using, but presumeably he used values where a < b, b < a **and** a != b., which not surprisingly was not what he expected. The defined operator< may be OK in a strict sense (no pun intended) but it's not very useful and not compatible with operator== – john Aug 27 '13 at 05:16
  • @nneonneo Ok. then we're definitely not on the same page because, barring optimizations (some are a little less cluttered than I presented above) that is *exactly* how a map deems equality. if both orders of `operator <()` return false, they're considered the same key, and thus map to the same result. `std::set<>` does the same thing. Maybe i'm lost in some implementation but all the ones I've seen do that for `std::map<>`. I'd have to check the std for absolute clarity. – WhozCraig Aug 27 '13 at 05:16
  • Bleh. The SGI documentation is quite convoluted in this way (I thought looking through that would be the best way to figure this out). Parts of it make it sound as if `map` could admit multiple "equivalent but not equal" keys, which misled me. Of course, since `map` only takes an ordering comparison, not an equality comparison, that would be impossible. – nneonneo Aug 27 '13 at 05:26
  • @nneonneo I totally agree. Its like reading doxygen skeletons. I think you're right on the term `equivalent`, since the standard is pretty picky about wording (25.4,p7) and to say they're the "same" key would imply they're the actual same *object*, which would obviously be an incorrect interpretation (though they might be=P). I think you're right on that term, its just how a map/set *uses* it to establish identity. – WhozCraig Aug 27 '13 at 05:30
  • @Whoz: In a language with value semantics everywhere saying the "same object" is almost always wrong. – Billy ONeal Aug 27 '13 at 21:29
  • @BillyONeal I completely agree. – WhozCraig Aug 27 '13 at 22:03