Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > STL container for sorted items

Reply
Thread Tools

STL container for sorted items

 
 
Hunk
Guest
Posts: n/a
 
      03-14-2007
Would like some advice on the fillowing
I have a sorted list of items on which i require to search and
retrieve the said item and also modify an item based on its identity.
I think an Map stl container would be most suited. Am i correct in my
assumptions
Problem
Reocrds are already stored with a unique identity in a binary
format.The structure is roughly

----------------------
Record Count
--------------------
Record1 -------------------------------------- String Identifier
------------------
--------------------
Obj
pointer
Record 2
------------------
Record n
--------------------

-------------
Obj1
------------
Obj2
------------

I propose to have a map of <strings , Obj Pointer>. The map would be
initialised with the file item initially and then routines would be
provided to search an item based on the identifier and update an item
based on the identifier.
Also if dealing with a file stored in memory , is it advisable to use
a STL in the first place instead of say directly using address
manipulations to get to the items since the identifiers are already
sorted?

 
Reply With Quote
 
 
 
 
Hunk
Guest
Posts: n/a
 
      03-14-2007
On Mar 14, 4:16 pm, "Hunk" <(E-Mail Removed)> wrote:
> Would like some advice on the fillowing
> I have a sorted list of items on which i require to search and
> retrieve the said item and also modify an item based on its identity.
> I think an Map stl container would be most suited. Am i correct in my
> assumptions
> Problem
> Reocrds are already stored with a unique identity in a binary
> format.The structure is roughly
>
> ----------------------
> Record Count
> --------------------
> Record1 -------------------------------------- String Identifier
> ------------------
> --------------------
> Obj
> pointer
> Record 2
> ------------------
> Record n
> --------------------
>
> -------------
> Obj1
> ------------
> Obj2
> ------------
>
> I propose to have a map of <strings , Obj Pointer>. The map would be
> initialised with the file item initially and then routines would be
> provided to search an item based on the identifier and update an item
> based on the identifier.
> Also if dealing with a file stored in memory , is it advisable to use
> a STL in the first place instead of say directly using address
> manipulations to get to the items since the identifiers are already
> sorted?


I think the formattin above is screwed up.I'm pasting the format once
again
----------------------
Record Count
--------------------
Record1
Record 2
------------------
Record n
--------------------


-------------
Obj1
------------
Obj2
------------

Each Record is made up of
Identity (unique)
Obj Pointer (pointer to objects obj1,ibj2)




 
Reply With Quote
 
 
 
 
coosa
Guest
Posts: n/a
 
      03-14-2007
On Mar 14, 7:23 pm, "Hunk" <(E-Mail Removed)> wrote:
> On Mar 14, 4:16 pm, "Hunk" <(E-Mail Removed)> wrote:
>
>
>
> > Would like some advice on the fillowing
> > I have a sorted list of items on which i require to search and
> > retrieve the said item and also modify an item based on its identity.
> > I think an Map stl container would be most suited. Am i correct in my
> > assumptions
> > Problem
> > Reocrds are already stored with a unique identity in a binary
> > format.The structure is roughly

>
> > ----------------------
> > Record Count
> > --------------------
> > Record1 -------------------------------------- String Identifier
> > ------------------
> > --------------------
> > Obj
> > pointer
> > Record 2
> > ------------------
> > Record n
> > --------------------

>
> > -------------
> > Obj1
> > ------------
> > Obj2
> > ------------

>
> > I propose to have a map of <strings , Obj Pointer>. The map would be
> > initialised with the file item initially and then routines would be
> > provided to search an item based on the identifier and update an item
> > based on the identifier.
> > Also if dealing with a file stored in memory , is it advisable to use
> > a STL in the first place instead of say directly using address
> > manipulations to get to the items since the identifiers are already
> > sorted?

