Question: Data structure

[Ulutay]

I was wondering when it is better to use map and when to type my own data structure. Like which one is more efficient a manually created linked list or the map and why would i ever need to write some function, declare a head pointer ..etc to create my linked list while i have a ready made map library?
i know for a fact that binary trees data structure are a better choice if i need to take advantage of the left and right sorting and so. correct me if i am wrong. and another question rises here, like if i have thousands of entries would be faster to search for an element in a map than in the binary tree?
thanks.

[Disch]

I was wondering when it is better to use map and when to type my own data structure.

999 times out of 1000 (or more), you are better off using one of the pre-made STL containers, like vector, map, deque, set, etc.

if i have thousands of entries would be faster to search for an element in a map than in the binary tree?

A map IS a binary tree.

[Ulutay]

aha thanks thumbs_up();

I also wanted to know, what does an iterator in a map or a vector holds? i mean is an iterator a pointer? does it hold address or value?
i did like this:

map<string,string> x;
//... some strings data entered ... 

now i want to access a random node and display it, say i want to play (cout) a random song out of x (which holds singer name and name of the song..)
i did like this and doesn't compile of course and i can't figure out a solution:

srand(time(NULL)); //bla bla
int i=rand()%5;

map<string,string>::iterator itr= x.begin() + i;
cout<<itr->first<<"  " <<itr->second;

i assumed x.begin() returns the address of the first slot and i add a random number between 0-5 to get a random song out of first 5.
i even tried declaring a
map<string,string>* p_itr=&x;
but got stuck on how to desplay -> first and -> second ..

sorry for long story :)

[Disch]

I also wanted to know, what does an iterator in a map or a vector holds? i mean is an iterator a pointer? does it hold address or value?

Sort of. An iterator is very similar to a pointer. The main difference is that when you increment an iterator, it intelligently traverses the container, whereas when you increment a pointer, it blindly just advances to the next physical address whether it's valid or not.

now i want to access a random node and display it, say i want to play (cout) a random song out of x (which holds singer name and name of the song..)

You should not use a map for that.

Map are designed to have a "key" and "value" pair for each entry. The idea is that you can quickly look up a value by providing its key.

For a singer/song combo, you appear to be using the singer as they key... which only makes sense if you have a singer name and need to use it to look up their song.

On top of that, map does not do random access well. If you need random access, consider a vector (or a deque, but vector is typically better).

i did like this and doesn't compile of course and i can't figure out a solution:

Right, the error is that you cannot add to a map iterator like that because maps do not have random access. You would have to traverse the map one element at a time. Again, this is probably where map is at its weakest and you probably should not be using map if you need to access it this way.


Make a struct, and throw that struct in a vector:

struct SongInfo
{
    string singer;
    string song;
};

vector<SongInfo> x;

// ...

int i = rand() % 5;

auto& itr = x.begin() + i;
cout << itr->singer << "  " << itr->song;