Is it possible for STL set to be faster than STL multiset for preventing duplicate entries?

Good afternoon, We are currently using STL multimap and STL set to cache memory mapped file regions. We would like our cache to have only unique entries. We wondering if there is a way for STL set and STL map to be faster than STL multiset and STL multimap for preventing duplica开发者_Go百科te entries. We are using the following code excerpt to prevent STL multimap and STL set duplicate entries. Is it possible to make this faster? Thank you.

int distance(char* x, char* y,int error){ 
    if (x >= y && (x - y) <= error){ 
        return 0;
    }
    return (x - y);
};

class MinDist {
public:
    MinDist(){}

    MinDist(char* & p, const int & error){}

    bool operator() (char *  p1, char *  p2 )
    {
      return distance( p1, myPoint, myError) < distance( p2,  myPoint, myError); 
    }

public:
    static char* myPoint;
    static int myError;
};


std::multiset<Range> ranges_type; 
std::multimap<char *,Range, MinDist> mmultimap;


MinDist::myPoint = TmpPrevMapPtr;
MinDist::myError = MEM_BLOCK_SIZE;

std::pair<I,I> b = mmultimap.equal_range(TmpPrevMapPtr); 
for (I i=b.first; i != b.second; ++i){ 
     ranges_type.erase(i->second);
     numerased++;
}

typedef std::multimap<char*,Range,MinDist>::iterator J;
std::pair<J,J> pr = mmultimap.equal_range(TmpPrevMapPtr); 


erasecount = 0;
J iter = pr.first;
J enditer = pr.second;
for(  ; iter != enditer ; ){ 
    if ((*iter).first == TmpPrevMapPtr){
        mmultimap.erase(iter++); 
        erasecount++;
    }
    else{
        ++iter;
    }
}

MinDist::myPoint = 0; 

ranges_type.insert(RangeMultiSet::value_type(n, n + mappedlength,
                &adjustedptr[n],MapPtr,mappedlength));


mmultimap.insert(RangeMultiMap::value_type(MapPtr,
                   Range(n,n + mappedlength,
                      &adjustedptr[n],
                      MapPtr,mappedlength)));

There's a lot of stuff to read here, and optimization of the complex container types is a tricky problem. I've spent a fair bit of time working on similar problems, so I'll try to point out some things that have helped me.

Firstly, the usual way to make your code faster is don't use binary trees when vectors will do. The Microsoft STL implementation is going to spend about 14 bytes (3 pointers + short int for red/black flag last I checked) of overhead for each node in your map/set, plus malloc overhead of at least 4 more bytes before it gets around to storing your node data. While I don't know the specifics of your domain too well, memory mapped I/O strikes me as an area where there likely exists a complex but faster vector-based solution. It would require that the number of blocks you map simultaneously is small--if your lookup-table is up to or less than 6,000 bytes, a sorted-array implementation with memmove for insert/erase, and binary_search for lookup will likely be faster in Release mode (and in Debug mode, it'll be faster up to several megabytes, sadly). If the elements are 4-byte pointers, then 6,000 bytes allows for up to 1,500 mapped blocks.

There are times that you simply need to use trees, however. One case is complex nodes (so that construction/destruction is essential) or fairly high element count (so that the O(N) array insertion becomes slower than the malloc cost of O(log n) tree insertion). What can you do here? Note that map/multimap and set/multiset or pretty nearly the same speed; the multi* versions do tend to be a little slower, but only because the code to handle them is a few lines longer.

Anyway, one thing that can help a lot is figuring out how to cut the malloc cost, since every node is going to call malloc/free at some point. Cutting that is difficult--the Release mode allocator is roughly the equivalent of about 50-200 arithmetic operations, so while it's beatable, it takes some effort. You do have some hope, though -- map/set allocations are all identically sized, so a memory pool can work very well. Google is probably a good way to get started; there are many good articles on this topic.

Finally, there's an open source sampling profiler that I have found very helpful -- it's called Very Sleepy, and usually Just Works on Visual Studio projects. If you want to definitely answer whether map/multimap or set/multiset is quicker in your case, that's the main thing I'd point you to. Good luck!

Here is a generic situation:

#include <cstddef>   // for size_t
#include <set>       // for std::set
#include <algorithm> // for std::swap
#include <ostream>   // for std::ostream

struct Range
{
  int start, end; // interpret as [start, end), so Range(n,n) is empty!

  Range(int s, int e) : start(s), end(e)
  {
    if (start > end) std::swap(start, end);
  }

  inline bool operator<(const Range & r) const
  {
    return (start < r.start) || (!(r.start > start) && end < r.end);
  }

  inline size_t size() const { return end - start; }
};

std::ostream & operator<<(std::ostream & o, const Range & r)
{
  return o << "[" << r.start << ", " << r.end << ")";
}

typedef std::set<Range> cache_t;

cache_t::const_iterator findRange(int pos, const cache_t & cache)
{
  cache_t::const_iterator it = cache.lower_bound(Range(pos, pos)),
                         end = cache.end();

  for ( ; it != end && it->start <= pos ; ++it) // 1
  {
    if (it->end > pos) return it;
  }

  return end;
}

inline bool inRange(int pos, const cache_t & cache)
{
  return findRange(pos, cache) != cache.end();
}

Now you can use findRange(pos, cache) to discover whether a given position is already covered by a range in the cache.

Note that the loop at // 1 is rather efficient as it only starts at the first element where pos could possibly be and stops once pos can no longer be in range. For non-overlapping ranges this will cover at most one range!

class Range { 
    public:   
        explicit Range(int item = 0)
        : mLow(item), mHigh(item), mPtr(0), mMapPtr(0) { }

        Range(int low, int high, char* ptr = 0, char * mapptr = 0, int currMappedLength = 0)
        : mLow(low), mHigh(high), mPtr(ptr), mMapPtr(mapptr), mMappedLength(currMappedLength) { }

        Range(const Range& r)
        : mLow(r.mLow), mHigh(r.mHigh), mMapPtr(r.mMapPtr), mMappedLength(r.mMappedLength) { }

        bool operator<(const Range& rhs) const { return mHigh < rhs.mHigh; }

        int   low()       const { return mLow; }   
        int   high()      const { return mHigh; }
        char* getMapPtr() const { return mMapPtr; }
        int getMappedLength() const { return mMappedLength; }

     private:   
         int mLow;          // beginning of memory mapped file region
         int mHigh;         // end of memory mapped file region 
         char* mMapPtr;     // return value from MapViewOfFile
         int mMappedLength; // length of memory mapped region
};