Sign in to follow this  
cpp forever

[C++] Use map::operator[] for inserting

Recommended Posts

cpp forever    150
I want some-how to subclass STL map<SomeType, std::string> for inserting char* and std::string. This is the declaration of map::operator[]
	mapped_type& operator[](const key_type& _Keyval)
		{	// find element matching _Keyval or insert with default mapped
		iterator _Where =
			insert(value_type(_Keyval, mapped_type())).first;
		return ((*_Where).second);
		}

I mean, I want to convert char* to std::string when using both of
MyMap[AAA] = "asdfasdg";
MyMap[AAA] = some_scl_string;

Share this post


Link to post
Share on other sites
cpp forever    150
Quote:
Original post by Nitage
Doesn't the "constant in quotes" get automatically converted to std::string anyway?


Well, yes. Sorry.
But when I'm writing the following: (and using it in previous circumstances)

map<SomeType, string>::mapped_type& operator[](const SomeType SomeType1)
{
return MyMap[SomeType1];
}


me receiving the error C2679.

Share this post


Link to post
Share on other sites
T1Oracle    100
I solved that by making my own string class for use in STL maps. It's very simple and can convert from "str *" to "std:string" in it's assingment operator. It also can output those forms using cast operators. Plus it has a "printf" function for generating string using the printf format. I created this class for STL maps since I read somewhere that the "std:string" class was slow in STL maps and since this thing is so simple I figured it would be faster. I also created for all the string conversions that it handles so easily. Here's my code:

#pragma once
#include<string>
#include <stdarg.h>

namespace strLib
{
class qckstr
{
public:
// void constructor
qckstr()
{
m_length=0;
m_pStr=NULL;
}
// copy constructor
qckstr(const qckstr& qStr)
{
m_length=0;
m_pStr=NULL;
Set(qStr.m_pStr);
}
// construct qckstr from a C style string
qckstr(const char *pStr)
{
m_length=0;
m_pStr=NULL;
Set(pStr);
}
// destructor
~qckstr()
{
Destroy();
}
// returns the length of the string
inline unsigned Length() const
{
return m_length;
}
// dealocates memory and resets string
void Destroy()
{
delete [] m_pStr;
m_length=0;
m_pStr=NULL;
}
// resets string to the value of C style string
bool Set(const char *pStr)
{
// check user pointer
if (!pStr||!*pStr)
return false;
// check local pointer
if (m_pStr)
Destroy();
// allocate space and copy string
m_length=strlen(pStr);
m_pStr=new char[m_length+1];
if (!m_pStr)
{
m_length=0;
return false;
}
strcpy(m_pStr,pStr);
return true;
}
// uses the printf syntax to format a string, returns a reference to the result
qckstr &Sprintf(const char *format,...)
{
Destroy();
va_list arglist;
va_start(arglist,format);
m_length=_vsnprintf(NULL,0,format,arglist);
if (!m_length)
return *this;
m_pStr=new char[m_length+1];
if (!m_pStr)
{
m_length=0;
return *this;
}
va_start(arglist,format);
vsprintf(m_pStr,format,arglist);
va_end(arglist);
return *this;
}
// assigns a C style string to qckstr
inline qckstr &operator=(const char *pStr)
{
if (m_pStr!=pStr)
Set(pStr);
return *this;
}
// assigns a stl string to qckstr
inline qckstr &operator=(const std::string &stlStr)
{
if (m_pStr!=stlStr)
Set(stlStr.c_str());
return *this;
}
// assigns a qckstr string to qckstr
inline qckstr &operator=(const qckstr &qStr)
{
if (this!=&qStr)
Set(qStr.m_pStr);
return *this;
}
inline bool operator<(const qckstr &qStr) const
{
return (strcmp(m_pStr,qStr.m_pStr)<NULL);
}
inline bool operator>(const qckstr &qStr) const
{
return (strcmp(m_pStr,qStr.m_pStr)>NULL);
}
inline bool operator==(const qckstr &qStr) const
{
return (strcmp(m_pStr,qStr.m_pStr)==NULL);
}
inline bool operator!=(const qckstr &qStr) const
{
return (strcmp(m_pStr,qStr.m_pStr)!=NULL);
}
inline bool operator<=(const qckstr &qStr) const
{
return (strcmp(m_pStr,qStr.m_pStr)<=NULL);
}
inline bool operator>=(const qckstr &qStr) const
{
return (strcmp(m_pStr,qStr.m_pStr)>=NULL);
}
// casts as a stl string, creates a temporary stl string
inline operator std::string()
{
return std::string(m_pStr);
}
// casts as a C style string (should only be used for const strings)
inline operator const char *()
{
return (const char *)m_pStr;
}
// casts as a qckstr
inline operator const qckstr ()
{
return (const qckstr)*this;
}
protected:
unsigned m_length; // length of string
char *m_pStr; // pointer to string data
};
};


