Updating element in an STL set<>

This is a discussion on Updating element in an STL set<> within the C++ Programming forums, part of the General Programming Boards category; Greetings, I am using a set<> of classes, where one or more members of the structure are used to determine ...

  1. #1
    Registered User
    Join Date
    Jul 2007
    Location
    Naperville, Illinois, USA (near Chicago)
    Posts
    7

    Updating element in an STL set<>

    Greetings,

    I am using a set<> of classes, where one or more members of the structure are used to determine sorting order. But not all members. This happens to work out very nicely when I have have to maintain a table for SNMP--I just define operator<() to be the SNMP ordering function. All that works just fine.

    However, I find that when I need to update an element of the set (not the indices used by operator<) I cannot as I get a const reference or iterator. Fine, that's the way set<> works, by assuming that all parts of the type are used in the sorting function. But it means that doing an update of an existing element is awkward; I must remove the original entry and then insert a new one to replace it. And these 2 versions have exactly the same indices.

    Below is a trimmed down version of the class and an update function. It works, but it just seems like it is unreasonably inefficient to have to:

    1. Find if there is an existing element already
    2. Remove that element
    3. Insert a new element that winds up in exactly the same position!


    So, finally, my question is: Is there a standard paradigm for updating a member of a set<>?

    Code:
    class ENTPHYSICALENTRY : public PHYSICAL_ENTITY_STRUCT
    {
    public:
    	ENTPHYSICALENTRY(void)	// default constructor
    	{
    		initEmptyEntry();
    	}
    
    	~ENTPHYSICALENTRY(void) {}
    
    	void initEmptyEntry(void);
    
    	ENTPHYSICALENTRY(const PHYSICAL_ENTITY_STRUCT &t)
    	{
    		CopyModule(&t);
    	}
    
    	ENTPHYSICALENTRY & operator= (const ENTPHYSICALENTRY &t)
    	{
    		if(&t != this)	// avoid copying to one's self
    		{
    			CopyModule(&t);
    		}
    		return(*this);
    	}
    
    	void CopyModule(const PHYSICAL_ENTITY_STRUCT *t);
    	
    	bool operator< (const ENTPHYSICALENTRY &r) const
    	{
    		if(this->entPhysicalIndex < r.entPhysicalIndex)
    			return(true);
    		return(false);
    	}
    };
    
    typedef std::set<ENTPHYSICALENTRY> ENTPHYSICALSET;
    typedef ENTPHYSICALSET::iterator ENTPHYSICALITER;
    ENTPHYSICALSET entPhysicalTable;	// This is the actual table of entPhysicalEntry
    
    // Insert new entry or replace old entry with more recent version
    STATUS UpdateEntityEntry(ENTPHYSICALENTRY &entry)
    {
    	// insert() will not overwrite, so we must remove and insert if it already exists.
    	// And erase() crashes if the entry doesn't already exist.
    	ENTPHYSICALITER iter = entPhysicalTable.find(entry);
    	if(iter != entPhysicalTable.end())
    	{
    		(void)entPhysicalTable.erase(iter);
    	}
    	pair<ENTPHYSICALITER, bool> insertRetval = entPhysicalTable.insert(entry);
    	if(ASSERT(insertRetval.second))	// second is a bool which is true if the insert succeeded
    	{
    		return ERROR;
    	}
    
    	blah, blah, blah, ...
    }
    I suspect I am just missing something. Suggestions appreciated.

    Thanks.

    -- Harold

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,339
    >> I suspect I am just missing something.
    No, unfortunately you are not.

    The only solution I know of would be to separate the key part of the class from the rest of the data, or duplicate it if it is something small by using a map.

  3. #3
    Registered User
    Join Date
    Jul 2007
    Location
    Naperville, Illinois, USA (near Chicago)
    Posts
    7
    Quote Originally Posted by Daved View Post
    The only solution I know of would be to separate the key part of the class from the rest of the data, or duplicate it if it is something small by using a map.
    Maybe I missed something after all! Are you suggesting using the indices in the set<> to maintain order and mark existence and then use a map<> with that same set of indices to get to the data? I can see how that would work, but now I wonder if it is worthwhile for a small collection (<100 items).

    I don't want to optimize something by adding a lot of complexity when the result might not be measurable...

  4. #4
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    The problem is that set<> guarantees a certain order on insertion, and there is no way to reorder it, say for instance, if you later changed an elements value, therefore, your method of removing and re-adding IS the only way otherwise you could break the ordering.

  5. #5
    Registered User
    Join Date
    Jul 2007
    Location
    Naperville, Illinois, USA (near Chicago)
    Posts
    7
    Quote Originally Posted by Darryl View Post
    The problem is that set<> guarantees a certain order on insertion, and there is no way to reorder it, say for instance, if you later changed an elements value, therefore, your method of removing and re-adding IS the only way otherwise you could break the ordering.
    Understood. I was hoping for a common paradigm for this problem. So far, it appears that I either live with the (perceived) inefficiency in erasing an element and then inserting a new one at the same exact position, or I hold the data indirectly (using a map<> as suggested before).

    To make matters worse, in my application the replacement data is usually identical to the original (it is updated via a polling mechanism). The cost of comparing the data to see if it should be updated is much higher than just replacing it blindly. Sigh.

    It just feels wrong...

  6. #6
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    I think what Daved was saying is dump using set and use map instead since it has a separate key and value. You'd now be able to blindly update value without changing the key.

    For example

    typedef std::map< entPhysicalIndex(type?) , ENTPHYSICALENTRY> ENTPHYSICALMAP;

    now insertion and updating is the same thing

    entPhysicalTable[entry.entPhysicalIndex] = entry;
    Last edited by Darryl; 07-17-2007 at 09:58 AM. Reason: Added example

  7. #7
    Registered User
    Join Date
    Jul 2007
    Location
    Naperville, Illinois, USA (near Chicago)
    Posts
    7
    The problem is that I then lose the SNMP sorting that set<> gives me. I suppose it is a trade-off between sorting every time I need to perform an SNMP operation such as GETNEXT or doing an erase/insert each time I update. SNMP table operations (using GETNEXT, of course) mean I face Order(N**2) time due to sorting.

    For my particular application, I have lots of time during the update part of the cycle but SNMP operations tend to be bursty with an implied time constraint. So, failing to find a better method, I will probably stay with what I have.

    Thanks for your input, guys!

  8. #8
    Tropical Coder Darryl's Avatar
    Join Date
    Mar 2005
    Location
    Cayman Islands
    Posts
    503
    Quote Originally Posted by hbamford View Post
    The problem is that I then lose the SNMP sorting that set<> gives me.
    No you won't, your set was sorted by the entPhysicalindex (albiet you had to extract it first), and now your map will be sorted by the entPhysicalindex, except you've already extracted it. There is no difference.

  9. #9
    Registered User
    Join Date
    Jul 2007
    Location
    Naperville, Illinois, USA (near Chicago)
    Posts
    7
    Quote Originally Posted by Darryl View Post
    No you won't, your set was sorted by the entPhysicalindex (albeit you had to extract it first), and now your map will be sorted by the entPhysicalindex, except you've already extracted it. There is no difference.
    You are correct. For some reason I was thinking that a map<> was unsorted. I guess I was thinking of a hash or something. I guess I'll convert this stuff to using a map<>

  10. #10
    Registered User
    Join Date
    Jan 2005
    Posts
    7,339
    The map does sound like the way to go. And since it is a small collection (<100 items) then any efficiency loss from duplicating the index value would be unnoticable.

    The only thing you have to worry about is not changing the entPhysicalIndex of objects in the map. If you did have to change that part, then you'd have to delete and re-insert with the proper key.

  11. #11
    Registered User
    Join Date
    Jul 2007
    Location
    Naperville, Illinois, USA (near Chicago)
    Posts
    7
    Agreed. Changing the entPhysicalIndex isn't going to happen as that is the unique identifier of the object being represented in the table.

    Thanks for your help.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. STL set max element in O(lgN)
    By Klesk in forum C++ Programming
    Replies: 4
    Last Post: 04-24-2008, 03:41 PM
  2. Replies: 4
    Last Post: 01-05-2008, 10:30 PM
  3. Modify an single passed array element
    By swgh in forum C Programming
    Replies: 3
    Last Post: 08-04-2007, 08:58 AM
  4. Sorting a 2-dimensional array
    By kmoyle73 in forum C++ Programming
    Replies: 3
    Last Post: 05-05-2004, 01:54 PM
  5. Struct *** initialization
    By Saravanan in forum C Programming
    Replies: 20
    Last Post: 10-09-2003, 12:04 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21