Re: Efficiently Extracting Identical Values From A List/Array

From: Ivan Vecerina (NOT_VALID_please_use_contact_webform_at_vecerina.com)
Date: 02/21/05 

Date: Mon, 21 Feb 2005 17:58:01 +0100

"Adam Hartshorne" <oracle3001@yahoo.com> wrote in message
news:cvd1rt$2tu$1@wisteria.csv.warwick.ac.uk...
> Maybe I'm missing something, but using this way
>
> > An "easy" way would be to use:
> > std::multimap< int/*nodeIndex*/, std::vector<int/*arrayIndex*/> >
> myList;
NB: I actually meant to write std::map< .... >

> > // for each index:
> > myList[aNodeIndex].push_back( anArrayIndex );
>
> will give me the list of lists, but I only want to consider those nodes
> which are mentioned multiple times in the storage array. The above will
> form me the list of lists, based upon the node indices and for each of
> those a list of array indices.
>
> I would then have to search / sort the whole MyList to isolate the
> elements in the new MyList that had multiple values stored.
> Is that correct?
Yes: sorting first tends to be the fastest way to find
identical values in a list.

This said, in your case, aNodeIndex values are in a know 0-based
interval. Because of that, you could probably use a faster approach:
 // initial map filled with -1 to say no ArrayIndex points to that node
 std::vector<int> nodeToFirstInd( maxNodeIndex, -1 );

 // this will store only nodes with multiple indices
 std::map< int/*nodeIndex*/, std::vector<int/*arrayIndex*/ > > multiLinked;

 for(....)// for each arrayIndex, nodeIndex pair:
 {
   if( nodeToFirstInd[nodeIndex]==-1 )
     nodeToFirstInd[nodeIndex] = arrayIndex; // mark node as 'used'
   else {
     std::vector<int/*arrayIndex*/ >& list = multiLinked[nodeIndex];
     if( list.empty() ) // put the initial item in
        list.push_back( nodeToFirstInd[nodeIndex] )
     list.push_back( arrayIndex ); // add the new value index
   }
 }

 // now multiLinked contains what you want

Sorry the code samples are a mess - just written in a rush.
I hope it is understandable and helpful, though.

Ivan 

-- 
http://ivan.vecerina.com/contact/?subject=NG_POST <- email contact form

Relevant Pages

  • [Full-Disclosure] Re: Full-Disclosure digest, Vol 1 #1933 - 20 msgs
    ... read from multiple peoples articles that it isn't this kind of bug. ... > that about how bad Windows sucks from people who don't know enough about how ... I don't do it out in the public lists like ... >>because you have a bug up your bum about it and work to prove that stance. ...
    (Full-Disclosure)
  • Re: Difficulty with List Selection and New Records
    ... but one Patent can be assigned to multiple ... Doug Steele, Microsoft Access MVP ... I need to create a list that allows multiple selections. ... successfully created lists that allow multiple selections. ...
    (microsoft.public.access.gettingstarted)
  • Re: MOSS 2007 Out of the Box Workflows Broken
    ... I will add that choosing the Allow Multiple Seletions also prevents users ... from editing lists in datasheet view, exporting lists to excel, and using ... that field in custom workflows through SharePoint Designer. ... theworkflowuses the default Task content type to manageworkflowtasks we ...
    (microsoft.public.sharepoint.portalserver.development)
  • Re: Multiple criteria with multiple results in one cell
    ... multiple criteria. ... firstcell is the first cell of the output array, ... companies in a separate column on that worksheet based on a pay rate table ... drop-down lists on her site, but in those cases, it requires either having a ...
    (microsoft.public.excel.worksheet.functions)
  • Re: Lookup function/sum function
    ... the list multiple times and don't have multiple releases? ... It also lists the master release which is the entire quantity ordered ... So what I want to do is look up all the sales for each month like I did from ... to total up on a different summary worksheet by month. ...
    (microsoft.public.excel.misc)