Anyway when I use that class I can do stuff like:
std::map<strLib::qckstr,int> myMap;
myMap["string constant"];
char *str="another constant";
myMap[str];

Share this post


Link to post
Share on other sites
Glak    315
"since I read somewhere that the "std:string" class was slow in STL maps"

Don't listen to rumors. The STL was designed for speed and efficiency. Always use it unless you can PROVE that it is too slow for your purposes.

Share this post


Link to post
Share on other sites
snk_kid    1312
Quote:
Original post by T1Oracle
I solved that by making my own string class for use in STL maps.


There is nothing to solve as the OP made a mistake anyways [grin].

Quote:
Original post by T1Oracle
... I created this class for STL maps since I read somewhere that the "std:string" class was slow in STL maps and since this thing is so simple I figured it would be faster...


Define slow, what aspect is slow? did you profile to know for sure? i don't mean to rude or put you down but your implementation is naive, it doesn't really do any better than a modern imp of std::basic_string. Most modern implementations make std::basic_string nothing more than a handle to a private reference counted representation with COW semantics (copy on write), granted COW semnatics does not have much thread safety but it's better than the greedy navie method the one which your code does among other things.

To get a better understanding you might want to read these articles:

Reference Counting - Part I
Reference Counting - Part II
Reference Counting - Part III.

Those articles use/write custom string type as the example.

Share this post


Link to post
Share on other sites
T1Oracle    100
What if the "lazily" copied string goes out of scope?

link <-Slow STL string performance. I'm sure I found it somewhere else though, but this is all I have right now.

*edit* Also, I only use my class for STL maps and the printf feature, after that I usually convert it to a STL string. I'm most concerned about performance in the STL map since I use those heavily in my code.

Share this post


Link to post
Share on other sites
Enigma    1410
Try posting a benchmark from a compiler which isn't horrendously obsolete.
#include <algorithm>
#include <cstdarg>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <string>
#include <vector>
#include <boost/lambda/algorithm.hpp>
#include <boost/lambda/bind.hpp>
#include <boost/lambda/lambda.hpp>

