Jump to content
  • Advertisement
Sign in to follow this  
Mawr

Quick question about std::map, objects as values.

This topic is 5118 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

For the last couple of days, I've been dancing around the problem of using objects as values in a std::map<char*, object> data type. All the tutorials or code examples I've seen on the net only use basic data types for both key and value. If someone could tell me what I'm doing wrong, I'd appreciate it. Basically I'm trying to do this:

//Creating the map
std::map<char*,Object> objMap;

//Arbitrary object and parameters
Object obj = Object(param one, param two);

//Assigning object to the list with arbitrary key
objMap[obj.attributeone]=obj;

This throws out a error saying "no Matching constructor for Object::Object()," even though I'm not trying to call that constructor.

Share this post


Link to post
Share on other sites
Advertisement
Insertion into a std::map relies on the default constructor and the assignment operator (or copy constructor, I forget which).

Share this post


Link to post
Share on other sites
Show the code for your Object class.

A word of warning, using char* as your map key type doesn't make the map string-indexed. You most likely want to use std::string as your key type.

Share this post


Link to post
Share on other sites
Thanks for the quick replies. I would show the code for the object class I intend to use it for, but that isn't currently in working order(for reasons other then this problem). But a test class I made that reproduces the same problem goes like this:


class OBJ
{
public:
int x,y,z;

OBJ(int X, int Y, int Z)
{
x=X;
y=Y;
z=Z;
}

OBJ()
{
x=0;
y=0;
z=0;
}
};


//and the code that used the class...

int main(int argc, char *argv[])
{
map<char *, OBJ> objlist;

OBJ o = OBJ(5,3,1);
char* word ="WORD";
objlist[word]=o;

word="SECOND";
o= OBJ(1,3,5);
objlist[word]=o;

word="THIRD";
o= OBJ(5,5,5);
objlist[word]=o;

int i=0;
for(map<char *, OBJ>::iterator it=objlist.begin();it!=objlist.end();++it)
{
cout << "Item: " << i << endl;
cout << "First: " << it->first << endl;
cout << "X: " << it->second.x << endl;
cout << "Y: " << it->second.y << endl;
cout << "Z: " << it->second.z << endl;
++i;
}

system("PAUSE");
return 0;
}



That code should compile, using the appropriate headers of course. And, to my suprise, the results from the for loop outputs the values I initialized each 'o' with. Remove the constructor with no parameters, and it produces the error mentioned in the OP.

I don't know anything about copy constructors (hadn't even heard about them before), but do you think the default one is sufficient to copy a class that isn't a fixed memory size? To be more specific, contains BYTE* pixelData as a member.

Also, I made the decision to use char* over string, because the I wouldn't need to include the string library in that file. My only concern is that I must be able to use the map::find function.

Share this post


Link to post
Share on other sites
Quote:
And, to my suprise, the results from the for loop outputs the values I initialized each 'o' with. Remove the constructor with no parameters, and it produces the error mentioned in the OP.


That's because objlist[word]=o; really is two operations.
First, if one doesn't already exist, objlist[word] creates an entry in the map, using the class' default constructor, and returns a reference to that entry. Then you do perform an assignment using that reference, overwriting the default-constructed value.

If you want to directly insert a value without prior default-construction, you will have to use std::map::insert().

Quote:
I don't know anything about copy constructors (hadn't even heard about them before), but do you think the default one is sufficient to copy a class that isn't a fixed memory size? To be more specific, contains BYTE* pixelData as a member.


A copy constructor is the function that is called when you do something like this:

Foo f; // default constructor
Foo g = f; // copy constructor

// BUT !!!
f = g; // assignment operator (f already exists!)




If the memory is dynamically allocated, you may be in deep trouble, since the default copy constructor only does a bitwise copy. That is, both the original and copy will have a pixelData member which points to the same address. Which means that, when either of those is destroyed, the other is left with a pointer to memory that has already been released. Which is a Bad Thing™. Additionally, it is (intentionally) unspecified whether the std::map class does create and destroy copies behind your back while working, so the simple objlist[word]=o; statement may already leave you in trouble.

As a rule of thumb, if your class needs one of destructor, copy-constructor, assignment operator, it probably needs all three.

Quote:
Also, I made the decision to use char* over string, because the I wouldn't need to include the string library in that file.


I wouldn't say that's a sufficient reason.


Quote:
My only concern is that I must be able to use the map::find function.


The problem is that since std::map compares its keys with operator<(), you will be comparing pointers and not strings. And two strings may be identical while not being at the same address - pointer comparisons do not work.

As a trivial example:
#include <iostream>

char a[] = "Hello World!";
char b[] = "Hello World!";

int main()
{
std::cout << a == b << std::endl; // Will be 0
}


The two arrays necessarily have different addresses.

There is, however, a way to override the comparison function used by the map, by passing it to the map's constructor:

#include <map>
#include <cstring>

bool string_less(const char const* a, const char* const b)
{
return strcmp(a,b) < 0;
}

std::map<char*, object>(string_less);



It is more a hassle than I would care in this particular case. And yes, you'll need that if you ever want std::map::find() to work reliably with char* keys (note that I did include a header to get access to strcmp())

