hi friends;
i am trying to build a class using multimap, the idea is something like this:
I have say N no of particles and each particle has fix position in 3d space

something like this:

Coordinate: Particle level
(1,2,3) ----------------> 1
(1,2,3) ----------------> 7
(1,0,0) ----------------> 2
(0,0,0) ----------------> 0
..... and so on

I tried this with 4d array like Pos[x][y][z], but i dont like the approach and thought maybe using multimap from stl will be more effivient in this kind of mapping. Please put your inputs in this regard.

i'll now show the class i have devolopped so far

// [B]Container class that define (i,j,k) triplet[/B]


typedef class container store;
typedef std::pair<const store, int> Pair;
typedef std::multimap< store, int > Box;

// 1st class container definition
class container
              int _i;
              int _j;
              int _k;
             container():_i(0),_j(0),_k(0){} //constructor
             container(const int&i, const int&j,
                       const int&k):_i(i),_j(j),_k(k){} //constructor
             container(const container& t)  //copy constructor
             { _i=t._i;
             bool operator>(const container& t)const     // need to understand
                           { return _k>t._k||_j>t._j||_i>t._i;}    
            bool operator<(const container& t)const
                           {return _k<t._k||_j<t._j||_i<t._i;}    // need to understand

             bool operator()(const container& __x, const container& __y) const
                             { return __x < __y; }   
            container & operator=(const container & t) //Assignment Operator
                      if (this == &t) // object assigned to itself
                      return *this; // all done
                       return *this;                 
             friend std::ostream & operator<<(std::ostream & os, const container & t)
                              os << "(" << t._i << "," << t._j<<","<<t._k<<")";
                              return os;

Next i write the mapping class using particle and data triplet defined in container class

class _Map
      Box xx;

   _Map(){}  //default constructor
    void int_insert(const store &HOLD, const int  &the_number)
                   {xx.insert(Pair(HOLD,the_number));}   //HOLD is the key index where the number is inserted
    int WholeEraseByKey(const store &HOLD) //it also returns the number of erased elements
         Box::size_type n;
         n = xx.erase(HOLD);
         return n;
    void ShowMap()
          Box::iterator pos;
          std::cout.setf(std::ios::left, std::ios::adjustfield);
         for (pos=xx.begin(); pos!=xx.end(); ++pos) {
              std::cout << pos->first << " ->"
                        << pos->second << std::endl;


This code so far works fine. But i need to put some more functionality where i am getting confused.

1. remove a particular particle.
say i have: (0,0,0) ----> 7
(0,0,0) -----> 8
(0,0,0) ------> 10
(1,1,1) --------> 1

and i need to erase the value 10 only. I am only able to erase the whole map with key value (0,0,0).

2. Secondly is it possible by looking at value, to retrive the information about is coordinate without doing a full search.

Please comment.

8 Years
Discussion Span
Last Post by StuXYZ

You seem to be doing what every condensed matter phys. student does a sometime that is to write an atomic simulation.
So I am assuming that is so. What you want is to have a multimap
that allows you to quickly obtain those particle of a particular type or
you use level (spin state maybe?), then process them. However, it is 99.99% certain that you are going to need to do it efficiently.

So use first off make your life easy and define a Atom class which holds 3D position and anything else you need. Here is a minimalistic
structure. Add cons/dest/copy etc

struct Atom
   double x;
   double y; 
   double z; 


Let us create a multimap and insert some atoms (I am using a typedef
because to keep the typing down. (let me know if you want it written completely)

typedef std::multimap<int,Atom>  mmTYPE;
mmTYPE Amap;         // Make  a multimap called Amap
Amap.insert(mmTYPE::value_type(7,Atom(3,4,5)) ;
Amap.insert(mmTYPE::value_type(8,Atom(1,2,3)) ;
Amap.insert(mmTYPE::value_type(7,Atom(6,-3,5)) ;

Note that we have two atoms (different position) at index 7.
Let us erase all atoms at level 7 AND with a negative Y position.
That is only ONE of the level 7 atoms.

mmTYPE::iterator mc=Amap.find(7);
for(;mc!=Amap.end() && mc->first==7;mc++)
   if (mc->second.y<0)

Ok the loop is messy, because the deletion invalidates the map iterator, so it has to be re-created. It is also very inefficient if
the secondary test is complex. However, if you need to improve the optimization here, then looking at your version of the STL, can show you how much you can rely on the iterator after the find.

All of the above can be done with a functor class. If the secondary test is expensive, then caching the results etc, is often done. (as is marking stuff dead and doing local garbage collection later when the dead score gets about x%)

Finally, yes I have re-ordered you map, from Point -> level to level->point. That will give you a large performance improvement.


thanks for digging this out.
And you have guessed it correctly, i am trying to devolop code for event driven simulation of dilute granular gas. To avoid technical details i had phrased the problem that way.

The reason i choose to follow:level->point is that
level resembles box in 3 dimension. I have to hop through different boxes, search for particle, remove, insert, calculate interaction with neighbour boxes.
So apperently information about certain box in 3d is imporatnt not the other way.


Despite your simulation set up, do not put the point as the first
part of the map.

The map is actually a std::set taking a pair. It is sorted on the first
on a red-black tree. If you use a point, you will end up with a horrific sorting problem, insert removes will take forever, additionally, I know of no way of getting avoiding the problem of different sort criteria for a point. (you need the particle closest to X). So divide you space into N bin and use that as the level and the map index. You can be clever and divide say 1024 and sub-divide each by another 1024 and make a large number for the level. This it is easy to pick-out based on the find.

If you need to do something specialized on the 3d-point write your own map/set class.

This article has been dead for over six months. Start a new discussion instead.
Be sure to adhere to our posting rules.