Maps Tutorial (C++)

Tutorials, I don''t know, but if you have questions, ask.

---

[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]

Ok, I would understand much more if you just told me how to use them.

1. What''s the best way to declare a map?
2. How to add an item to a map?
3. Can maps be sorted?
4. How to delete stuff from a map?

And any basic questions you can think of.

---

R.I.P. Mark Osback
Solo Pa Mi Gente
VG-Force

1) Depends on what you want to put in it. std::map< std::string, Object > ObjectMap; will declare a map that maps Objects to strings.



2) In the case above with the Object/string map:

Object MyObject;
std::string MyObjectName="ThisObject";

ObjectMap[ MyObjectName ]=MyObject;

This creates a key of value "ThisObject", and associates it with a copy of MyObject. You can declare std::map< std::string, Object * > to handle mapping strings to pointers to an object, to avoid copying objects.




3) Yes. No. All of the above. A map is a Sorted Associative Container, meaning that it sorts itself, due to it's internal structure (typically, a red-black tree), so that elements can be located as efficiently as possible. There is no need to call an extraneous sort() on it. In the case of the map above, objects are sorted alphabetically based on their string value. Iterating from ObjectMap.begin() to ObjectMap.end() will iterate in alphabetical order. Neat, huh?



4) ObjectMap.erase(MyObjectName); to erase by key or
ObjectMap.erase(Iter); to erase by iterator.



Maps are useful for a lot of different problems. For a quick example, in my game I have a class called AnimationMaster, which handles anything related to animation (frames of animation, timing, etc...). Any monster, NPC, etc.. that is created can request an AnimationMaster by name from the handler. AnimationMasters are stored in a map ( std::map< std::string, AnimationMaster * > ) so that when one is requested, the handler can quickly search to see if it has already been loaded, by performing find() on the map with the requested name. If that name is found, the associated AnimationMaster is returned rather than loading it again. If the name is not found, the AnimationMaster is loaded from file, and inserted into the map under the given name, then the pointer is returned.

Josh
vertexnormal AT linuxmail DOT org

---

Check out Golem: Lands of Shadow, an isometrically rendered hack-and-slash inspired equally by Nethack and Diablo.

[edited by - VertexNormal on October 19, 2003 12:44:33 AM]

1) std::map< KeyType, ValueType > MyMap;.

I usually create a typedef if I''m going to use that type a lot. It makes it easier when declaring iterators.

typedef std::map< KeyType, ValueType > MyMapType;

2) To insert a new object, one way is to use

MyMap.insert( std::make_pair( Key, Value) );.

** std::make_pair is found in <utility>, and is necessary since map elements are stored as Key/Value pairs. When you have such a pair p, p.first is the key (const KeyType) and p.second is the value (ValueType). **

The return value (a bool) will tell you whether the insertion succeeded or not (there can only be one element with a given key).
If you want to do "Create or update", you can use

MyMap[Key] = Value;

which will create the element if it doesn''t exist, or update it if it does. Also note that this syntax can be used for lookup (a reference to the value is returned by MyMap[Key]), but has the side-effect of creating a (default-constructed) Value if there was no element with that key.

3) Maps are implicitely sorted using the std::less<KeyType> functor class (which just compares items using operator<). Watch out, a common error is to use char* (or other pointer) as the key type, which has for effect of sorting keys by pointer values (address) and not by the value they point to.
You can give your own sorting function (functor, rather), by passing it when creating the map :

std::map<KeyType,ValueType> MyMap( Function );

This sorting order will only be apparent when walking through the map with iterators (which are pointer-like container accessors).

typedef std::map< KeyType, ValueType > MyMapType;
MyMapType MyMap;

/* ... */

MyMapType::iterator itor = MyMap.begin(); // First element

MyMapType::iterator end = MyMap.end();    // One-past the last element


while( itor != end )
{
  std::cout << "MyMap[" << itor->first
            << "] = "  << itor->second
            << std::endl;
  ++itor;
}

Will print MyMap[key] = value for each element in the map, in whatever order is defined by the comparison operator for KeyType (or the one you provided to the map constructor).

Note though that iteration is often much better done through the standard algorithms (like std::for_each, std::copy ...)

4)

• by key : MyMap.erase(Key);
  
• using iterators MyMap.erase(itor)
  
• according to some function - std::remove_if(MyMap.begin(), MyMap.end(), Predicate )
  

The destructor of the value will be called. REMEMBER that pointers do not have a destructor, and that you must therefore delete them before removing such a value from the map. If you use a container of smart pointers (e.g. boost::shared_ptr), you won''t have to worry about that, but otherwise, you will have to write code similar to what follows :

typedef std::map< KeyType, ValueType > MyMapType;
MyMapType MyMap;

/* ... */

MyMapType::iterator itor = MyMap.begin(); // First element

MyMapType::iterator end = MyMap.end();    // One-past the last element


while( itor != end )
{
   if( MustBeRemoved( *itor ) )
   {
      delete itor->second;
      itor = MyMap.erase( itor );
   }
   else ++itor;
}

Note that you must use the return value from erase to advance the iterator if you are erasing it - erase returns an iterator to the element following the element you just erased. Using ++itor assumes the iterator points to a valid map element - which it doesn''t anymore (that''s a very common error).

Also note that, while I mentioned smart pointers, std::auto_ptr cannot be used in STL containers.

---

[ Start Here ! | How To Ask Smart Questions | Recommended C++ Books | C++ FAQ Lite | Function Ptrs | CppTips Archive ]
[ Header Files | File Format Docs | LNK2001 | C++ STL Doc | STLPort | Free C++ IDE | Boost C++ Lib | MSVC6 Lib Fixes ]

template <
class Key,
class Type,
class Traits = less< Key >,
class Allocator=allocator< pair < const Key, Type > >
>
class map......

Where the third template parameter is the Functor for comparing. Yes the functor could be given in the constructor, but I kinda prefer when all containers of the typedef one usually makes behave the same.

}-- Programmer/Gamer/Dreamer --{

[edited by - Seriema on October 20, 2003 12:24:28 PM]