>
> I think the formattin above is screwed up.I'm pasting the format once
> again
> ----------------------
> Record Count
> --------------------
> Record1
> Record 2
> ------------------
> Record n
> --------------------
>
> -------------
> Obj1
> ------------
> Obj2
> ------------
>
> Each Record is made up of
> Identity (unique)
> Obj Pointer (pointer to objects obj1,ibj2)


I believe a Set is more appropriate;
The sorting itself should be made in such that the < operator should
be overloaded.
For instance, since sorted elements is important to you, you could
probably create a class which contains both the identity and object
content; in that class you should overload the less operator compared
to the identity.

Regards

 
Reply With Quote
 
coosa
Guest
Posts: n/a
 
      03-14-2007
On Mar 15, 12:30 am, "coosa" <(E-Mail Removed)> wrote:
> On Mar 14, 7:23 pm, "Hunk" <(E-Mail Removed)> wrote:
>
>
>
> > On Mar 14, 4:16 pm, "Hunk" <(E-Mail Removed)> wrote:

>
> > > Would like some advice on the fillowing
> > > I have a sorted list of items on which i require to search and
> > > retrieve the said item and also modify an item based on its identity.
> > > I think an Map stl container would be most suited. Am i correct in my
> > > assumptions
> > > Problem
> > > Reocrds are already stored with a unique identity in a binary
> > > format.The structure is roughly

>
> > > ----------------------
> > > Record Count
> > > --------------------
> > > Record1 -------------------------------------- String Identifier
> > > ------------------
> > > --------------------
> > > Obj
> > > pointer
> > > Record 2
> > > ------------------
> > > Record n
> > > --------------------

>
> > > -------------
> > > Obj1
> > > ------------
> > > Obj2
> > > ------------

>
> > > I propose to have a map of <strings , Obj Pointer>. The map would be
> > > initialised with the file item initially and then routines would be
> > > provided to search an item based on the identifier and update an item
> > > based on the identifier.
> > > Also if dealing with a file stored in memory , is it advisable to use
> > > a STL in the first place instead of say directly using address
> > > manipulations to get to the items since the identifiers are already
> > > sorted?

>
> > I think the formattin above is screwed up.I'm pasting the format once
> > again
> > ----------------------
> > Record Count
> > --------------------
> > Record1
> > Record 2
> > ------------------
> > Record n
> > --------------------

>
> > -------------
> > Obj1
> > ------------
> > Obj2
> > ------------

>
> > Each Record is made up of
> > Identity (unique)
> > Obj Pointer (pointer to objects obj1,ibj2)

>
> I believe a Set is more appropriate;
> The sorting itself should be made in such that the < operator should
> be overloaded.
> For instance, since sorted elements is important to you, you could
> probably create a class which contains both the identity and object
> content; in that class you should overload the less operator compared
> to the identity.
>
> Regards


Assuming the class is called A and it contains id as int and the
pointers to your objects;
Hence:
typedef set <A, less<A>> A_set;
..
..
..
For your A class definition:
bool A:perator < (const A & a) const {return this->id < a.id;}
now A_set s;
s takes simply an object of A and it is ensured that all the object of
A inserted into the set are sorted in ascending order based on the id
inside each object of A.

Hope it helps

 
Reply With Quote
 
Hunk
Guest
Posts: n/a
 
      03-15-2007
On Mar 14, 9:40 pm, "coosa" <(E-Mail Removed)> wrote:
> On Mar 15, 12:30 am, "coosa" <(E-Mail Removed)> wrote:
>
>
>
>
>
> > On Mar 14, 7:23 pm, "Hunk" <(E-Mail Removed)> wrote:

>
> > > On Mar 14, 4:16 pm, "Hunk" <(E-Mail Removed)> wrote:

>
> > > > Would like some advice on the fillowing
> > > > I have a sorted list of items on which i require to search and
> > > > retrieve the said item and also modify an item based on its identity.
> > > > I think an Map stl container would be most suited. Am i correct in my
> > > > assumptions
> > > > Problem
> > > > Reocrds are already stored with a unique identity in a binary
> > > > format.The structure is roughly

