CODEWITHSUNDEEP
c++dictionarycontainersstdvector
sccs
sccs

Reputation: 1163

std::map<int, int> vs. vector of vector

I need a container to store a value (int) according to two attributes, source (int) and destination (int) i.e. when a source sends something to a destination, I need to store it as an element in a container. The source is identified by a unique int ID (an integer from 0-M), where M is in the tens to hundreds, and so is the destination (0-N). The container will be updated by iterations of another function.

I have been using a vector(vector(int)) which means goes in the order of source(destination(value)). A subsequent process needs to check this container, to see if an element exists in for a particular source, and a particular destination - it will need to differentiate between an empty 'space' and a filled one. The container has the possibility of being very sparse.

The value to be stored CAN be 0 so I haven't had success trying to find out if the space is empty, since I can't seem to do something like container[M][N].empty().

I have no experience with maps, but I have seen another post that suggests a map might be useful, and an std::map<int, int> seems to be similar to a vector<vector<int>>.

To summarise:

  1. Is there a way to check if a specific vector of vector 'space' is empty (since I can't compare it to 0)
  2. Is a std::map<int, int> better for this purpose, and how do I use one?

Upvotes: 0

Views: 3666

Answers (3)

Boyko Perfanov
Boyko Perfanov

Reputation: 3047

First of all, assuming you want an equivalent structure of vector<vector<int>>

you would want

std::map<int,std::vector<int>>

because for each key in a map, there is one unique value only.

If your sources are indexed very closely sequentially as 0...N, will be doing a lot of look-ups, and few deletions, you should use a vector of vectors.

If your sources have arbitrary IDs that do not closely follow a sequential order or if you are going to do a lot of insertions/deletions, you should use a map<int,vector<int>> - usually implemented by a binary tree.

To check the size of a vector, you use

myvec.size()

To check whether a key exists in a map, you use

mymap.count(ID) //this will return 0 or 1 (we cannot have more than 1 value to a key)

I have used maps for a while and even though I'm nowhere close to an expert, they've been very convenient for me to use for storing and modifying connections between data.

P.S. If there's only up to one destination matching a source, you can proceed with 

map<int,int>

Just use the count() method to see whether a key exists before reading it

Upvotes: 2

Mark Ransom
Mark Ransom

Reputation: 308520

If you want to keep using a vector but want to add a check for whether the item contains a valid value, look at boost::optional. The type would now be std::vector<std::vector<boost::optional<int>>>.

You can also use a map, but the key into the map needs to be both IDs not just one.

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

Edit: std::pair implements a comparison operator operator< that should be sufficient for use in a map, see http://en.cppreference.com/w/cpp/utility/pair/operator_cmp.

Upvotes: 0

Josh Petitt
Josh Petitt

Reputation: 9589

I need a container to store a value (int) according to two attributes, source (int) and destination (int)

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

A subsequent process needs to check this container, to see if an element exists in for a particular source, and a particular destination - it will need to differentiate between an empty 'space' and a filled one.

std::map::find

http://www.cplusplus.com/reference/map/map/find/

The container has the possibility of being very sparse.

Use a std::map. The "correct" choice of a container is based on how you need to find things and how you need to insert/delete things. If you want to find things fast, use a map.

Upvotes: 3

Related Questions