Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > How to define a map whose 'key' is a structure?

Reply
Thread Tools

How to define a map whose 'key' is a structure?

 
 
Lambda
Guest
Posts: n/a
 
      06-23-2008
I'd like to define a std::map: map<struct term, vector<size_t> >.

The definition of the structure is:
struct term {
string word;
size_t freq;
};

the freq is the size() of vector<size_t>.

When I insert the 'term' into the map,
the map should sort the key by the string 'word'.

And later, I need to sort the 'term' by the 'freq'.

I think I can define two compare functions,
one for insertion to the map: map<struct term, vector<size_t>, comp1>
index;
another for a sort function: sort(terms.begin(), terms.end(), comp2).

And now:
1. How can I use map as associative array, that is, how to do
something like:
struct term test;
test.string = "Hello";
test.freq = 0;
index[test].push_back(1);
And after I push_back all the size_t, I need to change the value of
test.freq.

2. I didn't find a function that return all the 'keys' as a vector or
sth like that.
If I define a function take a parameter vector<string>,
how can I match the string with struct term in the map?

I wish I presented my questions clearly.

Thanks,
Stephen Hsu
 
Reply With Quote
 
 
 
 
Pascal J. Bourguignon
Guest
Posts: n/a
 
      06-23-2008
Lambda <(E-Mail Removed)> writes:

> I'd like to define a std::map: map<struct term, vector<size_t> >.
>
> The definition of the structure is:
> struct term {
> string word;
> size_t freq;
> };
>
> the freq is the size() of vector<size_t>.


Then just say it. In C++ !!

struct term {
string word;
};

size_t freq(string word,const map<term,vector<size_t> >& wordMap){
// freq
// is the
return wordMap[word].size();
// size
// of the vector of the
// word in the
// wordMap.
}

(and suddenly, you don't need structures as key anymore, but let's
assume you really needed a structure, like for example:

struct PersonId {
string name;
string firstName;
Date birthDate;
};


> When I insert the 'term' into the map,
> the map should sort the key by the string 'word'.
>
> And later, I need to sort the 'term' by the 'freq'.
>
> I think I can define two compare functions,
> one for insertion to the map: map<struct term, vector<size_t>, comp1>
> index;
> another for a sort function: sort(terms.begin(), terms.end(), comp2).


You cannot sort maps. The iterators returned by a map are not
random_iterators, that the sort algorithm expects. If you want the
keys you have put in the map in some other order, then you will have
to copy them in a vector, and sort that vector.


> And now:
> 1. How can I use map as associative array, that is, how to do
> something like:
> struct term test;
> test.string = "Hello";
> test.freq = 0;
> index[test].push_back(1);
> And after I push_back all the size_t, I need to change the value of
> test.freq.


You don't. It's like asking to change the value of 42.

If you need to change the value of test.freq without changing the
identity of the key, then you cannot use copies of the structures as
keys. You must use a pointer (or smartpointer) to the structure as
key. Then, the key will actually be the address of the structure, and
you will be able to change the slots of the structure, but of course,
the order will have to depend only on the actually key.

Otherwise, you won't change the value of the copies of the structures
used as keys in the map, unless you're ready to remap it (copy all the
entries from one map to another, changing on the fly the slots you
want in the keys). You can also remove the old entry from the map,
change the value of the key, and put back a new entry with the new
value of the key.


That is, to be clear, you cannot change the slots of the composite
key that are used by the order function of the map.



> 2. I didn't find a function that return all the 'keys' as a vector or
> sth like that.


Yep. Or do you think the standard library should include all the
programs you will ever have to write, so you're left only in choosing
which program you want and #include it?


> 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 wish I presented my questions clearly.


I wish you have clearer thoughts.

--
__Pascal Bourguignon__
 
Reply With Quote
 
 
 
 
Lambda
Guest
Posts: n/a
 
      06-23-2008
On Jun 23, 8:41*pm, (E-Mail Removed) (Pascal J. Bourguignon)
wrote:
> Lambda <(E-Mail Removed)> writes:
> > I'd like to define a std::map: map<struct term, vector<size_t> >.

>
> > The definition of the structure is:
> > struct term {
> > string word;
> > size_t freq;
> > };

>
> > the freq is the size() of vector<size_t>.