>
> > > > ----------------------
> > > > Record Count
> > > > --------------------
> > > > Record1 -------------------------------------- String Identifier
> > > > ------------------
> > > > --------------------
> > > > Obj
> > > > pointer
> > > > Record 2
> > > > ------------------
> > > > Record n
> > > > --------------------

>
> > > > -------------
> > > > Obj1
> > > > ------------
> > > > Obj2
> > > > ------------

>
> > > > I propose to have a map of <strings , Obj Pointer>. The map would be
> > > > initialised with the file item initially and then routines would be
> > > > provided to search an item based on the identifier and update an item
> > > > based on the identifier.
> > > > Also if dealing with a file stored in memory , is it advisable to use
> > > > a STL in the first place instead of say directly using address
> > > > manipulations to get to the items since the identifiers are already
> > > > sorted?

>
> > > I think the formattin above is screwed up.I'm pasting the format once
> > > again
> > > ----------------------
> > > Record Count
> > > --------------------
> > > Record1
> > > Record 2
> > > ------------------
> > > Record n
> > > --------------------

>
> > > -------------
> > > Obj1
> > > ------------
> > > Obj2
> > > ------------

>
> > > Each Record is made up of
> > > Identity (unique)
> > > Obj Pointer (pointer to objects obj1,ibj2)

>
> > I believe a Set is more appropriate;
> > The sorting itself should be made in such that the < operator should
> > be overloaded.
> > For instance, since sorted elements is important to you, you could
> > probably create a class which contains both the identity and object
> > content; in that class you should overload the less operator compared
> > to the identity.

>
> > Regards

>
> Assuming the class is called A and it contains id as int and the
> pointers to your objects;
> Hence:
> typedef set <A, less<A>> A_set;
> .
> .
> .
> For your A class definition:
> bool A:perator < (const A & a) const {return this->id < a.id;}
> now A_set s;
> s takes simply an object of A and it is ensured that all the object of
> A inserted into the set are sorted in ascending order based on the id
> inside each object of A.
>
> Hope it helps- Hide quoted text -
>
> - Show quoted text -


How would a set help in returning an object compared to a map?
Since the items given to me are already sorted, and i would have to
retrieve an object based on its identity, wouldnt map be more useful
as in the set i would have to decode the object first?

 
Reply With Quote
 
coosa
Guest
Posts: n/a
 
      03-16-2007
On Mar 15, 1:17 pm, "Hunk" <(E-Mail Removed)> wrote:
> On Mar 14, 9:40 pm, "coosa" <(E-Mail Removed)> wrote:
>
>
>
> > On Mar 15, 12:30 am, "coosa" <(E-Mail Removed)> wrote:

>
> > > On Mar 14, 7:23 pm, "Hunk" <(E-Mail Removed)> wrote:

>
> > > > On Mar 14, 4:16 pm, "Hunk" <(E-Mail Removed)> wrote:

>
> > > > > Would like some advice on the fillowing
> > > > > I have a sorted list of items on which i require to search and
> > > > > retrieve the said item and also modify an item based on its identity.
> > > > > I think an Map stl container would be most suited. Am i correct in my
> > > > > assumptions
> > > > > Problem
> > > > > Reocrds are already stored with a unique identity in a binary
> > > > > format.The structure is roughly

>
> > > > > ----------------------
> > > > > Record Count
> > > > > --------------------
> > > > > Record1 -------------------------------------- String Identifier
> > > > > ------------------
> > > > > --------------------
> > > > > Obj
> > > > > pointer
> > > > > Record 2
> > > > > ------------------
> > > > > Record n
> > > > > --------------------

>
> > > > > -------------
> > > > > Obj1
> > > > > ------------
> > > > > Obj2
> > > > > ------------

