How to unsort elements in map

[longway]

when using map to define a collection, It always sort the elements. How to prevent it automatically sort them or how to get element list as inserted?

Many thanks.

[alan w]

Elements are always sorted as they are inserted into a map container, so you should use an unsorted container, such as a list.

You *can* define your own key_comp function that will not sort the elements as they are added, but this will break everything dependent on sorting, such as map::find and map::operator[]. It will also break the single-entry characteristics of the map container (you can add multiple same keys like multimap).

#include <iostream>
#include <map>

template<class _Ty>
	struct nosort {
		bool operator()(const _Ty&, const _Ty&) const {
			return (true);
		}
	};

typedef std::map <int, std::string, nosort<int> >::iterator FILO_IT;
typedef std::map <int, std::string, nosort<int> > FILO_MAP;

int main()
{
	FILO_MAP UnSortedMap;
	FILO_IT  UnSortedIt;

	UnSortedMap[2] = "Rate";
	UnSortedMap[5] = "This";
	UnSortedMap[8] = "Post";
	UnSortedMap[1] = "If";
	UnSortedMap[7] = "It";
	UnSortedMap[7] = "Helped";

	for( UnSortedIt = UnSortedMap.begin(); UnSortedIt != UnSortedMap.end(); UnSortedIt++ )
	{
		std::cout << UnSortedIt->first << " " << UnSortedIt->second.c_str() << std::endl;
	}

	UnSortedIt = UnSortedMap.find(2);
	if( UnSortedIt != UnSortedMap.end() )
		std::cout << UnSortedIt->second.c_str() << std::endl;
	else
		std::cout << "Yep, sorting is broken" << std::endl;

	return 0;
}

[Ejaz]

[ Redirected Thread ]

[longway]

Thank you very much for your quick response.

I run your code snippet and get the following results:
7. Helped
7. It
1. If
8. Post
5. This
2. Rate
Yep, sorting is broken

It seems unsorted, but if I use insert() to add new element into map, I can get right elements order as inserted.

Thank you.

[Kheun]

See this thread.

[jlou]

Always returning true doesn't make sense for the comparison function of a map, since (a < b) should imply !(b < a). You could always return false, but there would be no guaranteed order of insertion, it might seem random and would not be reliable.

The hash_map has the same problem as the map. You cannot get the elements out as they were inserted.

You probably need two containers. One to maintain insertion order, and another to provide fast lookups. If you don't need fast lookups then of course a deque, list, or vector would work fine. If you do then you could have a vector (or deque) of your values (in insertion order) and a map of keys to the index in the vector of the appropriate value. This uses more storage, but it gives you fast lookup (find the key in the map and then access that element in the vector) and of course you can loop through the vector itself in insertion order.

[alan w]

It seems unsorted, but if I use insert() to add new element into map, I can get right elements order as inserted.

Right, it's unsorted but it's always going to be in FILO order. Inserting elements where you want them won't work. Each item inserted will always be inserted at the head of the list using this nosort<> key_comp function.

You can always retrieve the elements in reverse order, which would be the order of insertion.

Always returning true doesn't make sense for the comparison function of a map, since (a < b) should imply !(b < a). You could always return false, but there would be no guaranteed order of insertion, it might seem random and would not be reliable.

Always returning TRUE is the only way it makes sence with an unsorted map. Returning FALSE would result in each new element overwriting the previous, and you'd end up with only one element (the last one added) in the map.



I would suggest using another contianer. This was just an example to show it *could* be done with a map and how to do it... not that it is a good idea to do.

[jlou]

Always returning TRUE is the only way it makes sence with an unsorted map. Returning FALSE would result in each new element overwriting the previous, and you'd end up with only one element (the last one added) in the map.

You're right about returning false causing only one element to be stored (I was thinking multimap). However, I believe that always returning true might cause "undefined behavior". Of course, it doesn't really matter, since it makes no sense to use a map if your sort method always returns true.

[alan w]

You're right about returning false causing only one element to be stored (I was thinking multimap). However, I believe that always returning true might cause "undefined behavior".

Well the behavior is not undefined, no matter what you do every new element is added to the head. The elements are always in the correct order of adding them, they are just in FILO (last to first) order.

Of course, it doesn't really matter, since it makes no sense to use a map if your sort method always returns true.

Agreed.

[SuperKoko]

Well the behavior is not undefined, no matter what you do every new element is added to the head. The elements are always in the correct order of adding them, they are just in FILO (last to first) order.

No, the behavior is undefined.
An associative container must be used with a valid strict order between elements. Otherwise the behavior is undefined.

And, a strict order must be antireflexive, that is, for all x, !(x<x).
So, returning always true does not create a valid strict order algorithm.

Instead, returning always false is correct (but inefficient, that is : the std::map:perator[] will be very slow).

[marten_range]

It amazes me how easily _bad_ (really bad) ideas catches on. No flak intended towards alan w as he pointed out it was a bad idea. You spend years trying to convince people why std::vector is good or why std::string is good or why CString is good (I prefer std::string but CString >> C-style strings). Sometimes it feels like one don't succeed at all at getting the point through.

But as soon as someone presents a _bad_ idea that breaks neat classes such as std::map it seems people jumps on that bandwagon without much thought.

Just an observation.

PS. To the OP: Why not copy the elements into a std::vector and do an inplace shuffle? If you're worried about memory it's worth to consider that std::map uses a lot more memory than std::vector (to achive O(log n) lookups.