LinkedHashMap in C++
ap...@student.open.ac.uk
LinkedHashMap. For those not in the know this is like a hash table (ie
fast indexing via hash function) but also has the neat feature where
iterating through the table the entries are retrieved in the order
they were inserted. This is really useful when implementing caches. I
wonder what plans there are (if any) for a similar class in the std
library?
Regards,
Andrew Marlow
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Mathias Gaunard
> I have recently started using java and have come across the
> LinkedHashMap. For those not in the know this is like a hash table (ie
> fast indexing via hash function) but also has the neat feature where
> iterating through the table the entries are retrieved in the order
> they were inserted. This is really useful when implementing caches. I
> wonder what plans there are (if any) for a similar class in the std
> library?
std::list<T> (or std::vector<T> or whatever) + std::unordered_map<T*>
int...@gmail.com
> On 22 nov, 13:27, ap...@student.open.ac.uk wrote:
>
> > I have recently started using java and have come across the
> > LinkedHashMap. For those not in the know this is like a hash table (ie
> > fast indexing via hash function) but also has the neat feature where
> > iterating through the table the entries are retrieved in the order
> > they were inserted. This is really useful when implementing caches. I
> > wonder what plans there are (if any) for a similar class in the std
> > library?
>
> std::list<T> (or std::vector<T> or whatever) + std::unordered_map<T*>
Better yet, std::unordered_map<T> +
std::list<std::unordered_map<T>::iterator>
ap...@student.open.ac.uk
banner. Tip: newsreader programs (except Google) remove it
automatically. -mod }
On 23 Nov, 08:36, Mathias Gaunard <loufo...@gmail.com> wrote:
> On 22 nov, 13:27, ap...@student.open.ac.uk wrote:
>
> > I have recently started using java and have come across the
> > LinkedHashMap. For those not in the know this is like a hash table (ie
> > fast indexing via hash function) but also has the neat feature where
> > iterating through the table the entries are retrieved in the order
> > they were inserted. This is really useful when implementing caches. I
> > wonder what plans there are (if any) for a similar class in the std
> > library?
>
> std::list<T> (or std::vector<T> or whatever) + std::unordered_map<T*>
What did you have in mind? Please give more detail. A std::list is not
a linked hashmap. It is also different from a vector. And what do you
mean by a whatever? I suppose I could use a whatever to serve as a
LinkedHashMap in C++, if only I knew what it was.
Sean Hunt
> What did you have in mind? Please give more detail. A std::list is not
> a linked hashmap. It is also different from a vector. And what do you
> mean by a whatever? I suppose I could use a whatever to serve as a
> LinkedHashMap in C++, if only I knew what it was.
The suggestions are to store your data in one data structure, and then
store the iterators in another. Currently, C++ does not actually
guarantee the presence of a hash map, though your implementation may
provide one. The basic suggestion is that if you store your iterators
to std::unordered_map in a list, then you can add an iterator each
time to add to the map, effectively recording how things are accessed.
The data iterators provide very fast data to any individual element as
well.
If you want to create a class that wraps this featureset, you'll have
to do it yourself, though. There doesn't exist any pre-written
functionality for this.
Mathias Gaunard
> > std::list<T> (or std::vector<T> or whatever) + std::unordered_map<T*>
>
> What did you have in mind? Please give more detail.
Use whatever container that preserves sorting to store your keys, and
then have a separate hash table that maps those keys to values. (I
forgot to put the value type, btw)
The other idea though is more efficient: store your objects in the
hash table and then maintain the order in which to iterate your
hashtable in another container.
Roman.Pe...@gmail.com
> I have recently started using java and have come across the
> LinkedHashMap. For those not in the know this is like a hash table (ie
> fast indexing via hash function) but also has the neat feature where
> iterating through the table the entries are retrieved in the order
> they were inserted. This is really useful when implementing caches. I
> wonder what plans there are (if any) for a similar class in the std
> library?
Use boost::multi_index library.
typedef multi_index_container<
T,
indexed_by<
sequenced<>, // list-like index
hashed_unique<> // hashed index
>
> hash_list;
Regards,
Roman Perepelitsa.
ap...@student.open.ac.uk
> > What did you have in mind? Please give more detail.
>
> store the iterators in another. Currently, C++ does not actually
> guarantee the presence of a hash map, though your implementation may
> provide one. The basic suggestion is that if you store your iterators
> to std::unordered_map in a list, then you can add an iterator each
> time to add to the map, effectively recording how things are accessed.
> The data iterators provide very fast data to any individual element as
> well.
Ah, I see. Thanks for clarifying that.
> If you want to create a class that wraps this featureset, you'll have
> to do it yourself, though. There doesn't exist any pre-written
> functionality for this.
Well, this is what I thought might be the case. Wouldn't it be good if
there were plans for this to be added? I know some people may groan at
yet more to be added but hear me out. What I am saying is this is an
example of where java has a very useful foundation class that C++ does
not. It seems to me that C++ can learn from java in seeing what
foundation classes people find useful that are present in java and
providing a C++ equivalent.
I realise that equivalents in all areas are sometimes not possible or
inappropriate but I dont think that's the case for LinkedHashMap. I'm
sure there must be others. One thing I have in the back of my mind is
what plans there are (if any) for adding ODBC access to C++. This is
extremely convenient in java. I have seen it done in C++ but these
solutions are not 'official'.
Regards,
Andrew Marlow