>
> > > > > I propose to have a map of <strings , Obj Pointer>. The map would be
> > > > > initialised with the file item initially and then routines would be
> > > > > provided to search an item based on the identifier and update an item
> > > > > based on the identifier.
> > > > > Also if dealing with a file stored in memory , is it advisable to use
> > > > > a STL in the first place instead of say directly using address
> > > > > manipulations to get to the items since the identifiers are already
> > > > > sorted?

>
> > > > I think the formattin above is screwed up.I'm pasting the format once
> > > > again
> > > > ----------------------
> > > > Record Count
> > > > --------------------
> > > > Record1
> > > > Record 2
> > > > ------------------
> > > > Record n
> > > > --------------------

>
> > > > -------------
> > > > Obj1
> > > > ------------
> > > > Obj2
> > > > ------------

>
> > > > Each Record is made up of
> > > > Identity (unique)
> > > > Obj Pointer (pointer to objects obj1,ibj2)

>
> > > I believe a Set is more appropriate;
> > > The sorting itself should be made in such that the < operator should
> > > be overloaded.
> > > For instance, since sorted elements is important to you, you could
> > > probably create a class which contains both the identity and object
> > > content; in that class you should overload the less operator compared
> > > to the identity.

>
> > > Regards

>
> > Assuming the class is called A and it contains id as int and the
> > pointers to your objects;
> > Hence:
> > typedef set <A, less<A>> A_set;
> > .
> > .
> > .
> > For your A class definition:
> > bool A:perator < (const A & a) const {return this->id < a.id;}
> > now A_set s;
> > s takes simply an object of A and it is ensured that all the object of
> > A inserted into the set are sorted in ascending order based on the id
> > inside each object of A.

>
> > Hope it helps- Hide quoted text -

>
> > - Show quoted text -

>
> How would a set help in returning an object compared to a map?
> Since the items given to me are already sorted, and i would have to
> retrieve an object based on its identity, wouldnt map be more useful
> as in the set i would have to decode the object first?


Yes, map would be a better choice assuming you don't have to add any
more to your collection;
In simple words, if your application requires later that you add more
into your collection which needs to be always sorted, then I suggest
using a set; however, if you no longer need to add and the current
data you have is already sorted before inserting into your new
collection, then a map is a good choice for fast lookup, even though
it doesn't play role in maps whether the keys are sorted or not (some
one corrects me if I'm wrong).

 
Reply With Quote
 
coosa
Guest
Posts: n/a
 
      03-16-2007
On Mar 16, 9:06 am, "coosa" <(E-Mail Removed)> wrote:
> On Mar 15, 1:17 pm, "Hunk" <(E-Mail Removed)> wrote:
>
>
>
> > On Mar 14, 9:40 pm, "coosa" <(E-Mail Removed)> wrote:

>
> > > On Mar 15, 12:30 am, "coosa" <(E-Mail Removed)> wrote:

>
> > > > On Mar 14, 7:23 pm, "Hunk" <(E-Mail Removed)> wrote:

>
> > > > > On Mar 14, 4:16 pm, "Hunk" <(E-Mail Removed)> wrote:

>
> > > > > > Would like some advice on the fillowing
> > > > > > I have a sorted list of items on which i require to search and
> > > > > > retrieve the said item and also modify an item based on its identity.
> > > > > > I think an Map stl container would be most suited. Am i correct in my
> > > > > > assumptions
> > > > > > Problem
> > > > > > Reocrds are already stored with a unique identity in a binary
> > > > > > format.The structure is roughly

>
> > > > > > ----------------------
> > > > > > Record Count
> > > > > > --------------------
> > > > > > Record1 -------------------------------------- String Identifier
> > > > > > ------------------
> > > > > > --------------------
> > > > > > Obj
> > > > > > pointer
> > > > > > Record 2
> > > > > > ------------------
> > > > > > Record n
> > > > > > --------------------

