?
Solved

Compare two std multimaps for same element

Posted on 2008-09-30
6
Medium Priority
?
462 Views
Last Modified: 2010-04-21
Is there a quick and dirty way to compare two std::multimap to find an identical element?
0
Comment
Question by:steenpat
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
6 Comments
 
LVL 53

Expert Comment

by:Infinity08
ID: 22609807
>> to find an identical element?

Do you mean any identical element ? Or a specific one ?
0
 

Author Comment

by:steenpat
ID: 22610432
I'm storing a map of directories and the files underneath them.
So if I have a map that contains [0] - "Files", "readme.txt"
and I have another map that contains the same item, I want to be able to find this out, so I know if the src directory and destination directory, files, etc are going to be the same and alert the user before copying files over.
0
 

Author Comment

by:steenpat
ID: 22610443
But yeah any identical element will do.
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 53

Accepted Solution

by:
Infinity08 earned 1000 total points
ID: 22612434
>> But yeah any identical element will do.

From your explanation, it seems you need all identical items, not just one (any).


To answer your question : I wouldn't use a multimap for this. Something like this might be more appropriate :

        typedef std::string Directory;
        typedef std::string File;
        typedef std::map<Directory, std::set<File> > FileList;

Below is some example code of how you could do it (compile and run the code).

You can also do it with multimaps if you want, but it'll be slightly more complicated.
#include <iostream>
#include <string>
#include <map>
#include <set>
#include <algorithm>
 
typedef std::string Directory;
typedef std::string File;
typedef std::map<Directory, std::set<File> > FileList;
 
size_t intersection(FileList &res, const FileList &fl1, const FileList &fl2) {
  size_t cnt = 0;
  res.clear();
  FileList::const_iterator it, it2;
  for (it = fl1.begin(); it != fl1.end(); ++it) {
    if ((it2 = fl2.find(it->first)) != fl2.end()) {
      std::set<File>::const_iterator it3;
      for (it3 = it->second.begin(); it3 != it->second.end(); ++it3) {
        if (it2->second.find(*it3) != it2->second.end()) {
          res[it->first].insert(*it3);
          ++cnt;
        }
      }
    }
  }
  return cnt;
}
 
int main(void) {
  FileList flist1, flist2;
 
  flist1["dir1"].insert("file11");
  flist1["dir1"].insert("file12");
  flist1["dir2"].insert("file21");
  flist1["dir3"].insert("file31");
  flist1["dir3"].insert("file32");
  flist1["dir3"].insert("file33");
  flist1["dir5"].insert("file51");
  flist1["dir5"].insert("file52");
 
  flist2["dir1"].insert("file11");
  flist2["dir1"].insert("file12");
  flist2["dir2"].insert("file22");
  flist2["dir3"].insert("file32");
  flist2["dir4"].insert("file41");
  flist2["dir4"].insert("file42");
  flist2["dir5"].insert("file51");
  
  FileList duplicates;
  size_t cnt = intersection(duplicates, flist1, flist2);
  
  std::cout << cnt << " duplicates were found :" << std::endl;
  FileList::const_iterator it;
  for (it = duplicates.begin(); it != duplicates.end(); ++it) {
    std::cout << "  -> directory " << it->first << " :" << std::endl;
    std::set<File>::const_iterator it2;
    for (it2 = it->second.begin(); it2 != it->second.end(); ++it2) {
      std::cout << "     * file " << *it2 << std::endl;
    }
  }
 
  return 0;
}

Open in new window

0
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 1000 total points
ID: 22614335
>>>> but it'll be slightly more complicated

You didn't tend to under-estimating before. Why now?   ;-)

steenpat,  the std::multimap is one of the less comfortable classes (you may also call them 'poor'). In your case it especially worse as you may have a big count of files mapped to one directory. For that a multi-map isn't suitable.

Directories and their files best were stored in a tree container. Microsoft STL has a _Tree class which is the basic data structure for map and set class. AFAIK it is not recommended to use it. The FileList Infinity posted above is a good alternative, though not very comfortable (and not fast) both for traversing or finding duplicates.

Maybe the following is an alternative:

typedef std::string Path;
typedef std::string Directory;
typedef std::string Name;

std::set<Path> allPaths;
std::map<Name, std::vector<Directory> > index;

You would store any full path in allPaths and build-up the index same time

    while (getNextFileOrFolder(parentPath, name))
    {
         allPaths.insert(parentPath + "/" + name);
         index[name].push_back(parentPath);
    }

To check whether a given name has duplicates then is

   std::map<Name, std::vector<Directory> >::iterator f;

    // check if name was used more than once
   if ((f  = index.find(name)) != index.end() && f->size() > 1)
   {      
          std::cout << "folders containing " << name << ":" << std::endl;
          std::vector<Directory> v& = *f;
          for (int i = 0; i < (int)v.size(); ++i)
          {
               std::cout << v[i] << std::endl;
          }
   }  
 
   


0
 

Author Closing Comment

by:steenpat
ID: 31501750
Both options influenced my final decision, so I split the points.
0

Featured Post

On Demand Webinar: Networking for the Cloud Era

Did you know SD-WANs can improve network connectivity? Check out this webinar to learn how an SD-WAN simplified, one-click tool can help you migrate and manage data in the cloud.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
Suggested Courses

771 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question