Thread: 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

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

Originally Posted by Daved

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

Originally Posted by Darryl

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

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!

Originally Posted by Darryl

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

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.

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.