>
> > > > > > -------------
> > > > > > Obj1
> > > > > > ------------
> > > > > > Obj2
> > > > > > ------------

>
> > > > > > I propose to have a map of <strings , Obj Pointer>. The map would be
> > > > > > initialised with the file item initially and then routines would be
> > > > > > provided to search an item based on the identifier and update an item
> > > > > > based on the identifier.
> > > > > > Also if dealing with a file stored in memory , is it advisable to use
> > > > > > a STL in the first place instead of say directly using address
> > > > > > manipulations to get to the items since the identifiers are already
> > > > > > sorted?

>
> > > > > I think the formattin above is screwed up.I'm pasting the format once
> > > > > again
> > > > > ----------------------
> > > > > Record Count
> > > > > --------------------
> > > > > Record1
> > > > > Record 2
> > > > > ------------------
> > > > > Record n
> > > > > --------------------

>
> > > > > -------------
> > > > > Obj1
> > > > > ------------
> > > > > Obj2
> > > > > ------------

>
> > > > > Each Record is made up of
> > > > > Identity (unique)
> > > > > Obj Pointer (pointer to objects obj1,ibj2)

>
> > > > I believe a Set is more appropriate;
> > > > The sorting itself should be made in such that the < operator should
> > > > be overloaded.
> > > > For instance, since sorted elements is important to you, you could
> > > > probably create a class which contains both the identity and object
> > > > content; in that class you should overload the less operator compared
> > > > to the identity.

>
> > > > Regards

>
> > > Assuming the class is called A and it contains id as int and the
> > > pointers to your objects;
> > > Hence:
> > > typedef set <A, less<A>> A_set;
> > > .
> > > .
> > > .
> > > For your A class definition:
> > > bool A:perator < (const A & a) const {return this->id < a.id;}
> > > now A_set s;
> > > s takes simply an object of A and it is ensured that all the object of
> > > A inserted into the set are sorted in ascending order based on the id
> > > inside each object of A.

>
> > > Hope it helps- Hide quoted text -

>
> > > - Show quoted text -

>
> > How would a set help in returning an object compared to a map?
> > Since the items given to me are already sorted, and i would have to
> > retrieve an object based on its identity, wouldnt map be more useful
> > as in the set i would have to decode the object first?

>
> Yes, map would be a better choice assuming you don't have to add any
> more to your collection;
> In simple words, if your application requires later that you add more
> into your collection which needs to be always sorted, then I suggest
> using a set; however, if you no longer need to add and the current
> data you have is already sorted before inserting into your new
> collection, then a map is a good choice for fast lookup, even though
> it doesn't play role in maps whether the keys are sorted or not (some
> one corrects me if I'm wrong).


But I just recalled ...
Why not using hash_map?
I guess it's the fastest way to retrieve elements by a certain key
Check http://www.sgi.com/tech/stl/hash_map.html or by MSDN
http://msdn2.microsoft.com/en-us/lib...6z(VS.80).aspx for more
reference.

 
Reply With Quote
 
Hunk
Guest
Posts: n/a
 
      03-16-2007
On Mar 16, 6:21 am, "coosa" <(E-Mail Removed)> wrote:
> On Mar 16, 9:06 am, "coosa" <(E-Mail Removed)> wrote:
>
>
>
>
>
> > On Mar 15, 1:17 pm, "Hunk" <(E-Mail Removed)> wrote:

>
> > > On Mar 14, 9:40 pm, "coosa" <(E-Mail Removed)> wrote:

>
> > > > On Mar 15, 12:30 am, "coosa" <(E-Mail Removed)> wrote:

>
> > > > > On Mar 14, 7:23 pm, "Hunk" <(E-Mail Removed)> wrote:

>
> > > > > > On Mar 14, 4:16 pm, "Hunk" <(E-Mail Removed)> wrote:

>
> > > > > > > Would like some advice on the fillowing
> > > > > > > I have a sorted list of items on which i require to search and
> > > > > > > retrieve the said item and also modify an item based on its identity.
> > > > > > > I think an Map stl container would be most suited. Am i correct in my
> > > > > > > assumptions
> > > > > > > Problem
> > > > > > > Reocrds are already stored with a unique identity in a binary
> > > > > > > format.The structure is roughly

>
> > > > > > > ----------------------
> > > > > > > Record Count
> > > > > > > --------------------
> > > > > > > Record1 -------------------------------------- String Identifier
> > > > > > > ------------------
> > > > > > > --------------------
> > > > > > > Obj
> > > > > > > pointer
> > > > > > > Record 2
> > > > > > > ------------------
> > > > > > > Record n
> > > > > > > --------------------

>
> > > > > > > -------------
> > > > > > > Obj1
> > > > > > > ------------
> > > > > > > Obj2
> > > > > > > ------------

>
> > > > > > > I propose to have a map of <strings , Obj Pointer>. The map would be
> > > > > > > initialised with the file item initially and then routines would be
> > > > > > > provided to search an item based on the identifier and update an item
> > > > > > > based on the identifier.
> > > > > > > Also if dealing with a file stored in memory , is it advisable to use
> > > > > > > a STL in the first place instead of say directly using address
> > > > > > > manipulations to get to the items since the identifiers are already
> > > > > > > sorted?

>
> > > > > > I think the formattin above is screwed up.I'm pasting the format once
> > > > > > again
> > > > > > ----------------------
> > > > > > Record Count
> > > > > > --------------------
> > > > > > Record1
> > > > > > Record 2
> > > > > > ------------------
> > > > > > Record n
> > > > > > --------------------

>
> > > > > > -------------
> > > > > > Obj1
> > > > > > ------------
> > > > > > Obj2
> > > > > > ------------

>
> > > > > > Each Record is made up of
> > > > > > Identity (unique)
> > > > > > Obj Pointer (pointer to objects obj1,ibj2)

>
> > > > > I believe a Set is more appropriate;
> > > > > The sorting itself should be made in such that the < operator should
> > > > > be overloaded.
> > > > > For instance, since sorted elements is important to you, you could
> > > > > probably create a class which contains both the identity and object
> > > > > content; in that class you should overload the less operator compared
> > > > > to the identity.

>
> > > > > Regards

>
> > > > Assuming the class is called A and it contains id as int and the
> > > > pointers to your objects;
> > > > Hence:
> > > > typedef set <A, less<A>> A_set;
> > > > .
> > > > .
> > > > .
> > > > For your A class definition:
> > > > bool A:perator < (const A & a) const {return this->id < a.id;}
> > > > now A_set s;
> > > > s takes simply an object of A and it is ensured that all the object of
> > > > A inserted into the set are sorted in ascending order based on the id
> > > > inside each object of A.

>
> > > > Hope it helps- Hide quoted text -

>
> > > > - Show quoted text -

>
> > > How would a set help in returning an object compared to a map?
> > > Since the items given to me are already sorted, and i would have to
> > > retrieve an object based on its identity, wouldnt map be more useful
> > > as in the set i would have to decode the object first?

>
> > Yes, map would be a better choice assuming you don't have to add any
> > more to your collection;
> > In simple words, if your application requires later that you add more
> > into your collection which needs to be always sorted, then I suggest
> > using a set; however, if you no longer need to add and the current
> > data you have is already sorted before inserting into your new
> > collection, then a map is a good choice for fast lookup, even though
> > it doesn't play role in maps whether the keys are sorted or not (some
> > one corrects me if I'm wrong).

>
> But I just recalled ...
> Why not using hash_map?
> I guess it's the fastest way to retrieve elements by a certain key
> Checkhttp://www.sgi.com/tech/stl/hash_map.htmlor by MSDNhttp://msdn2.microsoft.com/en-us/library/6x7w9f6z(VS.80).aspxfor more
> reference.- Hide quoted text -
>
> - Show quoted text -