namespace strLib
{
class qckstr
{
public:
// void constructor
qckstr()
{
m_length=0;
m_pStr=NULL;
}
// copy constructor
qckstr(const qckstr& qStr)
{
m_length=0;
m_pStr=NULL;
Set(qStr.m_pStr);
}
// construct qckstr from a C style string
qckstr(const char *pStr)
{
m_length=0;
m_pStr=NULL;
Set(pStr);
}
qckstr(std::string const & str)
{
m_length=0;
m_pStr=NULL;
Set(str.c_str());
}
// destructor
~qckstr()
{
Destroy();
}
// returns the length of the string
inline unsigned Length() const
{
return m_length;
}
// dealocates memory and resets string
void Destroy()
{
delete [] m_pStr;
m_length=0;
m_pStr=NULL;
}
// resets string to the value of C style string
bool Set(const char *pStr)
{
// check user pointer
if (!pStr||!*pStr)
return false;
// check local pointer
if (m_pStr)
Destroy();
// allocate space and copy string
m_length=strlen(pStr);
m_pStr=new char[m_length+1];
if (!m_pStr)
{
m_length=0;
return false;
}
strcpy(m_pStr,pStr);
return true;
}
// uses the printf syntax to format a string, returns a reference to the result
qckstr &Sprintf(const char *format,...)
{
Destroy();
va_list arglist;
va_start(arglist,format);
m_length=_vsnprintf(NULL,0,format,arglist);
if (!m_length)
return *this;
m_pStr=new char[m_length+1];
if (!m_pStr)
{
m_length=0;
return *this;
}
va_start(arglist,format);
vsprintf(m_pStr,format,arglist);
va_end(arglist);
return *this;
}
// assigns a C style string to qckstr
inline qckstr &operator=(const char *pStr)
{
if (m_pStr!=pStr)
Set(pStr);
return *this;
}
// assigns a stl string to qckstr
inline qckstr &operator=(const std::string &stlStr)
{
if (m_pStr!=stlStr)
Set(stlStr.c_str());
return *this;
}
// assigns a qckstr string to qckstr
inline qckstr &operator=(const qckstr &qStr)
{
if (this!=&qStr)
Set(qStr.m_pStr);
return *this;
}
inline bool operator<(const qckstr &qStr) const
{
return (strcmp(m_pStr,qStr.m_pStr)<0);
}
inline bool operator>(const qckstr &qStr) const
{
return (strcmp(m_pStr,qStr.m_pStr)>0);
}
inline bool operator==(const qckstr &qStr) const
{
return (strcmp(m_pStr,qStr.m_pStr)==0);
}
inline bool operator!=(const qckstr &qStr) const
{
return (strcmp(m_pStr,qStr.m_pStr)!=0);
}
inline bool operator<=(const qckstr &qStr) const
{
return (strcmp(m_pStr,qStr.m_pStr)<=0);
}
inline bool operator>=(const qckstr &qStr) const
{
return (strcmp(m_pStr,qStr.m_pStr)>=0);
}
// casts as a stl string, creates a temporary stl string
inline operator std::string()
{
return std::string(m_pStr);
}
// casts as a C style string (should only be used for const strings)
inline operator const char *() const
{
return (const char *)m_pStr;
}
// casts as a qckstr
inline operator const qckstr () const
{
return (const qckstr)*this;
}
protected:
unsigned m_length; // length of string
char *m_pStr; // pointer to string data
};
};

struct ReverseString
:
std::unary_function< std::string, std::string >
{

public:

std::string operator()(std::string string)
{
std::reverse(string.begin(), string.end());
return string;
}
};

struct ReverseQckstr
:
std::unary_function< strLib::qckstr, strLib::qckstr >
{

public:

strLib::qckstr operator()(strLib::qckstr string)
{
std::string str(string.operator const char *());
std::reverse(str.begin() , str.end());
return strLib::qckstr(str);
}
};

