2

Let us say that I have a 2D matrix, given by vector<vector<double>> matrix, and that matrix has already been initialized to have R rows and C columns.

There is also a list-of-coordinates (made up of say, N (x,y) pairs), that we are going to process, such that for each co-ordinate, we get a mapping to a particular row (r) and column (c) in our matrix. So, we basically have [r, c] = f(x,y). The particularities of the mapping function f are not important. However, what we want to do, is keep track of the rows r and columns c that are used, by inserting them into another list, called list-of-indicies.

The problem is that, I do not want to keep adding the same r and c to the list if that (r,c) pair already exists in that list. The brute force method would be to simply scan the entire list-of-indicies every time I want to check, but that is going to be very time consuming.

For example, if we have the co-ordinate (x=4, y=5), this yields (r=2, c=6). So, we now add (r=2, c=6) to the list-of-indicies. Now we get a new point, given by (x=-2, y=10). This also ends up falling under (r=2, c=6). However, since I have already added (r=2, c=6) to my list, I do not want to add it again! But without doing a brute-force scan of the list-of-indicies, is there a better way?

Spacey
  • 2,941
  • 10
  • 47
  • 63
  • 4
    Use a `std::map` (or `std::unordered_map`)? – Oliver Charlesworth Aug 23 '15 at 19:06
  • @OliverCharlesworth Thanks for the tip - indexing in efficient ways is new to me, so thanks for the leads. I will look them up. In the meantime, can you give a brief description of how it would fit here, to augment what I read about it? Thanks again. – Spacey Aug 23 '15 at 19:07
  • You could use a 'reverse matrix' that you fill in with r and c as the coordinates, simply check if it has a value, if it doesn't, fill it in, otherwise don't. – DrunkWolf Aug 23 '15 at 19:08

2 Answers2

8

You would need a map to do that.

In case you use c++11 you can use unordered_map which is a hashmap and has a constant time lookup, in case you use an older version of c++ you can use the standard map, which is a treemap, and has a logarithmic lookup.

The performance difference won't be big, if you don't have many items.

  • Thanks Aleksandar. I am looking up unordered map as we speak - I am somewhat unclear as to 'how' it is managing a constant time lookup - what is going on here under the hood? Secondly, am I just expected to feed it (r,c), and then have it output... what?... whether it is occupied or not? Thanks. – Spacey Aug 23 '15 at 19:11
  • @Learnaholic Basically it calculates the hash of an element, and based on the hash it tries to insert it in the array, if an element already exists there it will find the next possible hash. The hash functions have good hashing algorithms that reduces the number of collisions to a constant number. For more check https://en.wikipedia.org/wiki/Hash_table . It depends if you use a unorderedmap you have a key and value, you can ask if the key exists, and what it value is. Else you can use an unorderedset, where you cna only ask if a given key exists. –  Aug 23 '15 at 19:17
  • thanks - I have been reading up on unordered maps all day, but I seem to not be getting something - it seems like I have to 'define a hash function' in order to use it? Is this true for my application, that way I have described it? – Spacey Aug 24 '15 at 01:42
  • @Learnaholic yes, you would need to implement a hashing function for it. As you probably have std::pair you should check this one https://stackoverflow.com/questions/7222143/unordered-map-hash-function-c , the answer shows a nice implementation of the hashing. –  Aug 24 '15 at 07:30
4

Instead of the map or unordered_map you could simply use a matrix vector<vector<bool>> with the same R and C as your other matrix with every field initialized to false. Instead of adding and (r,c) pair to a list you simply set the corresponding boolean in the matrix to true.

trenki
  • 7,133
  • 7
  • 49
  • 61