Home » U++ Library support » U++ Core » what about VectorBiMap / ArrayBiMap ?
what about VectorBiMap / ArrayBiMap ? [message #26407] |
Fri, 30 April 2010 09:55 |
|
kohait00
Messages: 939 Registered: July 2009 Location: Germany
|
Experienced Contributor |
|
|
if you have lets say VectorMap<String, String> which is kind of a dictionary map, than you can search in one direction using the Find method. but if you want to look for the key that corresponds to a value, than there is only FindIndex(), which is sort of plain compare loop. what about having a container class, that offers both directions?
const VectorMap<K, T>;
int id = VectorMap<K, T>::Find(const K & key);
int id = VectorMap<K, T>::Find(const T & t);
const K & VectorMap<K, T>::operator[] const;
K & VectorMap<K, T>::operator[];
//donno if thats possible to override like that
const K & VectorMap<K, T>::operator[] const;
K & VectorMap<K, T>::operator[];
|
|
|
Re: what about VectorBiMap / ArrayBiMap ? [message #26410 is a reply to message #26407] |
Fri, 30 April 2010 10:49 |
|
mirek
Messages: 13975 Registered: November 2005
|
Ultimate Member |
|
|
kohait00 wrote on Fri, 30 April 2010 03:55 | if you have lets say VectorMap<String, String> which is kind of a dictionary map, than you can search in one direction using the Find method.
|
What you mean by direction? If you want to search starting with the last element with the value, you still can - FindLast, FindPrev.
Quote: |
but if you want to look for the key that corresponds to a value, than there is only FindIndex(), which is sort of plain compare loop. what about having a container class, that offers both directions?
|
Just use pair of Indexes.
In fact, the Index is the ultimate mapping weapon. VectorMap is just its common use wrapper...
Mirek
|
|
|
Re: what about VectorBiMap / ArrayBiMap ? [message #26416 is a reply to message #26410] |
Fri, 30 April 2010 13:13 |
Mindtraveller
Messages: 917 Registered: August 2007 Location: Russia, Moscow rgn.
|
Experienced Contributor |
|
|
Over three years of using U++ containers approved them to be extremely quick and easy to use. Everything you put into ****Map, is searched with hash, which is extremely fast even for large number of records.
The only thing which IMO is needed is Index "const hash/key" flavour which means that container element doesn't change it's internal state far enough to change it's hash value. This flavour should make possible to return (T &) from operator[], not (const T &).
Above this thing, U++ containers are far more comfortable and fast than any STL.
[Updated on: Fri, 30 April 2010 13:14] Report message to a moderator
|
|
|
|
Re: what about VectorBiMap / ArrayBiMap ? [message #26429 is a reply to message #26410] |
Fri, 30 April 2010 16:32 |
|
kohait00
Messages: 939 Registered: July 2009 Location: Germany
|
Experienced Contributor |
|
|
@Mirek:
direction is meant to be key -> value, or value -> key;
say i have a pair of Strings, in a capabale VectorBiMap,
and add "MyKey" | "MyValue" pair (here spoken as key/value), then i will be able to find location of "MyValue" *VIA HASH* of "MyKey", what is trivial and possible with VectorMap.
but what if i want to be able to find location of "MyKey" (which is same location of "MyValue") *VIA HASH* of "MyValue"?
this is currently not possible, except manually using 2 Indexes, separately driving their api together. But is quite cool.
usecase: (simple and stupid) a dictionary 2 languages with exactly a pair of words like "Buenos Dias" <=> "Hi" (stupid)
and a *HIGH* speed translation in *BOTH* directions needed.
another usecase is a communication protocol translator, which depending on strings sends special values, and answers with values, which map to strings again.
this would need *2* Indexes with same stuff in it but swaped K-T
i had some ideas like the following:
template<class K, class T, class HashFnK = StdHash<K>, class HashFnT = StdHash<T>>
class VectorBiMap
: public Index<K, HashFnK>
, public Index<T, HashFnT>
{
//following the api
//find T with K hash
//find K with T hash
};
template<class K, class T, class HashFnK = StdHash<K>, class HashFnT = StdHash<T>>
class VectorBiMap2
: public MoveableAndDeepCopyOption<VectorBiMap2<K, T, HashFnK, HashFnT> >
, public AMap< K, T, Vector<T>, HashFnK >
{
typedef AMap< K, T, Vector<T>, HashFnK > B;
HashBase hash2;
HashFnT hashfn2;
//following the api
//find T with K hash
//find K with T hash
};
i took a look in to implementation and it looks like there is no way except for coding an additional Interface, AIndex is not suitable AMap neither, but its a mix of both
PITFALL: all hash containers of Upp allow hash collision (handled internally with linked list). for a bijectional relation, this is not allowed ! or to define this to be a right unique relation (surrection)
i'll try it..any hints/comments/evaluations on the idea welcome
PS: in case of using Index, this would imply to use non const operator[] there like dicsribed above i think
|
|
|
Re: what about VectorBiMap / ArrayBiMap ? [message #26430 is a reply to message #26429] |
Fri, 30 April 2010 22:54 |
|
mirek
Messages: 13975 Registered: November 2005
|
Ultimate Member |
|
|
kohait00 wrote on Fri, 30 April 2010 10:32 | @Mirek:
direction is meant to be key -> value, or value -> key;
say i have a pair of Strings, in a capabale VectorBiMap,
and add "MyKey" | "MyValue" pair (here spoken as key/value), then i will be able to find location of "MyValue" *VIA HASH* of "MyKey", what is trivial and possible with VectorMap.
but what if i want to be able to find location of "MyKey" (which is same location of "MyValue") *VIA HASH* of "MyValue"?
this is currently not possible, except manually using 2 Indexes, separately driving their api together. But is quite cool.
usecase: (simple and stupid) a dictionary 2 languages with exactly a pair of words like "Buenos Dias" <=> "Hi" (stupid)
and a *HIGH* speed translation in *BOTH* directions needed.
|
Index<String> spain;
Index<String> english;
void AddWord(const String& sp, const String& en)
{
spain.Add(sp);
english.Add(en);
}
String EnglishToSpain(const String& w)
{
int q = english.Find(w);
return q >= 0 ? spain[q] : String();
}
String SpainToEnglish(const String& w)
{
int q = spain.Find(w);
return q >= 0 ? english[q] : String();
}
Mirek
|
|
|
|
|
|
Re: what about VectorBiMap / ArrayBiMap ? [message #26517 is a reply to message #26503] |
Fri, 07 May 2010 14:37 |
|
mirek
Messages: 13975 Registered: November 2005
|
Ultimate Member |
|
|
kohait00 wrote on Thu, 06 May 2010 14:38 | sorry, i try to make it more clear..
in containers, by default, it is possible adding another element with same hash. this is called hash collision, because normaly a hash value should map to exactly one counterpart.
is there a possib in the containers internally, to restrict such behaviour besides manually checking before adding another element?
i know of FindAdd, but this handles it kind of differently..
|
Uh, I am not quite sure what you want to check.
Generally, hashing is always a little bit stochastic. In theory, it is possible that collisions would slow down your code, but statistically, it is quite unlikely.
Or, if you want some analogy, some very special pattern of memory allocations and frees could put down to knees any memory allocator and/or any cache subsystem. But it is so unlikely to happen (unless engineered) that we are still using memory allocators and caches...
BTW, of course, U++ changes the size of hashing space dynamically based on number of elements...
Whatever, my advice is to forget about this. It is internal issue, do not think in terms of hash codes...
|
|
|
|
Goto Forum:
Current Time: Sat May 04 18:20:32 CEST 2024
Total time taken to generate the page: 0.03295 seconds
|