int main()
{
using namespace boost::lambda;
std::ifstream reader("words.lst");
std::deque< std::string > wordsAsStrings;
std::copy(std::istream_iterator< std::string >(reader), std::istream_iterator< std::string >(), std::back_inserter(wordsAsStrings));
std::random_shuffle(wordsAsStrings.begin(), wordsAsStrings.end());
std::deque< strLib::qckstr > wordsAsQckstrs(wordsAsStrings.begin(), wordsAsStrings.end());
std::deque< std::string > reverseWordsAsStrings;
std::transform(wordsAsStrings.rbegin(), wordsAsStrings.rend(), std::back_inserter(reverseWordsAsStrings), ReverseString());
std::deque< strLib::qckstr > reverseWordsAsQckstrs;
std::transform(wordsAsQckstrs.rbegin(), wordsAsQckstrs.rend(), std::back_inserter(reverseWordsAsQckstrs), ReverseQckstr());
std::clock_t times[5];
std::map< std::string, std::string > stringMap;
std::map< strLib::qckstr, strLib::qckstr > qckstrMap;
std::vector< unsigned int > accumulatorString(wordsAsStrings.size(), 0);
std::vector< unsigned int > accumulatorQckstr(wordsAsStrings.size(), 0);
std::vector< unsigned int > randomIndices;
std::generate_n(std::back_inserter(randomIndices), 1000000, bind(std::rand) * wordsAsStrings.size() / RAND_MAX);
times[0] = std::clock();
for (std::deque< std::string >::const_iterator word = wordsAsStrings.begin(), wordsEnd = wordsAsStrings.end(), reverseWord = reverseWordsAsStrings.begin(); word != wordsEnd; ++word, ++reverseWord)
{
stringMap.insert(std::make_pair(*word, *reverseWord));
}
times[1] = std::clock();
for (std::deque< strLib::qckstr >::const_iterator word = wordsAsQckstrs.begin(), wordsEnd = wordsAsQckstrs.end(), reverseWord = reverseWordsAsQckstrs.begin(); word != wordsEnd; ++word, ++reverseWord)
{
qckstrMap.insert(std::make_pair(*word, *reverseWord));
}
times[2] = std::clock();
for (std::vector< unsigned int >::const_iterator wordIndex = randomIndices.begin(), wordIndicesEnd = randomIndices.end(); wordIndex != wordIndicesEnd; ++wordIndex)
{
accumulatorString[*wordIndex] += stringMap[wordsAsStrings[*wordIndex]][0];
}
times[3] = std::clock();
for (std::vector< unsigned int >::const_iterator wordIndex = randomIndices.begin(), wordIndicesEnd = randomIndices.end(); wordIndex != wordIndicesEnd; ++wordIndex)
{
accumulatorQckstr[*wordIndex] += stringMap[wordsAsQckstrs[*wordIndex]][0];
}
times[4] = std::clock();
std::cout << "std::string insert: " << (times[1] - times[0]) << '\n';
std::cout << "std::string lookup: " << (times[3] - times[2]) << '\n';
std::cout << "strLib::qckstr insert: " << (times[2] - times[1]) << '\n';
std::cout << "strLib::qckstr lookup: " << (times[4] - times[3]) << '\n';
}


gcc 3.3.1:
std::string insert: 828
std::string lookup: 3531
strLib::qckstr insert: 1500
strLib::qckstr lookup: 4250

msvc++ 7.1:
std::string insert: 687
std::string lookup: 2828
strLib::qckstr insert: 1125
strLib::qckstr lookup: 3047

That was run on a word list of 173528 words. I did have to add a constructor-from-std::string to your string class. I was also highly tempted to rename it to slowstr.

