 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Nick R.
Guest
|
 Posted: Fri Dec 12, 2003 2:00 am Post subject: Saving hash_map content in orderly manner? |
 |
|
I have a hash_map with a bunch of strings inside. When I serialize it
into a file, I iterate the collection and simply write each string in turn.
The problem is that the order is simply chaotic and sometime changes if
the insertion map order!
Anybody knows a simple and fast way to do *a* ordering before saving the
map?
Thanks,
Nick
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
Joshua Lehrer
Guest
|
| Posted: Fri Dec 12, 2003 9:52 am Post subject: Re: Saving hash_map content in orderly manner? |
|
|
"Nick R." <nick_r75 (AT) yahoo (DOT) com> wrote
| Quote: | I have a hash_map with a bunch of strings inside. When I serialize it
into a file, I iterate the collection and simply write each string in turn.
The problem is that the order is simply chaotic and sometime changes if
the insertion map order!
Anybody knows a simple and fast way to do *a* ordering before saving the
map?
|
Why is this a problem? If you are using a hash table then the
ordering doesn't matter. If the order matters, you have to use a
container that is ordered, like std::map<>.
Why are you using a hash table, which is an unordered container, and
then complaining that you can't get the values out in an ordered
fashion?
joshua lehrer
factset research systems
NYSE:FDS
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Nick R.
Guest
|
| Posted: Fri Dec 12, 2003 4:57 pm Post subject: Re: Saving hash_map content in orderly manner? |
|
|
Joshua Lehrer wrote:
| Quote: | "Nick R." <nick_r75 (AT) yahoo (DOT) com> wrote
I have a hash_map with a bunch of strings inside. When I serialize it
into a file, I iterate the collection and simply write each string in turn.
The problem is that the order is simply chaotic and sometime changes if
the insertion map order!
Anybody knows a simple and fast way to do *a* ordering before saving the
map?
Why is this a problem? If you are using a hash table then the
ordering doesn't matter. If the order matters, you have to use a
container that is ordered, like std::map<>.
|
Order doesn't matter *in memory*, it matters *on disk*.
| Quote: | Why are you using a hash table, which is an unordered container, and
then complaining that you can't get the values out in an ordered
fashion?
|
For in memory access speed. Now, what's the easiest way to order them
before writing to the disk?
Nick
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Antoun Kanawati
Guest
|
| Posted: Fri Dec 12, 2003 6:57 pm Post subject: Re: Saving hash_map content in orderly manner? |
|
|
Nick R. wrote:
| Quote: | I have a hash_map with a bunch of strings inside. When I serialize it
into a file, I iterate the collection and simply write each string in turn.
The problem is that the order is simply chaotic and sometime changes if
the insertion map order!
Anybody knows a simple and fast way to do *a* ordering before saving the
map?
|
That's the natural behavior of hash maps. Nothing fundamentally wrong
with that.
Is it necessary to order the data in the output file, or is this an
aesthetic issue? or debugging support?
The quick-and-dirty way is to copy the hash map into a std::map, and
emit that one. Plain maps are sorted on key values. A slightly more
efficient approach would be to put the keys into a std::set, and then
iterate over the set to get your keys in a sorted sequence while saving
the contents of the hash map.
Since you're using the word "serialize", I presume that you're reading
the data file later. So, a third option would be to read the data into
a std::map and serialize it again into an nice looking order. This
would be useful if you have lots of data, and the order is necessary for
eyeballing the output, but not for program functionality.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Stephen Howe
Guest
|
| Posted: Fri Dec 12, 2003 7:14 pm Post subject: Re: Saving hash_map content in orderly manner? |
|
|
| Quote: | I have a hash_map with a bunch of strings inside. When I serialize it
into a file, I iterate the collection and simply write each string in
turn.
The problem is that the order is simply chaotic and sometime changes if
the insertion map order!
|
Right. But hash_map's are intrinsically unordered. You should be using a map
if you want ordering.
Stephen Howe
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
David Fisher
Guest
|
| Posted: Sat Dec 13, 2003 2:15 am Post subject: Re: Saving hash_map content in orderly manner? |
|
|
"Nick R." <nick_r75 (AT) yahoo (DOT) com> wrote:
| Quote: | I have a hash_map with a bunch of strings inside. When I serialize it
into a file, I iterate the collection and simply write each string in
turn.
The problem is that the order is simply chaotic and sometime changes if
the insertion map order!
Anybody knows a simple and fast way to do *a* ordering before saving the
map?
|
If you just want to sort it for a single operation like writing to a file,
you can create a temporary vector of pointers to the objects in the
hash_map, and then sort the pointers (which is faster than swapping values
all the time, unless they are integers or something; come to think of it,
strings tend to be reference counted, so this may not be the best example).
Anyway, here is one way to do it:
inline bool stringPtrCompare(const string *s1, const string *s2) const
{
return (*s1 < *s2);
}
.....
typedef vector
StringPtrVec vec;
vec.reserve(theHashMap.size());
for (hash_map::iterator i = theHashMap.begin();i != theHashMap.end();++i)
{
vec.push_back(&(*i).second); // (assuming hash_maps are just like
std::maps ?)
}
sort(vec.begin(), vec.end(), stringPtrCompare);
Then iterate through the values of vec ...
David F
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Francis Glassborow
Guest
|
| Posted: Sat Dec 13, 2003 2:17 am Post subject: Re: Saving hash_map content in orderly manner? |
|
|
In article <brc3ln$1n01a$1 (AT) ID-197819 (DOT) news.uni-berlin.de>, Nick R.
<nick_r75 (AT) yahoo (DOT) com> writes
| Quote: | For in memory access speed. Now, what's the easiest way to order them
before writing to the disk?
|
something like:
std::map ordered(hm.begin, hm.end());
assuming that hm is your hash_map object.
--
Francis Glassborow ACCU
Author of 'You Can Do It!' see http://www.spellen.org/youcandoit
or http://www.robinton.demon.co.uk
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Ben Hutchings
Guest
|
| Posted: Sat Dec 13, 2003 2:20 am Post subject: Re: Saving hash_map content in orderly manner? |
|
|
Nick R. wrote:
| Quote: | Joshua Lehrer wrote:
"Nick R." <nick_r75 (AT) yahoo (DOT) com> wrote in message
news:<bra91s$16bhl$1 (AT) ID-197819 (DOT) news.uni-berlin.de>...
I have a hash_map with a bunch of strings inside. When I serialize it
into a file, I iterate the collection and simply write each string in turn.
The problem is that the order is simply chaotic and sometime changes if
the insertion map order!
Anybody knows a simple and fast way to do *a* ordering before saving the
map?
Why is this a problem? If you are using a hash table then the
ordering doesn't matter. If the order matters, you have to use a
container that is ordered, like std::map<>.
Order doesn't matter *in memory*, it matters *on disk*.
Why are you using a hash table, which is an unordered container, and
then complaining that you can't get the values out in an ordered
fashion?
For in memory access speed. Now, what's the easiest way to order them
before writing to the disk?
|
Copy the elements to a vector, sort the vector, write that out.
More efficiently, copy pointers to the map's elements and sort
according to their target values:
typedef stdext::hash_map<std::string, std::string> map_type;
typedef map_type::value_type value_type;
template<typename T>
struct address_of : std::unary_function<T, T*>
{
T * operator()(T & value) const
{
return &value;
}
};
template<typename T, typename Pred>
struct compare_first
: std::binary_function<const T *, const T *, bool>
{
compare_first(Pred pred = Pred()) : pred_(pred)
{}
bool operator()(const T * left, const T * right) const
{
return pred_(left->first, right->first);
}
private:
Pred pred_;
};
template<typename T>
struct write_pair : std::unary_function<const T *, void>
{
write_pair(std::ostream & os) : os_(os)
{}
void operator()(const T * pair) const
{
os_ << pair->first << ": " << pair->second << "n";
}
private:
std::ostream & os_;
};
void write_map(const map_type & map, std::ostream & os)
{
std::vector
std::transform(map.begin(), map.end(),
std::back_inserter(vector),
address_of<const value_type>());
std::sort(vector.begin(), vector.end(),
compare_first<value_type, std::less());
std::for_each(vector.begin(), vector.end(),
write_pair<value_type>(os));
}
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Stephen Howe
Guest
|
| Posted: Sat Dec 13, 2003 11:17 am Post subject: Re: Saving hash_map content in orderly manner? |
|
|
| Quote: | Order doesn't matter *in memory*, it matters *on disk*.
|
Why not do this:
1. Construct a vector of the keys in the hash_map by iterating over the
hash_map and push_back()'ing the elements into the vector (or a vector of
hash_map iterators)
2. sort() the vector using a appropriate predicate
3. iterate over the vector, locating each item in the hash_map (and if it
is the hash_map iterators, there is no location overhead)
and write to disk.
Stephen Howe
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Ed Avis
Guest
|
| Posted: Sat Dec 13, 2003 11:24 am Post subject: Re: Saving hash_map content in orderly manner? |
|
|
Ben Hutchings <do-not-spam-benh (AT) buswebsoft (DOT) dnsalias.com> writes:
| Quote: | I have a hash_map with a bunch of strings inside. When I serialize it
into a file, I iterate the collection and simply write each string in turn.
Copy the elements to a vector, sort the vector, write that out.
|
I'm not clear on whether the keys or values of the map are being
written, or both. If writing the values or keys+values it may be more
efficient to copy only the keys to a vector, sort that, and write in
key order. Perhaps this is what you meant anyway.
--
Ed Avis <ed (AT) membled (DOT) com>
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
