58

I have a std::map that I'm using to store values for x and y coordinates. My data is very sparse, so I don't want to use arrays or vectors, which would result in a massive waste of memory. My data ranges from -250000 to 250000, but I'll only have a few thousand points at the most.

Currently I'm creating a std::string with the two coordinates (i.e. "12x45") and using it as a key. This doesn't seem like the best way to do it.

My other thoughts were to use an int64 and shove the two int32s into it and use it as a key.

Or to use a class with the two coordinates. What are the requirements on a class that is to be used as the key?

What is the best way to do this? I'd rather not use a map of maps.

2
  • You could easily and legitimately stuff two longs into an _int64, or as in my answer below, a serial number, PID, and NodeId. Since MAX_PID is (1<<22) on Linux, this actually leaves 64 - (32 + 22) left for the NodeId, which is 10 bits, holding any value up to (1<<10) IE:1024
    – user1899861
    Sep 9, 2013 at 5:59
  • Assuming You do not want to iterate the map in some specific order, use a hash map like std::unordered_map. Much more efficient especially when you have that many values.
    – hyde
    Sep 9, 2013 at 7:16

10 Answers 10

142
+50

Use std::pair<int32,int32> for the key:

std::map<std::pair<int,int>, int> myMap;

myMap[std::make_pair(10,20)] = 25;
std::cout << myMap[std::make_pair(10,20)] << std::endl;
5
  • 5
    a pair works but is generic. Might be a good idea to define a custom type that expresses what the pair really means, cartesian coordinates or whatever.
    – bames53
    Jul 10, 2013 at 17:20
  • 4
    @bames53 The main problem with that is that you must then implement a comparison operator for the new type, which may not make sense if all you want to ensure is uniqueness. Feb 10, 2016 at 21:27
  • Didn't even know until now that there are overloads of the comparison operators for std::pair.
    – zett42
    Mar 6, 2017 at 1:50
  • 1
    @KyleStrand how is this a problem? Uniqueness is not violated by a comparison operator. Besides, you might only define a comparison operator as third argument for map, not for the type itself. Speaking code and therefore code clarity definitely supports bames53's suggestion
    – IceFire
    Mar 20, 2019 at 8:08
  • @IceFire I think what I was trying to say was that you wouldn't want to define an operator that implies a logical ordering on a type that isn't supposed to support the semantic concept of ordering, because it could be misused. But obviously using pair instead doesn't actually avoid that problem. I think your suggestion of providing the operator as a map argument is the correct solution. Mar 20, 2019 at 14:18
34

I usually solve this kind of problem like this:

struct Point {
    int x;
    int y;
};

inline bool operator<(const Point& p1, const Point& p2) {
    if (p1.x != p2.x) {
        return p1.x < p2.x;
    } else {
        return p1.y < p2.y;
    }
}
7
  • 11
    This is explicit, which is good. Just note this is the same as typedef std::pair<int, int> Point;
    – GManNickG
    Jul 11, 2009 at 0:28
  • 13
    Heh, until now I didn't know that std::pair has operator< defined. Love SO! Jul 11, 2009 at 0:33
  • 5
    @GManNickG except the interface of x and y which is first and second for a std::pair.
    – rubenvb
    Jul 16, 2013 at 19:51
  • 3
    This is very good because can be used also for keys containing more than 2 fields.
    – bluish
    Jul 20, 2016 at 9:55
  • 1
    You can also add a comparator functor as a template argument of map: std::map<Point, std::string, PointComp> mapping;
    – orzechow
    Mar 8, 2018 at 10:11
7

Boost has a map container that uses one or more indices.

Multi Index Map

1
  • It can be achieved by using boost's tuples as well.
    – Frizi
    Aug 6, 2012 at 23:29
5

What are the requirements on a class that is to be used as the key?

The map needs to be able to tell whether one key's value is less than another key's value: by default this means that (key1 < key2) must be a valid boolean expression, i.e. that the key type should implement the 'less than' operator.

The map template also implements an overloaded constructor which lets you pass-in a reference to a function object of type key_compare, which can implement the comparison operator: so that alternatively the comparison can be implemented as a method of this external function object, instead of needing to be baked in to whatever type your key is of.

1
  • Another requirement is that the key must be constant and cannot change
    – Emiliano
    May 23, 2013 at 10:09
1

This will stuff multiple integer keys into a large integer, in this case, an _int64. It compares as an _int64, AKA long long (The ugliest type declaration ever. short short short short, would only be slightly less elegant. 10 years ago it was called vlong. Much better. So much for "progress"), so no comparison function is needed.

#define ULNG  unsigned long
#define BYTE  unsigned char
#define LLNG  long long 
#define ULLNG unsigned long long

// --------------------------------------------------------------------------
ULLNG PackGUID(ULNG SN,  ULNG PID, BYTE NodeId) {
    ULLNG CompKey=0;

    PID = (PID << 8) + NodeId;
    CompKey = ((ULLNG)CallSN << 32) + PID;

    return CompKey;
}

Having provided this answer, I doubt this is going to work for you, as you need two separate and distinct keys to navigate with in 2 dimensions, X and Y.

On the other hand, if you already have the XY coordinate, and just want to associate a value with that key, then this works spectacularly, because an _int64 compare takes the same time as any other integer compare on Intel X86 chips - 1 clock.

In this case, the compare is 3X as fast on this synthetic key, vs a triple compound key.

If using this to create a sparsely populated spreadsheet, I would RX using 2 distinct trees, one nested inside the other. Make the Y dimension "the boss", and search Y space first to resolution before proceeding to the X dimension. Spreadsheets are taller than they are wide, and you always want the 1st dimension in any compound key to have the largest number of unique values.