The more i think of it i feel we should use a vector with a pair
instead of any associative container. The reasons as explained in item
23 in Effective Stl by Scott meyers says that associative containers
would lead to page faults and more memory due to the fact that they
use 3 pointers internally and they are not stored in a contiguos
location in memory.
So when the decision is
Insert elements
Sort Elements -- skip this in my case
Look up elements
the best decision is to use a pair in a vector to achieve the same
thing as a map<string,structure> would do.
Do let me know if i'm wrong in my explanations

 
Reply With Quote
 
Lionel B
Guest
Posts: n/a
 
      03-16-2007
On Fri, 16 Mar 2007 04:59:02 -0700, Hunk wrote:

> On Mar 16, 6:21 am, "coosa" <(E-Mail Removed)> wrote:
>> On Mar 16, 9:06 am, "coosa" <(E-Mail Removed)> wrote:
>>
>>
>>
>>
>>
>> > On Mar 15, 1:17 pm, "Hunk" <(E-Mail Removed)> wrote:

>>
>> > > On Mar 14, 9:40 pm, "coosa" <(E-Mail Removed)> wrote:

>>
>> > > > On Mar 15, 12:30 am, "coosa" <(E-Mail Removed)> wrote:

>>
>> > > > > On Mar 14, 7:23 pm, "Hunk" <(E-Mail Removed)> wrote:

>>
>> > > > > > On Mar 14, 4:16 pm, "Hunk" <(E-Mail Removed)> wrote:

>>
>> > > > > > > Would like some advice on the fillowing
>> > > > > > > I have a sorted list of items on which i require to search and
>> > > > > > > retrieve the said item and also modify an item based on its identity.
>> > > > > > > I think an Map stl container would be most suited. Am i correct in my
>> > > > > > > assumptions


[snip]

>> > Yes, map would be a better choice assuming you don't have to add any
>> > more to your collection;
>> > In simple words, if your application requires later that you add more
>> > into your collection which needs to be always sorted, then I suggest
>> > using a set; however, if you no longer need to add and the current
>> > data you have is already sorted before inserting into your new
>> > collection, then a map is a good choice for fast lookup, even though
>> > it doesn't play role in maps whether the keys are sorted or not (some
>> > one corrects me if I'm wrong).

>>
>> But I just recalled ...
>> Why not using hash_map?
>> I guess it's the fastest way to retrieve elements by a certain key
>> Check http://www.sgi.com/tech/stl/hash_map.htmlor by
>> MSDNhttp://msdn2.microsoft.com/en-us/library/6x7w9f6z(VS.80).aspxfor
>> more reference.

>
> The more i think of it i feel we should use a vector with a pair instead
> of any associative container. The reasons as explained in item 23 in
> Effective Stl by Scott meyers says that associative containers would
> lead to page faults and more memory due to the fact that they use 3
> pointers internally and they are not stored in a contiguos location in
> memory.
> So when the decision is
> Insert elements
> Sort Elements -- skip this in my case Look up elements
> the best decision is to use a pair in a vector to achieve the same thing
> as a map<string,structure> would do. Do let me know if i'm wrong in my
> explanations


My inclination would be to use the data structure that most closely
reflects the problem you are addressing; in your case this sounds like a
map. You won't know until you try it whether efficiency is an issue. If it
is, you could try other ideas, such as a vector of pairs.

--
Lionel B
 
Reply With Quote
 
coosa
Guest
Posts: n/a
 
      03-16-2007
On Mar 16, 8:20 pm, Lionel B <(E-Mail Removed)> wrote:
> On Fri, 16 Mar 2007 04:59:02 -0700, Hunk wrote:
> > On Mar 16, 6:21 am, "coosa" <(E-Mail Removed)> wrote:
> >> On Mar 16, 9:06 am, "coosa" <(E-Mail Removed)> wrote:

