push back for the map container

Question

we got this map :

std::map <int, int> values;

would this function be the same as the push_back function of a Vector :

void PushBack(int value)
{
  values[values.size()] = value;
}

since size returns the size of the container I thought it would be correct, according to the following scenario it is : index 0 = 200 index 1 = 150 you want to push back 100, values.size() would return 2, right? so then, it would , just like the normal push_back go inside index 2, correct?

Solution 1

The whole point of maps is to lookup and store data based on a key that uniquely represents that data.

If you're doing this there's no point in using a map; you should choose another data structure that more appropriately addresses the design needs of the application.

Solution 2

Maps and vectors are very different.

The short version to the actual question you asked:

if all you do on your customized map is key-based lookup of already existing keys (the operator[]) and your push_back it may act like an inefficient drop-in replacement for vector where you only use the vector operator[] and push_back, yes.

The long version providing some background on why what you are doing is probably not actually what you want:

A map doesn't have an index, it has a key. A map is usually implemented as a red-black tree. Such a data structure allows for efficient lookup based on the key. You usually care about the key of a particular element, the key itself carries important information. Keys are usually not contiguous, and maps will not allocate space for keys that are not used in the map.

A vector is a contiguous block of memory. This allows for efficient indexed access. An index is not the same as a key: you generally don't care about which index a particular element gets, which index you do get depends on the order of insertion (they key is independent of the insertion order in in a map), indexes into vectors are always integer values, and you cannot have non-contiguous indexes.

If all you do in your map is your own custom push_back then to the outside it might appear to function like a vector in some contexts, and it might not in ways in other contexts (e.g. iterator invalidation).

Since you don't actually care about the key for the element that gets added in your example the choice of a map is pointless. Indexed lookup in the vector will be faster, and memory overhead will be smaller (though you could end up with memory fragmentation issues if you allocate very many objects, but that's a separate subject).

And finally, if you don't know which container class to use, vector and list are the places to start. Understand the differences between those two, and when you should use either of them, and then move on to the more advanced, specialized containers like map, set, their "multi" variants, and their "unordered" variants.

Solution 3

Unless you only use the map in a very special way, it won't be correct. Consider this scenario:

std::map<int, int> values;

values[1] = 42;
PushBack(7);

values now holds just one element, 7, at index 1.

The question is, of course, if you need 'push back', why use a map in the first place.

Comments

[Barış Uşaklı]

+1, std::vector and std::map exist for different purposes use them where they make sense.

[Alessandro Flati]

This is not entirely true, often extensions as for the OP one are needed in order to implement missing methods on otherwise slow containers (obviously, slowness depends on the specific application and its use, but a typical scenario/example is using std::map<int,T> instead of std::vector<T> and std::list<T> when you have to fast access and erase elements).