Re: How to define a map whose 'key' is a structure?
Lambda <stephenhsu9@gmail.com> writes:
I want to sort several strings order by the matching vector size.
If I want to get the size of vector, I need to read the whole vector
first, right?
No. Check some stl reference, size() is O(1) for vectors.
http://www.cplusplus.com/reference/stl/vector/size.html
(See section "Complexity").
But because the amount of data of all the vectors is too large to
reside in memory,
I'll put all the vectors in disk.
You don't really have a choice, stl vectors are stored in virtual
memory. If your vectors become bigger than the available RAM, then
your system will swap some data out to the swap partition of file, but
this is done automatically. You don't have to do anything to get that
behavior.
On the other hand, if you are implementing your own vector, I cannot
say anything about them.
And let the map key contains a pointer to each matching vectors.
If I have vector size in the key, I can sort the several strings first
without disk read. So I need this redundancy vector size member in the
key.
All right. Just be sure you don't use this field in the comparison
function you pass to stl::map.
That is, to be clear, ?you cannot change the slots of the composite
key that are used by the order function of the map. ?
You mean, if I assign a key to map, the key must be constant, right?
Why can I use pointers?
Because C++ objects don't move in memory.
(This wouldn't be true with a copying garbage collector, but C++ is
far from having one. Language implementations that use copying
garbage collector may have to rehash hash-tables when they move keys).
The address of the structure will not change?
Right.
What if I move the structure to another place?
The map will be broken?
What circumstance are you considering?
struct Key {
....
};
bool Key_equal(const Key& a,const Key& b){
....
}
std::map<Key,Value,Key_equal> map1;
std::map<Key*,Value> map2;
In the case of map1, the key structures are copied inside the map, so
you can always destroy (or "move") your Key structures.
In the case of map2, the pointer to the key structures are copied
inside the map, so if you destroy (or have destroyed) a key structure
pointed to by map2, you're burst! You must ensure that the pointer to
the keys inside map2 stay valid while map2 is valid, like for any
other pointer. (Same would be true with references).
I just want to make sure there is no such function in C++.
Browse a stl reference, such as: http://www.cplusplus.com/reference/stl/
If I define a function take a parameter vector<string>,
how can I match the string with struct term in the map?
You tell us!
How do you want to match it?
I don't know. I'm trying to find a better way.
I think it would be clearer to keep the attribute with the value than
with the key. That's really what you want to do. In your case, it
seems the key is only the string, so you don't need a structure for
the key.
struct Attributes {
std::string word; // yes, put the key inside the value, it's often useful.
std::vector<size_t> sizes;
size_t numberOfSizes; // = sizes.size()
Attributes(std::string aWord):word(aWord){
computeSizes(word,&sizes);
numberOfSizes=sizes().size();
}
void update(void){
updateSizes(word,&sizes);
numberOfSizes=sizes().size();
}
};
std::map<std::string,Attributes*> wordMap;
then you can enter your words:
wordMap[word]=new Attributes(word);
and you can update your counters:
wordMap[word]->update();
and you can get the cached numbers:
wordMap[word]->numberOfSizes;
--
__Pascal Bourguignon__