This arrangement would create a map for the Y dimension that would have a map for the X dimension as it's data. When you get to a leaf in the Y dimension, you start searching it's X dimension for the column in the spreadsheet.

If you want to create a very powerful spreadsheet system, add a Z dimension in the same way, and use that for, as an example, organizational units. This is the basis for a very powerful budgeting/forecasting/accounting system, one which allows admin units to have lots of gory detail accounts to track admin expenses and such, and not have those accounts take up space for line units which have their own kinds of detail to track.

1
  • 2
    I believe stuffing two longs into an _int64, provided the high long is Y, and low long is X, will search Y space first, and then X space, as all values with the same high long (same Y value) will be equal, leaving the low long (X space) to break the tie. Sep 12, 2013 at 22:33
1

I think for your use case, std::pair, as suggested in David Norman's answer, is the best solution. However, since C++11 you can also use std::tuple. Tuples are useful if you have more than two keys, for example if you have 3D coordinates (i.e. x, y, and z). Then you don't have to nest pairs or define a comparator for a struct. But for your specific use case, the code could be written as follows:

int main() {
    using tup_t = std::tuple<int, int>;
    std::map<tup_t, int> m;

    m[std::make_tuple(78, 26)] = 476;
    tup_t t = { 12, 45 }; m[t] = 102;

    for (auto const &kv : m)
        std::cout << "{ " << std::get<0>(kv.first) << ", "
                          << std::get<1>(kv.first) << " } => " << kv.second << std::endl;
    return 0;
}

Output:

{ 12, 45 } => 102
{ 78, 26 } => 476

Note: Since C++17 working with tuples has become easier, espcially if you want to access multiple elements simultaneously. For example, if you use structured binding, you can print the tuple as follows:

for (auto const &[k, v] : m) {
    auto [x, y] = k;
    std::cout << "{ " << x << ", " << y << " } => " << v << std::endl;
}

Code on Coliru

0

Use std::pair. Better even use QHash<QPair<int,int>,int> if you have many of such mappings.

-1

Hope you will find it useful:

map<int, map<int, int>> troyka = { {4, {{5,6}} } };
troyka[4][5] = 7;
1
  • 1
    OP says he'd rather not use a map of maps, so this answer is not very likely to help. In addition, some explanations of the code could be helpful for others to understand your solution. Sorry if I'm complaining too much, but you have answered a very old question from 2009 that already has an answer with many upvotes. So it's very unlikely that your answer will provide something new or even better than the accepted answer.
    – zett42
    Mar 6, 2017 at 1:48
-1

An alternative for the top result that is slightly less performant but allows for easier indexing

std::map<int, std::map<int,int>> myMap;

myMap[10][20] = 25;
std::cout << myMap[10][20] << std::endl;
1
  • The OP specifically mentioned they didn't want to use a map of maps.
    – Sneftel
    Mar 15, 2021 at 9:56
-2

First and foremost, ditch the string and use 2 ints, which you may well have done by now. Kudos for figuring out that a tree is the best way to implement a sparse matrix. Usually a magnet for bad implementations it seems.

FYI, a triple compound key works too, and I assume a pair of pairs as well.

It makes for some ugly sub-scripting though, so a little macro magic will make your life easier. I left this one general purpose, but type-casting the arguments in the macro is a good idea if you create macros for specific maps. The TresKey12 is tested and running fine. QuadKeys should also work.

NOTE: As long as your key parts are basic data types you DON'T need to write anything more. AKA, no need to fret about comparison functions. The STL has you covered. Just code it up and let it rip.

using namespace std;    // save some typing
#define DosKeys(x,y)      std::make_pair(std::make_pair(x,y))
#define TresKeys12(x,y,z) std::make_pair(x,std::make_pair(y,z))
#define TresKeys21(x,y,z) std::make_pair(std::make_pair(x,y),z))

#define QuadKeys(w,x,y,z) std::make_pair(std::make_pair(w,x),std::make_pair(y,z))


map<pair<INT, pair<ULLNG, ULLNG>>, pIC_MESSAGE> MapMe;
MapMe[TresKey12(Part1, Part2, Part3)] = new fooObject;

If someone wants to impress me, show me how to make a compare operator for TresKeys that doesn't rely on nesting pairs so I can use a single struct with 3 members and use a comparison function.

PS: TresKey12 gave me problems with a map declared as pair,z as it makes x,pair, and those two don't play nice. Not a problem for DosKeys, or QuadKeys. If it's a hot summer Friday though, you may find an unexpected side-effect of typing in DosEquis ... err.. DosKeys a bunch of times, is a thirst for Mexican beer. Caveat Emptor. As Sheldon Cooper says, "What's life without whimsy?".

7
  • 6
    This is pretty ugly. Why a macro for what should be a function? And this is way too many nested pairs. To answer your question on how to solve it: struct location { int x, y, z; }; bool operator<(const location& lhs, const location& rhs) { return std::tie(lhs.x, lhs.y, lhs.z) < std::tie(rhs.x, rhs.y, rhs.z); }
    – GManNickG
    Jul 10, 2013 at 17:52
  • 2
    @GManNickG, thanks for the reply. Will give this a try and report back. Yeah, this guy'll be smiling if this works! Jul 10, 2013 at 23:58
  • @GManNickG, This doesn't quite compile. I'll futz around with it here in VS 2012 C++. Probably get it working, but if you have a minute to spare, maybe post something that's compiling? TVMIA Jul 11, 2013 at 16:20
  • 1
    Works for me: coliru.stacked-crooked.com/…, as well as in VS2012.
    – GManNickG
    Jul 11, 2013 at 16:51
  • 1
    @GManNickG, color me impressed, and thanks for going the extra mile here. Up against a lean agile slice here, so appreciate the help.
    – user1899861
    Jul 12, 2013 at 4:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.