Additionally, you will have to worry about the lifetime of those char* keys of yours. In your example, you used string literals, which are static (indeed, the strings are embedded into the binary, and the literal "WORD" resolves to a pointer to the address in the binary where that specific string is stored - which is why you really can't modify it, even though C++ tolerates assigning it to a char* instead of demanding a const char* - for historical reasons).

But once you start using dynamic keys, you'd better make sure that each key lasts as long as the entry it is associated with, and also gets cleaned up on time.

A common mistake is to use a local char array as the key:

int foo()
{
char buf[256];

for(int i = 0; i < 5; ++i)
{
// Do some overflow prevention ;)
std::cin >> std::setw(256) >> buf;

objlist[buf] = Object(i);
}
}


We do have several problems here, related to the fact that the char* that is used as the key will hold the address of the local array buf.
Which means that when you change the text in that array (in the loop, for example), you are changing the text of every "C string" that alias to that array. Which means that, oops, you've just changed the keys of the elements which already are in the map... Basically all the elements in the map have the same key - the address of buf. Since you are using a std::map and not a std::multimap, which would allow for duplicates, you ever have only a single element in your map - later assignments are done to the same elements as the first.

The second problem is that as soon as your function returns, the array is destroyed. Which means that your map keys now all point to invalid memory locations. Your program may or may not crash (depending on what kind of memory protection your hardware has), but you can be sure that the memory location will be reused (the array was on the stack) for some other variables in the next function call. Which means that, not only will your keys change, you won't even be guaranteed they are null-terminated C strings anymore.

So that leaves you with dynamic memory allocation (hurray!).

int foo()
{
for(int i = 0; i < 5; ++i)
{
char* buf = new char[256];
// Do some overflow prevention ;)
std::cin >> std::setw(256) >> buf;

objlist[buf] = Object(i);
}
}


Now every map entry gets a clean unique pointer. Which makes mandatory the use of a custom comparison function for your map, since none of those pointers will compare equal with any other.

You just have to remember to delete the key pointer (with delete[]) before you remove any entry from the map. Using a smart pointer would alleviate the problem (but hey! that's a header you got not only to include, but also to download, since they're not in the standard library - yet).

Take my word for it, you do not want to have to do memory management for elements you've put in a STL container. It's just too much of a hassle.

Do yourself a favor, just go ahead and use std::string. It will save you untold grief. It's a freaking standard C++ class, in the freaking standard library, after all. It is in there for are reason!

Share this post


Link to post
Share on other sites
Your example re-written:

#include <iostream>
#include <string>

class OBJ
{
public:
int x,y,z;

OBJ(int X, int Y, int Z)
// Initializer list! Learn about them!
: x(X), y(Y), z(Z)
{}

OBJ()
: x(0), y(0), z(0)
{}
};


//and the code that used the class...

int main(int argc, char *argv[])
{
// Handy typedef
typedef std::map<std::string, OBJ> objlist_t;

objlist_t objlist;

// No need to create named OBJ, char* (or string) variables
// You can use temporaries for the OBJ values, and literals
// for the strings (the string class will make the copies as
// necessary).

objlist["WORD"] = OBJ(5,3,1);
objlist["SECOND"] = OBJ(1,3,5);
objlist["THIRD"] = OBJ(5,5,5);

int i=0;

// See, handy typedef!
for(objlist_t::iterator it=objlist.begin();
it!=objlist.end();++it)
{
std::cout << "Item: " << i << std::endl;
std::cout << "First: " << it->first << std::endl;
std::cout << "X: " << it->second.x << std::endl;
std::cout << "Y: " << it->second.y << std::endl;
std::cout << "Z: " << it->second.z << std::endl;
++i;
}

// Don't do that, that's evil.
// system("PAUSE");
return 0;
}

Share this post


Link to post
Share on other sites
I honestly didn't think there would be such problems using char* as the key for a map. It cut down the .o file by a noticable portion and it allowed a convenient solution to naming. The keys were to be the file names (using fopen, fread, and fwrite) passed as a parameter into the constructor for the object I orignally had the problems on. Shouldn't be that big of a deal to change, and from what you've said, worth it in terms of less memory management.

If I use the std::map as a static lookup table (after I'm done loading it), would it be possible to have other objects who rely on the images contained within the map be searchable, and once found, have a pointer directly to the memory location of the value, so I don't have to keep refinding it, or allocate more memory for its own copy. From what you said, its possible that objects inside the map could be destroyed without my knowledge.

Never seen a initializer list before. More things to research!

Thanks for the detailed reply!

The only pointer I'm worried about is the BYTE *pixelData, I need it because I'm not sure of the exact image height and width, and know of no better way to store it while still being easily able to send it to glDrawPixels().

davedx - read the link. I may just have to create a copy constructor to transfer the data in BYTE *pixelData.

Share this post


Link to post
Share on other sites
Quote:
Original post by Mawr
Shouldn't be that big of a deal to change, and from what you've said, worth it in terms of less memory management.


No change, really, you can make std::string objects out of char* with a simple explicit conversion.

Quote:
If I use the std::map as a static lookup table (after I'm done loading it), would it be possible to have other objects who rely on the images contained within the map be searchable, and once found, have a pointer directly to the memory location of the value, so I don't have to keep refinding it, or allocate more memory for its own copy.


Yes, so long as you keep in mind you are sharing that one object among many client objects. Smart pointers (same link as before) are a very good way to track that kind of things.

Quote:
From what you said, its possible that objects inside the map could be destroyed without my knowledge.


It will not destroy it whimsically, what I meant is that the object actually stored in the map may not be the original object you had, but a copy.

Quote:
Never seen a initializer list before. More things to research!


Passing parameters in an initializer list will call the appropriate constructor for the member variable, instead of first default-constructing an instance and then overwriting it with an assignment in your class constructor body. For member variables which aren't lvalues, such as constants and references, or for member variables without a copy constructor, that's the only way you have to initialize them.

It generates faster code, and looks better too.

Quote:
The only pointer I'm worried about is the BYTE *pixelData, I need it because I'm not sure of the exact image height and width, and know of no better way to store it while still being easily able to send it to glDrawPixels().


As davedx pointed out, that's what copy constructors and assignment operators are for. Here's a way to do it:


#include <iostream>
#include <string>
#include <algorithm>

class Foo
{
unsigned long size;
char* pixelData;
public:
Foo(const std::string& filename)
{
std::ifstream ifs(filename.c_str());
// Read in the size of the image, somehow
ifs.read( (char*)&size, sizeof(size));

// Allocate the data
pixelData = new char[size];

// Read the data in
ifs.read( pixelData, size);
}

// Copy constructor
Foo(const Foo& rhs)
: size(rhs.size), pixelData(new char[rhs.size])
{
// Standard STL copy algorithm
// copy from [rhs.pixelData, rhs.pixelData+size)
// to the [pixelData...)

// Since you've seen iterators (q.v. your example),
// you know that iterator ranges are semi-open, excluding
// their end point. Pointers are iterators over C arrays.

std::copy(rhs.pixelData, rhs.pixelData+size, pixelData);
}

// Assignment operator
Foo& operator=(const Foo& rhs)
{
// First, guard against self-assignment "a=a"
// If we don't, not only is it wasteful, but
// we would end up losing our data (and leaking memory)

if(this==&rhs) // Same object means same address
return *this;
// Note that we return the object (*this) by reference
// to allow for chained assignment a=b=c=d=e;


// If the data had the same length, we could have
// reused the memory. A more complex example would
// keep track of the data size and allocated memory
// size, and only reallocate if we don't have enough
// memory. Granted, if you're not going to reuse the
// objects much there is not much benefit, but hey,
// it's simple and instructive

if(size != rhs.size)
{
size = rhs.size;
delete[] pixelData;
pixelData = new char[size];
}

std::copy(rhs.pixelData, rhs.pixelData+size, pixelData);

return *this;
}

// Destructor
~Foo()
{
delete[] pixelData;
}
};





Now that's not *too* complicated, but there is a way to make things simpler, and yet preserve compatibility with glDrawPixels().

You can store your data into a std::vector<char>.

I'm not kidding.

Once again, it'll do your memory management for you, and you are guaranteed that a vector has contiguous storage - i.e. is compatible with a C array. The only trick is that, instead of passing the object to a function expecting a C array (or a pointer), you'll have to pass a pointer to the first element of the vector.

std::vector<char> pixelData;
char* pixels = &pixelData[0];


What does that earn you? Well, std::vector does have its own copy constructors, assignment operators and destructors. And the nice thing is that, if your class members all implement them (or don't need them, e.g. because they are built-in types), then your class won't need to implement them itself.

The default constructor does a memberwise copy, calling the copy constructors of those members which have copy constructors, and doing a bitwise copy of those which don't. Idem for the assignment operator, and similarly, all your member destructors do get called when the enclosing object is destroyed.

Which gives us the following code:

#include <iostream>
#include <string>
#include <vector>

class Foo
{
std::vector<char> pixelData;
public:
Foo(const std::string& filename)
{
std::ifstream ifs(filename.c_str());
// Read in the size of the image, somehow
unsigned long size;
ifs.read( (char*)&size, sizeof(size));

// Allocate the data
pixelData.resize(size);

// Read the data in
ifs.read( &pixelData[0], size);
}
};

// Client code:

Foo image("hi_mom.tga")
glDrawPixels( width, height, format, type, &image.pixelData[0]);






A bit better, isn't it? Now, that may make your executable bigger, sure, that's a downside of the STL, but it isn't as big a problem as some people here make it.

std::vector::size() does give me the number of pixels whenever needed, so I don't need to keep track of it myself, risking desynchronization if I ever code it wrong (e.g. I don't want a size member in my Foo class that doesn't hold the actual size of the data, so I removed one potential source of error).

There are ways to directly read whole files into vectors, but I don't think that's interesting to you, since you probably have to parse the file for the image data.

Share this post


Link to post
Share on other sites
Mmm. That does sound better. I'll give it a proper go tommarow when I'm not so fuzzy headed. Once again, thanks for the detailed reply.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!