Thread: Rewrote my cMap class. Looking for more criticism

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    673

    Rewrote my cMap class. Looking for more criticism

    Okay so I rewrote my map class, and changed pretty much everything.

    What I fixed (I think)-

    • I added memory recording. Probably not accurate, but I don't know how else to do it.
    • Removed a lot of unnecessary searching, thus saving a lot of time I think.
    • Added functionality for copying.
    • Added better exception. using std::runtime_error


    Well, here it is. I am hoping you all can point out mistakes, or better ways of doing something.
    Although not really looking for people to tell me it doesn't work like an associative array, as I already know that ( just do not have a better name for the class )
    Code:
    #pragma once
    
    #include <map>
    #include <list>
    #include <string>
    #include <stdexcept>
    
    template <class T>
    class cMap
    {
    private:
    	/* Index management */
    	size_t m_iCurIndex;
    	std::list<size_t> m_cList;
    
    	/* Memory Recording */
    	size_t m_iMemUsage;
    	bool   m_fRecordMemory;
    
    
    	std::map<size_t, T*> m_cMap;
    
    	size_t _GetIndex()
    	{
    		if ( !m_cList.empty() )
    		{
    			size_t iIndex = m_cList.back();
    			m_cList.pop_back();
    			return iIndex;
    		}
    		++m_iCurIndex;
    		return m_iCurIndex;
    	}
    
    	void _Copy(const cMap& p_cCopy)
    	{
    		//Make sure the map is empty first
    		Clear();
    		//Now copy all indices, and pointers
    		typename std::map<size_t, T*>::const_iterator iter = p_cCopy.m_cMap.begin();
    		for (/**/; iter != p_cCopy.m_cMap.end(); ++iter )
    		{
    			m_cMap[(*iter).first] = new T(*(*iter).second);
    		}
    		//Copy index list
    		m_cList = p_cCopy.m_cList;
    
    		//Copy variable values
    		m_iCurIndex = p_cCopy.m_iCurIndex ;
    		m_iMemUsage = p_cCopy.m_iMemUsage;
    		m_fRecordMemory = p_cCopy.m_fRecordMemory;
    	}
    
    public:
    	explicit cMap()
    		:m_iCurIndex(0), m_iMemUsage(0),m_fRecordMemory(true)
    	{ }
    	~cMap()
    	{
    		Clear();
    	}
    
    	/* Copying */
    	explicit cMap(const cMap& p_cCopy)
    	{
    		_Copy(p_cCopy);
    	}
    	const cMap& operator=(const cMap& p_cCopy)
    	{
    		_Copy(p_cCopy);
    		return *this;
    	}
    
    	/* Memory Recording */
    	void SetMemRec(bool p_fValue) { m_fRecordMemory = p_fValue; }
    	bool GetMemRec() const		  { return m_fRecordMemory; }
    	int  GetMemUsage() const      { return m_iMemUsage;}
    
    
    	size_t Push(const T& p_cCopy)
    	{
    		size_t iIndex = _GetIndex();
    		m_cMap[iIndex] = new T(p_cCopy);
    
    		/* Manage memory */
    		if ( m_fRecordMemory )
    		{
    			m_iMemUsage += sizeof(T);
    		}
    		return iIndex;
    	}
    
    	void Remove(size_t p_iIndex) throw(...)
    	{
    		typename std::map<size_t,T*>::iterator iter = m_cMap.find(p_iIndex);
    		if ( iter == m_cMap.end() )
    		{
    			throw std::runtime_error("Invalid index was provided to cMap<T*>::Remove(size_t)");
    		}
    		delete (*iter).second; (*iter).second = 0;
    		m_cList.push_back(p_iIndex);
    		m_cMap.erase(iter);
    
    		/* Manage memory */
    		if ( m_fRecordMemory )
    		{
    			m_iMemUsage -= sizeof(T);
    		}
    	}
    
    	void Clear()
    	{
    		typename std::map<size_t,T*>::iterator iter = m_cMap.begin();
    		for(/**/; iter != m_cMap.end(); ++iter )
    		{
    			delete (*iter).second; (*iter).second = 0;
    		}
    		m_iMemUsage = 0;
    		m_iCurIndex = 0;
    		m_cMap.clear();
    	}
    
    	T& operator[](size_t p_iIndex) 
    	{
    		if ( m_cMap.find(p_iIndex) == m_cMap.end() )
    		{
    			throw std::runtime_error("Invalid index was provided to cMap<T*>::operator[](size_t)");
    		}
    		return *m_cMap[p_iIndex];
    	}
    
    	const T& operator[](size_t p_iIndex) const
    	{
    		if ( m_cMap.find(p_iIndex) == m_cMap.end() )
    		{
    			throw std::runtime_error("Invalid index was provided to cMap<T*>::operator[](size_t)");
    		}
    		return *m_cMap[p_iIndex];
    	}
    };
    Thank you for any input you have.
    Last edited by Raigne; 11-06-2008 at 01:54 PM. Reason: typo in code

  2. #2
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Some remarks:

    Include <stdexcept> (not <exception>) to use std::runtime_error (or other std exception types derived from std::exception).

    You are again missing the typename keyword from all iterator declarations.

    The "throws anything" exception specifiers don't compile. (And they don't provide any useful information either: in a templated container any method can really throw anything - the stored type may throw its own exceptions.)

    I think now my earlier criticism applies: why do you allocate the objects dynamically if you are going to make a copy of the stored objects anyway? Why not use a std::map<size_t, T> instead of std::map<size_t, T*> as the underlying type? I don't think a map makes any more copies of the objects once they have been inserted.
    Last edited by anon; 11-06-2008 at 03:56 AM.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  3. #3
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    For example:
    typename std::map<size_t,T*>::iterator iter = m_cMap.begin();
    Since it is dependant on T, it is a dependant type, and thus needs the typename.
    (Yeah, I know, Visual C++ really seems to ignore it, but it is required by the standard.)
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  4. #4
    Registered User
    Join Date
    Nov 2005
    Posts
    673
    Visual Studio apparently ignores a lot of things.

    The reason for the dynamic elements is because this map's purpose is to contain thousands of elements, and (game resources) so stack would be overrun pretty quick.

    the throw(...) doesn't matter in visual studio, as it is put there anyway. I will take it out.

    Anon: If I don't use dynamic memory then the map stores just ordinary objects, and thus using stack memory correct? Dynamic uses heap IIRC.
    Last edited by Raigne; 11-06-2008 at 01:41 PM.

  5. #5
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by Raigne View Post
    Visual Studio apparently ignores a lot of things.
    Yes, sometimes it seems too smart for its own good.
    It may simply be that the compiler engine is built in such a way that those keywords are really irrelevant and the compiler has no good way of knowing whether they should be there or not.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Quote Originally Posted by Raigne View Post
    The reason for the dynamic elements is because this map's purpose is to contain thousands of elements, and (game resources) so stack would be overrun pretty quick.

    Anon: If I don't use dynamic memory then the map stores just ordinary objects, and thus using stack memory correct? Dynamic uses heap IIRC.
    Incorrect. The map nodes (and thus the objects they contain) are on the heap anyway.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  7. #7
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677

    Post

    what is the purpose of m_iCurIndex? As far as I can tell, it's always either 0 or 1, and it's only used when the list is empty.

    Your operator= should probably cope with "a = a" type operations [if you use references, this can sometimes be valid code even if it looks like "b = a", because "a" is reference to b or the other way around. In your current code, if p_cCopy is the same as "this", then you clear it, and the rest of the copy doesn't happen.

    A very non-technical point, but:
    Code:
    	void Clear()
    	{
    		typename std::map<size_t,T*>::iterator iter = m_cMap.begin();
    		for(/**/; iter != m_cMap.end(); ++iter )
    can be written as either:
    Code:
    	void Clear()
    	{
    		for(typename std::map<size_t,T*>::iterator iter = m_cMap.begin(); 
                          iter != m_cMap.end(); ++iter )
    or
    Code:
    		typename std::map<size_t,T*>::iterator iter;
    		for(iter =  = m_cMap.begin(); iter != m_cMap.end(); ++iter )
    I prefer to see the initialization of the loop variable inside the for-loop - but as I said, that's personal preference. I just find it easier to read than to try to hunt around for the initialization on some other line above the for-loop.

    The same applies to the other similar for-loop in _Copy().

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  8. #8
    Registered User
    Join Date
    Nov 2005
    Posts
    673
    m_iCurIndex is incremented everytime _GetIndex() is called(if the m_cList is empty), m_cList is for reusing indexes.
    On the operator=() should I just check if the reference address passed is the same as the this pointer?

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Code:
    I added memory recording. Probably not accurate, but I don't know how else to do it.
    std::map should have a constant time size() method. Of course, you can't turn that on/off, so it would always report the exact number of map items...

    As to assignment operator, you could just switch to map<size_t, T>, and the default copying behaviour should be OK. As it is, you have just added another level of indirection for zero gain.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  10. #10
    Registered User
    Join Date
    Nov 2005
    Posts
    673
    It is wierd though, I heard somewhere that using pointers in STL containers provides a significant boost in performance of the container.

  11. #11
    The larch
    Join Date
    May 2006
    Posts
    3,573
    That may probably be the case if the contents are going to be copied around a lot and the contained objects are large (e.g a vector resizing, or perhaps sorting a vector etc). IMO, things like list, set and map are node based, and the only manipulations on them are resetting node pointers - the contents should not get copied.

    Another cost you might be worried about, is that the containers make a copy of the items when you insert them, and it can be cheaper to copy a pointer than an object. However, your class also makes a copy of the object when you insert it. And not only that, it performs an extra memory allocation that none of the STL containers does (together with all the resulting slow-down from an extra indirection and increasing the complexity of the code).

    There may also be other reasons to store pointers, polymorphism being an important reason. But your class makes a copy of the object and therefore slices it, so it still won't work for polymorphic objects (unless a pointer is what you put in in the first place). And even then you might consider either special purpose pointer containers (like boost ptr_containers), or more versatile simple containers of smart pointers (like boost shared_ptr).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  12. #12
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Quote Originally Posted by Raigne View Post
    It is wierd though, I heard somewhere that using pointers in STL containers provides a significant boost in performance of the container.
    http://www.research.att.com/~bs/bs_f...low-containers
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  13. #13
    and the hat of sweating
    Join Date
    Aug 2007
    Location
    Toronto, ON
    Posts
    3,545
    Code:
    size_t _GetIndex()
    ...
    void _Copy(const cMap& p_cCopy)
    ...
    Don't use names that begin with an underscore. They are reserved for use by the compiler *.

    * Actually only names that begin with two underscores, or a single underscore and either a capital or small letter (I can never remember which it is) are reserved for the compiler.
    "I am probably the laziest programmer on the planet, a fact with which anyone who has ever seen my code will agree." - esbo, 11/15/2008

    "the internet is a scary place to be thats why i dont use it much." - billet, 03/17/2010

  14. #14
    Registered User
    Join Date
    Nov 2005
    Posts
    673
    I doubt that the underscore thing will matter if it is a member.

  15. #15
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Well, most of the time you can get away with functions that starts with __. The point being, it's bad practice because they're reserved, so don't do it.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Specializing class
    By Elysia in forum C++ Programming
    Replies: 6
    Last Post: 09-28-2008, 04:30 AM
  2. Default class template problem
    By Elysia in forum C++ Programming
    Replies: 5
    Last Post: 07-11-2008, 08:44 AM
  3. Defining derivated class problem
    By mikahell in forum C++ Programming
    Replies: 9
    Last Post: 08-22-2007, 02:46 PM
  4. matrix class
    By shuo in forum C++ Programming
    Replies: 2
    Last Post: 07-13-2007, 01:03 AM
  5. Replies: 7
    Last Post: 05-26-2005, 10:48 AM