i have an array of strings (2D array). i am taking input of strings and that strings can be same with strings which i have inputted before that string. so i want that i don't enter that string which is already being taken into array. so how can i do this thing in my code ? using linear search is costly in my case. thanks in advance.
nitin1 15 Master Poster
deceptikon 1,790 Code Sniper Team Colleague Featured Poster
tux4life commented: Yuppers ;-) +13
nitin1 15 Master Poster
map<string,int> M is really an awsome thing. learnt today from book which you told me one month back. yipeee.. :-) don't know how map work ? how it hash the keys ? secondly, can i say that it is good to learn C++ for these types of implementaions ? because in C, they are very tuff to do in limited time. thanks in advance.
deceptikon 1,790 Code Sniper Team Colleague Featured Poster
don't know how map work ?
Typically it's some form of balanced binary search tree, with red black trees being the most common implementation.
secondly, can i say that it is good to learn C++ for these types of implementaions ?
Using a library is recommended over rolling your own data structures. Whether that results in using a language where the standard library has what you need or linking with a third party library so that you can continue using C is entirely your decision.
nitin1 15 Master Poster
how does it hash each value to a differnet location ? i hope it will definitely have collision problem. yes! i knoe about red black trees. AVL trees can also be implemented using this ? thanks sir.
deceptikon 1,790 Code Sniper Team Colleague Featured Poster
how does it hash each value to a differnet location ?
It doesn't hash anything, the keys are exact matches. For duplicate keys in C++ you'd either use a multimap<> or store a list of values at the same key:
map<string, vector<T>> m;
In C you'd do something similar, but using a third party library or by writing your own tree.
nitin1 15 Master Poster
ohh... multimap is just an map having second argument as vector , can i say this simply for multimap ? and secondly, in C , this is really going to be a difficiult and time taking task so implement our own tree in time constraint ? thirdly, and sir, the space used in map is the sum of spaces used ny keys + values or does it take more than that ?
deceptikon 1,790 Code Sniper Team Colleague Featured Poster
ohh... multimap is just an map having second argument as vector , can i say this simply for multimap ?
No, not at all. std::multimap is a collection that supports duplicate keys, it's not the same thing at all as a std::map with a collection as the value.
in C , this is really going to be a difficiult and time taking task so implement our own tree in time constraint ?
If you're writing it from scratch and don't have experience with those data structures then yes. However, if you rely on a good tutorial things become drastically simpler.
the space used in map is the sum of spaces used ny keys + values or does it take more than that ?
Assuming we're talking about a red black implementation then it takes more space. Usually equal to the cost of two or three pointers (links) and a boolean (red black state). There might be other extraneous fields as well.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.