>
> Then just say it. *In C++ !!
>
> struct term {
> * *string word;
>
> };
>
> size_t freq(string word,const map<term,vector<size_t> >& wordMap){
> // * * freq
> // * * * * * * * * * * * * * * * * *is the
> * * return wordMap[word].size();
> // * * * * * * * * * * * size
> // * * * * * * * * * * * * * * * * *of the vector of the
> // * * * * * * * * word * * * * * * in the
> // * * * * wordMap.
>
> }
>
> (and suddenly, you don't need structures as key anymore, but let's
> assume you really needed a structure, like for example:
>
> struct PersonId {
> * string *name;
> * string *firstName;
> * Date * *birthDate;
>
> };


Thank you for your reply!
Of course, I can get the number of the size_t by the vector.size()
function.
I have tried it first. But it's not good enough.

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?
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.
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.

> > When I insert the 'term' into the map,
> > the map should sort the key by the string 'word'.

>
> > And later, I need to sort the 'term' by the 'freq'.

>
> > I think I can define two compare functions,
> > one for insertion to the map: map<struct term, vector<size_t>, comp1>
> > index;
> > another for a sort function: sort(terms.begin(), terms.end(), comp2).

>
> You cannot sort maps. *The iterators returned by a map are not
> random_iterators, that the sort algorithm expects. *If you want the
> keys you have put in the map in some other order, then you will have
> to copy them in a vector, and sort that vector.
>


I don't want to sort the map, because all the members in the map is
always sorted.
As the map is implemented with Red-Black Tree,
the map need to know how to compare two keys to put them in right
places.

> > And now:
> > 1. How can I use map as associative array, that is, how to do
> > something like:
> > struct term test;
> > test.string = "Hello";
> > test.freq = 0;
> > index[test].push_back(1);
> > And after I push_back all the size_t, I need to change the value of
> > test.freq.

>
> You don't. *It's like asking to change the value of 42. *
>
> If you need to change the value of test.freq without changing the
> identity of the key, then you cannot use copies of the structures as
> keys. *You must use a pointer (or smartpointer) to the structure as
> key. *Then, the key will actually be the address of the structure, and
> you will be able to change the slots of the structure, but of course,
> the order will have to depend only on the actually key.
>
> Otherwise, you won't change the value of the copies of the structures
> used as keys in the map, unless you're ready to remap it (copy all the
> entries from one map to another, changing on the fly the slots you
> want in the keys). You can also remove the old entry from the map,
> change the value of the key, and put back a new entry with the new
> value of the key.
>
> 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? The address of the structure will not change?
What if I move the structure to another place? The map will be broken?

> > 2. I didn't find a function that return all the 'keys' as a vector or
> > sth like that.

>
> Yep. *Or do you think the standard library should include all the
> programs you will ever have to write, so you're left only in choosing
> which program you want and #include it?
>


There is such a method in Java.
I just want to make sure there is no such function in C++.

> > 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 wish I presented my questions clearly.

>
> I wish you have clearer thoughts.
>
> --
> __Pascal Bourguignon__


 
Reply With Quote
 
Michael Oswald
Guest
Posts: n/a
 
      06-23-2008
Lambda wrote:
> the freq is the size() of vector<size_t>.
>
> When I insert the 'term' into the map,
> the map should sort the key by the string 'word'.
>
> And later, I need to sort the 'term' by the 'freq'.
>
> I think I can define two compare functions,
> one for insertion to the map: map<struct term, vector<size_t>, comp1>
> index;
> another for a sort function: sort(terms.begin(), terms.end(), comp2).


[snip]

This sounds to me, like you want someting like boost multiindex
(http://www.boost.org/doc/libs/1_35_0...doc/index.html)


lg,
Michael
 
Reply With Quote
 
Pascal J. Bourguignon
Guest
Posts: n/a
 
      06-23-2008
Lambda <(E-Mail Removed)> 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__
 
Reply With Quote
 
Lambda
Guest
Posts: n/a
 
      06-24-2008
On Jun 24, 12:29*am, (E-Mail Removed) (Pascal J. Bourguignon)
wrote:
> Lambda <(E-Mail Removed)> 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.
>


Won't the vector throw bad_alloc exception?
If so, I can't know there is no free memory available during
execution?

> > 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__


Good idea, i'll try it. Thanks.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Re: How include a large array? Edward A. Falk C Programming 1 04-04-2013 08:07 PM
About typedef -- define the function pointer or define function model? robin liu C Programming 3 04-21-2006 03:26 PM
#define _ and #define __ Brian Takita Ruby 0 01-23-2006 04:34 AM
map whose key_type is the pointer to an object cesco C++ 4 01-17-2006 09:00 PM
How to define a define that defines some defines ? theotyflos C Programming 3 02-19-2004 05:07 PM



Advertisments