>
> >> > On Mar 15, 1:17 pm, "Hunk" <(E-Mail Removed)> wrote:

>
> >> > > On Mar 14, 9:40 pm, "coosa" <(E-Mail Removed)> wrote:

>
> >> > > > On Mar 15, 12:30 am, "coosa" <(E-Mail Removed)> wrote:

>
> >> > > > > On Mar 14, 7:23 pm, "Hunk" <(E-Mail Removed)> wrote:

>
> >> > > > > > On Mar 14, 4:16 pm, "Hunk" <(E-Mail Removed)> wrote:

>
> >> > > > > > > Would like some advice on the fillowing
> >> > > > > > > I have a sorted list of items on which i require to search and
> >> > > > > > > retrieve the said item and also modify an item based on its identity.
> >> > > > > > > I think an Map stl container would be most suited. Am i correct in my
> >> > > > > > > assumptions

>
> [snip]
>
>
>
> >> > Yes, map would be a better choice assuming you don't have to add any
> >> > more to your collection;
> >> > In simple words, if your application requires later that you add more
> >> > into your collection which needs to be always sorted, then I suggest
> >> > using a set; however, if you no longer need to add and the current
> >> > data you have is already sorted before inserting into your new
> >> > collection, then a map is a good choice for fast lookup, even though
> >> > it doesn't play role in maps whether the keys are sorted or not (some
> >> > one corrects me if I'm wrong).

>
> >> But I just recalled ...
> >> Why not using hash_map?
> >> I guess it's the fastest way to retrieve elements by a certain key
> >> Checkhttp://www.sgi.com/tech/stl/hash_map.htmlorby
> >> MSDNhttp://msdn2.microsoft.com/en-us/library/6x7w9f6z(VS.80).aspxfor
> >> more reference.

>
> > The more i think of it i feel we should use a vector with a pair instead
> > of any associative container. The reasons as explained in item 23 in
> > Effective Stl by Scott meyers says that associative containers would
> > lead to page faults and more memory due to the fact that they use 3
> > pointers internally and they are not stored in a contiguos location in
> > memory.
> > So when the decision is
> > Insert elements
> > Sort Elements -- skip this in my case Look up elements
> > the best decision is to use a pair in a vector to achieve the same thing
> > as a map<string,structure> would do. Do let me know if i'm wrong in my
> > explanations

>
> My inclination would be to use the data structure that most closely
> reflects the problem you are addressing; in your case this sounds like a
> map. You won't know until you try it whether efficiency is an issue. If it
> is, you could try other ideas, such as a vector of pairs.
>
> --
> Lionel B


Agree with you; a map or precisely a hashed map.
Trust me on not using vectors; I've worked on the netflix competition
with a dataset containing over 100 millions of ratings and I used Java
for it, but it won't play a big role if I used C++; for some
processing the code ran and lasted around 2-3 days to finish; when I
decided to switch to HashMap it took less than 6 hours to process.
Vectors vs Maps, I also have the book of scott meyers and it's a great
one and I don't see a contradiction for using Maps or hashed maps; you
worry much about retrieving the elements fast and I guess Maps are
best suited for that.
Let me repeat again:
You need to ensure sorted elements -> sets
you need uniqueness -> sets and maps
you need fast lookup -> maps and hashes
you need insertions and deletions from the beginning, ending or middle
of container -> lists
you need random access -> vectors
See what's most crucial for your application and decide for a
container.

Good luck

 
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
sorted container Gary Wessle C++ 7 03-07-2007 03:20 PM
container inside container in stl wolverine C++ 2 07-24-2006 03:08 PM
Copy elements from one STL container to another STL container Marko.Cain.23@gmail.com C++ 4 02-16-2006 05:03 PM
stl container that store unique items marcwentink@hotmail.com C++ 6 11-18-2005 12:02 PM
STL: container's values setup by another container Maitre Bart C++ 2 02-11-2004 12:11 AM



Advertisments