C++ Key Value Relationship

Question

I want to store the combination of X, Y and distance in a data structure. where X and Y are integers. distance is the distance between X and Y.

Which would be the best data structure to use in c++ so that I can later find if the combination is present in the list?

He means key, value relationships. I have a pending title edit as such — Christian Stewart, Feb 28 '13 at 23:18
how big is your list? how do you access it a lot? you can use a class/struct with the 2 int/float/double in a vector. a map will be faster to look for.a hash map even faster however if you don't have many points to iterate just use vector. so please tell us a little more details — Gilad, Feb 28 '13 at 23:21
BAsically what I am trying to do is calculate the distance between 2 points and store the points and distance in a data structure. Later find if the points are already present in that data structure if so then return the distance or else calculate the distance between the points and insert into the data structure — Angel, Feb 28 '13 at 23:23
The main reason i am asking for a effective Data structure is because i have large set of points. — Angel, Feb 28 '13 at 23:24
You may find this useful: http://stackoverflow.com/a/471461/78845 — johnsyweb, Feb 28 '13 at 23:28
@Angel add the details in the comments into the question. A more detailed question renders more exact answers. I'll delete mine, it was not relevant. — daramarak, Mar 01 '13 at 00:07
I realise the title has been edited once already. But I find the current title overly general, to the point of near-uselessness. How about: _C++ Optimal data structure for memoization of simple function_? That's what you are looking for, no? — jogojapan, Mar 01 '13 at 12:53
possible duplicate of [In which scenario do I use a particular STL Container?](http://stackoverflow.com/questions/471432/in-which-scenario-do-i-use-a-particular-stl-container) — PearsonArtPhoto, Mar 01 '13 at 13:50

Jerry Coffin · Answer 1 · 2013-02-28T23:34:17.127

You probably want to use std::set for the storage. You'll want/need a comparison function that takes the coordinates into account (the distance is directly derived from them, so you don't really need to compare it).

Edit: based on the comment that a large number of points is involved, an std::unordered_set may be a better choice. It'll probably be more work, but allows both insertion and searching with complexity you normally expect to be constant.

score 2 · Answer 2 · answered Feb 28 '13 at 23:19

2

Make that std::unordered_set with an appropriate hash.

answered Feb 28 '13 at 23:19

user1095108

14,119
9
58
116

Daniel Frey · Answer 3 · 2013-03-01T00:02:02.353

1

EDIT: The question changed, latitude/longitude are gone and some things have been clarified. I'm starting over:

Your question seems to imply that the distance calculation is not just a simple std::abs(X-Y), as it would make no sense at all to store the result to speed things up. I'll assume that you have an expensive function that calculates it, let's say:

int distance( int X, int Y ) { /* heavy stuff */ }

Now you need to decide whether or not to call it or if you have already done that and you can reuse the result. You need a container to store the results and a function to use it:

typedef std::pair< int, int > key;
std::map< key, int > values;

int quick_distance( int X, int Y )
{
  const auto k = key(X,Y);
  const auto it = values.find(k);
  if( it != values.end() ) return it->second;
  const auto d = distance(X,Y);
  values[k] = d;
  return d;
}

edited Mar 01 '13 at 00:02

answered Feb 28 '13 at 23:25

Daniel Frey

55,810
13
122
180

Basically what I am trying to do is calculate the distance between 2 points and store the points and distance in a data structure. Later find if the points are already present in that data structure if so then return the distance or else calculate the distance between the points and insert into the data structure. – Angel Feb 28 '13 at 23:45
Yes This is exactly what i was trying to do. I have a complex function which does distance calculation and I want to reuse the distance value instead of redoing it every time. Thank you :) It helped a lot – Angel Mar 01 '13 at 00:07
values[k] = d; is nothing but values.insert(k, d); right ? – Angel Mar 01 '13 at 00:21
No, that would be `values.insert(std::make_pair(k,d))`. – Daniel Frey Mar 01 '13 at 00:24

score 0 · Answer 4 · edited May 23 '17 at 12:21

Take a look at std::pair, they was created for this purpose, and you could use improvements in containers associated with this kind of data structures.

what-is-stdpair

Time ago I wrote something using data pairs to graphics serial data from microcontrolers, check at https://github.com/jpcordovae/GLRealTimeGraphics/blob/master/DataPair.hpp, maybe it will help you.

Regards !

JP Cordova E.

C++ Key Value Relationship

4 Answers4