The reason strings are inefficient with std::map (that's strings in general, not std::string in particular) is because of the algorithm behind std::map and the nature of the English language. The requirements on std::map necessitate the use of some form of balanced binary tree. To lookup in a binary tree you must perform upto log2 comparisons. String comparisons will search through a string until they find a character mismatch. The problem with the English language is that many words share a common prefix (super, under, trans etc.) which means in some cases five or more character comparisons are needed to determine if a word is lexographically before or after another word.

A more efficient system is to use a hashing container, which (with an appropriate hash function) can greatly reduce the number of character comparisons needed.

Enigma

Share this post


Link to post
Share on other sites
Nitage    1107
Quote:
Original post by T1Oracle
What if the "lazily" copied string goes out of scope?

link <-Slow STL string performance. I'm sure I found it somewhere else though, but this is all I have right now.

*edit* Also, I only use my class for STL maps and the printf feature, after that I usually convert it to a STL string. I'm most concerned about performance in the STL map since I use those heavily in my code.


If the lazily copied string goes out of scope, typically the copy gains control of the memory used to store the string.

This is a small implementation detail - copy-on-write is a tried and tested idiom for reducing wasted cpu usage and works very well.


If you are so concerned about speed, I suggest you use a hash table rather than std::map.

Share this post


Link to post
Share on other sites
snk_kid    1312
Quote:
Original post by T1Oracle
link <-Slow STL string performance. I'm sure I found it somewhere else though, but this is all I have right now.


I just checked that link, most of those results are pretty much useless just as VC++ 6.0 is altogether a useless C++ compiler. VC++ 6.0 has poor standard compliance and a mediocre implementation of the C++ standard library, is almost 8-10 years old technology, it's development/release predates C++ ISO standardization what do you expect?.

Quote:
Original post by T1Oracle
Also, I only use my class for STL maps and the printf feature, after that I usually convert it to a STL string.


Be careful with variable argument lists in C++ you can only use POD-types with them. Consider string streams or boost::lexical_cast (which uses string streams internally) and boost::format for printf style format string.

Quote:
Original post by T1Oracle
I'm most concerned about performance in the STL map since I use those heavily in my code.


Well use a modern, update C++ compiler and profile first. Also note that all standard library containers are parameterized by allocator type, usually the last template type parameter which defaults to use std::allocator this is even the case for std::basic_string. You could use a pooled allocator for both std::map and std::basic_string better yet use it with hash_map/std::tr1::unordered_map if your compiler supports those std lib extensions.

Share this post


Link to post
Share on other sites
DrEvil    1148
Thats the most retarted article I've seen in a while.

std::map<int, sometype>
vs
std::map<char*, sometype>
vs
std::map<string, sometype>

aren't even doing the same thing. attempting to perform a lookup using a char* as the key sounds to be like its asking for trouble, because a char* could be pointing to the same string value but the pointers would have different values, resulting in a failed find(). There really isnt much difference in using int and char* as the key unless some compiler magic is turning it into a strcmp as a char* specialization or something(is it?).

If you really demand a string key you would be better off hashing the key and storing the numeric hash in the map as the key.

Share this post


Link to post
Share on other sites
Enigma    1410
Quote:
Original post by snk_kid
I just checked that link, most of those results are pretty much useless just as VC++ 6.0 is altogether a useless C++ compiler. VC++ 6.0 has poor standard compliance and a mediocre implementation of the C++ standard library, is almost 8-10 years old technology, it's development/release predates C++ ISO standardization what do you expect?.

I didn't realise at first, but it's even worse than that. Check the sourcecode of the profiled program. [lol]

Enigma

Share this post


Link to post
Share on other sites
snk_kid    1312
Quote:
Original post by Enigma
I didn't realise at first, but it's even worse than that. Check the sourcecode of the profiled program. [lol]


I think you've said enough for me to not need to look [grin]. It just goes to show always take online resources with a very fine grain of salt.

Share this post


Link to post
Share on other sites
T1Oracle    100
Interesting, although hashes have the problem of their unpredictable collisions. I also like the simplicity of being able to do this:

SOMEHASHMAP_t myMap;
const char key[]="some key";
myMap[key]; // returns the value stored at that key


I guess now I have to do some more research to find a good way of achieving that. I just want fast, safe, associative arrays in C++.

Share this post


Link to post
Share on other sites
DrEvil    1148
Quote:
Original post by T1Oracle
... I also like the simplicity of being able to do this:
*** Source Snippet Removed ***
...


A hash_map would likely give you better performance for large key/value lookups with a string key.

The problem AFAIK with a char* as the key is that the actual pointer value is the lookup, which has little to do with the string that is being pointed to. With string pooling by the compiler this may work in many cases, especially if your lookups are hard coded in the code such as your example.

Your code snippet would work fine if your key is an std::string, because it will create an std::string from your char * to do the lookup with. If more speed is what you need try a stdext::hash_map.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this