diff --git a/lemon/concepts/maps.h b/lemon/concepts/maps.h
--- a/lemon/concepts/maps.h
+++ b/lemon/concepts/maps.h
@@ -47,10 +47,9 @@
       typedef T Value;
 
       /// Returns the value associated with the given key.
-
-      /// Returns the value associated with the given key.
-      /// \bug Value shouldn't need to be default constructible. 
-      Value operator[](const Key &) const { return Value(); }
+      Value operator[](const Key &) const { 
+        return *static_cast<Value *>(0);
+      }
 
       template<typename _ReadMap>
       struct Constraints {
@@ -126,7 +125,9 @@
       typedef T Value;
 
       /// Returns the value associated with the given key.
-      Value operator[](const Key &) const { return Value(); }
+      Value operator[](const Key &) const { 
+        return *static_cast<Value *>(0);
+      }
 
       /// Sets the value associated with the given key.
       void set(const Key &, const Value &) {}
@@ -160,15 +161,17 @@
       /// The const reference type of the map.
       typedef CR ConstReference;
 
-    protected:
-      Value tmp;
     public:
 
       /// Returns a reference to the value associated with the given key.
-      Reference operator[](const Key &) { return tmp; }
+      Reference operator[](const Key &) { 
+        return *static_cast<Value *>(0);
+      }
 
       /// Returns a const reference to the value associated with the given key.
-      ConstReference operator[](const Key &) const { return tmp; }
+      ConstReference operator[](const Key &) const {
+        return *static_cast<Value *>(0);
+      }
 
       /// Sets the value associated with the given key.
       void set(const Key &k,const Value &t) { operator[](k)=t; }
diff --git a/test/maps_test.cc b/test/maps_test.cc
--- a/test/maps_test.cc
+++ b/test/maps_test.cc
@@ -32,6 +32,12 @@
 inline bool operator<(A, A) { return true; }
 struct B {};
 
+class C {
+  int x;
+public:
+  C(int _x) : x(_x) {}
+};
+
 class F {
 public:
   typedef A argument_type;
@@ -58,9 +64,13 @@
 {
   // Map concepts
   checkConcept<ReadMap<A,B>, ReadMap<A,B> >();
+  checkConcept<ReadMap<A,C>, ReadMap<A,C> >();
   checkConcept<WriteMap<A,B>, WriteMap<A,B> >();
+  checkConcept<WriteMap<A,C>, WriteMap<A,C> >();
   checkConcept<ReadWriteMap<A,B>, ReadWriteMap<A,B> >();
+  checkConcept<ReadWriteMap<A,C>, ReadWriteMap<A,C> >();
   checkConcept<ReferenceMap<A,B,B&,const B&>, ReferenceMap<A,B,B&,const B&> >();
+  checkConcept<ReferenceMap<A,C,C&,const C&>, ReferenceMap<A,C,C&,const C&> >();
 
   // NullMap
   {