How to shuffle 2 random items in a map?

[Somelauw]

Here is a code which needs to be expanded.

include <iostream>

include <map>

using namespace std;

int main()
{
map <const char*, int> List;

//Initializing
List["ene"] = 1;
List["tweede"] = 2;
List["derde"] = 3;
List["vierde"] = 4;
List["vijfde"] = 5;

// HERE I NEED HELP!   
// I want to swap the 3th and 4th item, but I don't want to access them by
// their key.
swap(List.3th, List.4th);

// Print the items to test the result.   
for(map<const char*, int>::iterator iter = List.begin(); iter != List.end(); iter++ ) {
    cout << (*iter).first << " is " << (*iter).second << endl;
}

}

Can someone please help me?

[Somelauw]

Thanks for your time.

[cpns]

A map is not a list, and so there is no concept of third or fourth (or I guess "derde" or "vierde"?) in a map. Elements are not stored in a map in the order you add them. You can see this if you use an iterator to extract each member, the keys are alphanumerically sorted I believe you'll find.

If you need to access elements ordinally, then a map is an inappropriate container type. Containers such as <vector> and <list> overload the [] operator to take an ordinal integer so you can access elements ordinally (bearing in mind that the first element is 0 not 1).

If you really must do this, (but to be honest it smacks or poor design or lack of clear thought if you do), then you could do this:

const char*[] ordinal = { "dummy", "ene", "tweede", "derde", "vierde", "vijfde" } ;

then:

swap( List[ordinal[3]}, List[ordinal[4]] ) ;

But it seems a sledge hammer to crack a nut, hard to maintain, and error prone, it seems that you are simply using an inappropriate container type for the job.

Clifford

[Somelauw]

derde and vierde are Dutch for third and forth

For my goal a map or a dict seems the easiest. I want to add encryption to a compressor.
I just need a way to shuffle the items in the map or dict. I don't necessarily need the third item, but just a random one.

2 solutions are in my mind:

1. Iterating through an iterator a random number of times to find a random key.
   I wonder: Will an iterator have direct access to a map or will it built a copy first? Is constructing an iterator every step slow?

2. Using 2 lists where one functions as key and the other as element list.

[cpns]

> derde and vierde are Dutch for third and forth
I guessed that much! ;-)

> I don't necessarily need the third item, but just a random one.

Perhaps use an iterator and iterate a random number of times up to the size of the map. Might be very slow. Alternatively create a std::list of iterators to each map element and shuffle that. Bear in mind that the iterators are invalid if the map is altered.

> 2 solutions are in my mind:
>
> 1. Iterating through an iterator a random number of times [...]

Oh, you already thought of that!

> 2. Using 2 lists where one functions as key and the other as element list.

More or less what I suggested too. ;-) It is confusing to keep referring to a map as a list. My suggestion is that you have one std::map and one std::list.

Clifford

[Somelauw]

Wouldn't it be faster to use 2 lists instead of a list and a map since every time you append a key + item to the map, you also need to add the key to the list.

[cpns]

You said you needed a map, so I went with that; I am not suggesting that you keep a list of keys, but create a list of iterators just at the point you need to shuffle. I have not thought about this too hard, I may be talking s***t. I was thinking something like (untested):

map <const char, int> List;
map<const char, int>::iterator it;
list<map<const char*, int>::iterator> shuffle_list ;

...

for( it = List.begin() ; it != List.end(); it++ )
{
shuffle_list.push_back( it )
}

So now shuffle_list has a sequential list of pointers to elements in the map, so you shuffle the shuffler_list, not the map. You have to create a new list each time you have to shuffle if teh map has been modified - since the iterators may be invalidated (I think).

Note that std::list is efficient for element swapping, but not so good for random access, so you might be better off with std::vector. It depends on the nature of the objects - size and complexity of copying them, and the length of the list. Experiment.

Clifford

[Somelauw]

But elements need to be shuffled every step.

Anyway, someone on another forum suggested to use:
advance(it, amount) on the iterator.

I also found out that when changing the map, the iterator still works.
Probably iterators are still valid after changing the map in contrary as we both thought.

Here is the code the guy gave me (which I edited a bit to test adding elements to the map):

code:

include<iostream>

include <map>

using namespace std;

int main()
{
map <const char*, int> List;

List["ene"] = 1;
List["tweede"] = 2;
List["derde"] = 3;
List["vierde"] = 4;
List["vijfde"] = 5;

// I want to swap the 3th and 4th item, but I don't want to access them by
// key, but like it was an array.
assert( List.size() >= 5 ); // Assuming 0-based indexing?
map<const char*, int>::iterator i1( List.begin() );
map<const char*, int>::iterator i2( i1 );
List["zesde"] = 6;
std::advance( i1, 2 );
std::advance( i2, 5 );
swap( i1->second, i2->second );

for(map<const char*, int>::iterator iter = List.begin(); iter != List.end(); iter++ ) {
    cout << (*iter).first << " is " << (*iter).second << endl;
}
system("pause");

}

output:

ene is 1
tweede is 2
derde is 6
vierde is 4
vijfde is 5
zesde is 3

[cpns]

> Probably iterators are still valid after
> changing the map in contrary as we both thought.

It did occur to me that that might be the case. I should have checked. For vectors it is certainly not true. However if you add an element, that would not be present in your iterator list.

Anyway, I guess you have a solution.