Removing the duplicates in the multiset (bit urgent)

[pdk5]

Hello,

I have the following map. I changed the set to multiset, as I need to store, the cell, even if the distance is the same.

struct TACNeighbourData
{
    int m_CellKey;
	double m_Distance;
	int m_HOCount;
	std::string m_CellID;

	TACNeighbourData()
	{
		m_Instancecounter++;
	}

	TACNeighbourData(const TACNeighbourData& rother):
	m_CellKey(rother.m_CellKey),
	m_Distance(rother.m_Distance),
	m_HOCount(rother.m_HOCount),
	m_CellID(rother.m_CellID)
	{
		m_Instancecounter++;
	}

	~TACNeighbourData()
	{
		m_Instancecounter--;
	}

	bool operator<(const TACNeighbourData& rother) const
	{
		if (bIsHO)
			return m_HOCount < rother.m_HOCount;
		else
			return m_Distance < rother.m_Distance;
	}

	static int m_Instancecounter;
};


	std::map<int, std::multiset<TACNeighbourData> >	m_SiteKeyToNeighbourKeys;

Now the map is having values like this say:

{siteid=1 , { cellid= 100, distance=0, hocnt=0},
{ cellid=100, distance=0, hocnt=0}
{cellid=200, distance=0, hocnt=0}
{cellid=300, distance=0, hocnt=0}
}

i want to see something like this::


{siteid=1 , { cellid= 100, distance=0, hocnt=0},
{cellid=200, distance=0, hocnt=0}
{cellid=300, distance=0, hocnt=0}
}

I had not tested everything before , so finding this issue at last moment. So im trying to fix at last monent, so any help is much appreciated.

Basically, i am populating in the ascending order of distance (but i also want to populate if the distance are same), so i used the multiset. Hope this is ok. As the set doesnot populate same values, it overwrites it.

thanks a lot
pdk

[pdk5]

I think i found a way, I just tried to check before the insertion, if that element is already present,

struct find_by_cellkey {
    find_by_cellkey(const int & cellkey) : cellkey(cellkey) {}
    bool operator()(const TACNeighbourData & neigh) {
        return neigh.m_CellKey == cellkey;
    }
private:
    int cellkey;
};

Then somewhere in the code:

							// Also check if this cell id is already listed 
							std::multiset<TACNeighbourData>::iterator result = 
								std::find_if(found->second.begin(), found->second.end(), find_by_cellkey(sneigh.m_CellKey));

							if (result == found->second.end())
							{
								// no match
								found->second.insert(sneigh);
							}

						}

[2kaud]

Whilst this solution will prevent the non-required duplicate entries, it will have an adverse effect on performance - as the multiset is effectively traversed twice - once to see if the cell doesn't exist and then again to find the position for insertion. For a few entries, this won't be noticeable but for a large number of entries it could well be noticeable.

I see that you want the set data sorted by distance. What about where you're trying to insert an item with an existing cell but a shorter distance? Won't this now not get inserted as the cell already exists ???

Instead of multiset, don't you want a map with key cell and value multiset of {distance, hocnt} sorted by distance?

Something like:

struct TACData {
    double m_Distance;
    int m_HOCount;
};

std::map<int, std::map<std::string, std::multiset<TACData> > > m_SiteKeyToNeighbourKeys;

where TACData is sorted by m_Distance.

The key to the outer map is siteid and that of the inner map is m_CellKey.

[pdk5]

Thanks a lot kaud for the inputs, I'll try to change that and make efficient as you suggested. The initial design didnot consider all possibilities