Why algorithm function available even though it is slow ?

Question

Hi

We have find function from algorithm header as well as map class.

Algorithm merely working on data does not know that map has implementation of red black tree and it contains sorted data.

So, map class find works faster than algorithm function find.

Concern is why such duplicate function from stl ? What is need to have algorithm function as specific container functions are faster ?

Answer 1

Think of a map as a dictionary it’s a very specific way of storing data. The other containers especially vector are fast for random access and other things so find sort etc can work on them. I usually use a map for storing things by name so std::unordered_map<std::string,object *>

Algorithms are specified in terms of iterator kinds, forward, random, etc. This means they're POLYADIC meaning independent of the container type (provided it supports the required kind of iterator).

This means you can change the container type without changing the semantics.

Answer 2

if you're talking about find() from an array and getting values from map by keys, those are completely different usage, a map which are implemented as a hash table works by hashing your key and use it in the internal array with a complexity of O(1) aka constant no matter how long your map is or how big the data is it's still gonna take constant time, on the other hand find() iterates over an array to find a specific element which takes O(n), n being the length of the array and this is very slow process

think of it like map stores your data in a hashed key (like a book name) and it can be turned to an integer for example, and you can go to the right index from that integer from a list of books, and find() is just looking from the start until you find them

you can read more about them here https://www.geeksforgeeks.org/difference-between-array-and-map/

Answer 3

CutieRei thanks for this information... I have basic idea about the implementation and why map specifically onordered map is O(1) and normal map is O(log n ) by using class specific find function

Concern is availability of algorithm function from c++... It is slower compared to specific function from container... If it is not better , what's the point of having those function from algorithm ?

Sole purpose is to know the scenario when one would chose algorithm function rather than going with member function of specific container (like map etc)

Answer 4

well the map find is looking for a key in the hash table but a normal find() takes in an iterator which are mostly from arrays, and map is an iterator but its not indexed like an array, so like map stores a key value pair but just know that the key are unique, on the other hand arrays stores element of the same type and is indexable, so array[0] searches the offset 0 of the array there's a lot of low level things happening which i forgot about them but arrays are a sequence of elements of the same type like a list of books, but a map are a key value pair like types of furniture in your house, and technically you can use map for similar behavior like array but you shouldn't, accessing their values are similar in terms of speed if you know their position, im sorry if anything is missing lmao

Answer 5

I think you misunderstood the question...

I am not asking for what to choose as container like map or vector or array...

Assume that I have chosen map for my requirements and it is fine as far as choice is concerned...

Now question is map has also find function and algorithms has also find function... Map.find is faster than algorithm find function...

There are so many such function which are present in both algorithm header and map... But I feel that map specific function on map data is faster than algorithm function

So is there some case when specific function to container is slower than the algorithm function ?

Answer 6

well there's a worst case for it, O(n) container size, says so on the c++ docs for map::find()