• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 466
  • Last Modified:

Compare two std multimaps for same element

Is there a quick and dirty way to compare two std::multimap to find an identical element?
0
steenpat
Asked:
steenpat
  • 3
  • 2
2 Solutions
 
Infinity08Commented:
>> to find an identical element?

Do you mean any identical element ? Or a specific one ?
0
 
steenpatAuthor Commented:
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
 
steenpatAuthor Commented:
But yeah any identical element will do.
0
The 14th Annual Expert Award Winners

The results are in! Meet the top members of our 2017 Expert Awards. Congratulations to all who qualified!

 
Infinity08Commented:
>> 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
 
itsmeandnobodyelseCommented:
>>>> 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
 
steenpatAuthor Commented:
Both options influenced my final decision, so I split the points.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Cloud Class® Course: Amazon Web Services - Basic

Are you thinking about creating an Amazon Web Services account for your business? Not sure where to start? In this course you’ll get an overview of the history of AWS and take a tour of their user interface.

  • 3
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now