The other kind of map?

[Steven T. Hatton]

There are probably a zillion ways to do this, but I'm wondering of there's a
C++ convention. I want to have a fixed mapping between keys and values.
It's basically the same thing as a std::map<>, except what I'm talking
about would not create a new element on a miss. This is a traditional
approach I've seen with C and other languages.
string
SectionTypes( Elf32_Word type )
{
string sRet = "UNKNOWN";
switch ( type ) {
case SHT_NULL :
sRet = "NULL";
break;
case SHT_PROGBITS :
sRet = "PROGBITS";
break;
case SHT_SYMTAB :
sRet = "SYMTAB";
break;
case SHT_STRTAB :
sRet = "STRTAB";
break;
case SHT_RELA :
sRet = "RELA";
break;
case SHT_HASH :
sRet = "HASH";
break;
case SHT_DYNAMIC :
sRet = "DYNAMIC";
break;
case SHT_NOTE :
sRet = "NOTE";
break;
case SHT_NOBITS :
sRet = "NOBITS";
break;
case SHT_REL :
sRet = "REL";
break;
case SHT_SHLIB :
sRet = "SHLIB";
break;
case SHT_DYNSYM :
sRet = "DYNSYM";
break;
}

return sRet;
}

If I were to use a switch method, I'd return from the case rather than
falling off the end. Even that seems a bit too clunky for me. std::map<>
is good for what it's designed for, but it doesn't work for fixed sets with
a default for cases where there's no key to match the sample.

I know this is trivial, but it's the kind of thing I find myself fretting
over more than seems necessary. Everytime I encounter the situation I toy
around with a solution, but I've never found the "right fit". Any
suggestions for a nice, concise, flexible way of setting up this kind of
associative mapping.

I could use a set of std::pair<key,v alue>, and provide a comparator, but
that seems unnecessarily complicated for the situation. Using a std::map<>
and doing a find likewise seems excessive.

--
If our hypothesis is about anything and not about some one or more
particular things, then our deductions constitute mathematics. Thus
mathematics may be defined as the subject in which we never know what we
are talking about, nor whether what we are saying is true.-Bertrand Russell

[Alf P. Steinbach]

* Steven T. Hatton:

std::map<>
is good for what it's designed for, but it doesn't work for fixed sets with
a default for cases where there's no key to match the sample.

How about wrapping a std::map in your own little class with your own
accessor, where you use 'find'?

--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?

[Steven T. Hatton]

Alf P. Steinbach wrote:

* Steven T. Hatton:

std::map<>
is good for what it's designed for, but it doesn't work for fixed sets
with a default for cases where there's no key to match the sample.

How about wrapping a std::map in your own little class with your own
accessor, where you use 'find'?

I guess a variant on this theme is what you're talking about. That's among
the best I've come up with so far.

#ifndef FILEDUMPER_H
#define FILEDUMPER_H

#include <string>
#include <map>
#include <iostream>

class FileDumper {
public:

FileDumper(cons t std::string& filename_);

~FileDumper();

std::string SectionFlags(El f32_Word flags);
std::string SectionTypes(El f32_Word type);
std::string SegmentTypes( Elf32_Word type );
//...

private:
std::string _filename;
std::map<Elf32_ Word,std::strin g> _sectionTypes;
std::map<Elf32_ Word,std::strin g> _segmentTypes;
};
#endif

/*************** *************** ***************/

FileDumper::Fil eDumper(const std::string& filename_)
:_filename(file name_) {
_sectionTypes[SHT_NULL] = "NULL";
_sectionTypes[SHT_PROGBITS] = "PROGBITS";
_sectionTypes[SHT_SYMTAB] = "SYMTAB";
_sectionTypes[SHT_STRTAB] = "STRTAB";
_sectionTypes[SHT_RELA] = "RELA";
_sectionTypes[SHT_HASH] = "HASH";
_sectionTypes[SHT_DYNAMIC] = "DYNAMIC";
_sectionTypes[SHT_NOTE] = "NOTE";
_sectionTypes[SHT_NOBITS] = "NOBITS";
_sectionTypes[SHT_REL] = "REL";
_sectionTypes[SHT_SHLIB] = "SHLIB";
_sectionTypes[SHT_DYNSYM] = "DYNSYM";

_segmentTypes[PT_NULL] = "NULL";
_segmentTypes[PT_LOAD] = "PT_LOAD";
_segmentTypes[PT_DYNAMIC] = "PT_DYNAMIC ";
_segmentTypes[PT_INTERP] = "PT_INTERP" ;
_segmentTypes[PT_NOTE] = "PT_NOTE";
_segmentTypes[PT_SHLIB] = "PT_SHLIB";
_segmentTypes[PT_PHDR] = "PT_PHDR";

}

FileDumper::~Fi leDumper() {}

std::string FileDumper::Sec tionFlags(Elf32 _Word flags) {
std::string sRet = "";
if ( flags & SHF_WRITE ) { sRet += "W"; }
if ( flags & SHF_ALLOC ) { sRet += "A"; }
if ( flags & SHF_EXECINSTR ) { sRet += "X"; }
return sRet;
}

std::string FileDumper::Sec tionTypes(Elf32 _Word type) {
return(_section Types.end()!=_s ectionTypes.fin d(type))?_secti onTypes[type]:
"UNKNOWN";
}

--
If our hypothesis is about anything and not about some one or more
particular things, then our deductions constitute mathematics. Thus
mathematics may be defined as the subject in which we never know what we
are talking about, nor whether what we are saying is true.-Bertrand Russell

[Kai-Uwe Bux]

Steven T. Hatton wrote:

There are probably a zillion ways to do this, but I'm wondering of there's
a
C++ convention. I want to have a fixed mapping between keys and values.
It's basically the same thing as a std::map<>, except what I'm talking
about would not create a new element on a miss. This is a traditional
approach I've seen with C and other languages.
string
[big switch snipped]
If I were to use a switch method, I'd return from the case rather than
falling off the end. Even that seems a bit too clunky for me. std::map<>
is good for what it's designed for, but it doesn't work for fixed sets
with a default for cases where there's no key to match the sample.

I know this is trivial, but it's the kind of thing I find myself fretting
over more than seems necessary. Everytime I encounter the situation I toy
around with a solution, but I've never found the "right fit". Any
suggestions for a nice, concise, flexible way of setting up this kind of
associative mapping.

I could use a set of std::pair<key,v alue>, and provide a comparator, but
that seems unnecessarily complicated for the situation. Using a
std::map<> and doing a find likewise seems excessive.

What about:

#include <map>

template < typename KeyType,
typename ValueType >
class dictionary {
public:

typedef KeyType key_type;
typedef ValueType value_type;

private:

typedef std::map< key_type, value_type > map_type;

map_type data;
value_type answer_default;

public:

dictionary ( value_type default_value = value_type() )
: data ()
, answer_default ( default_value )
{}

dictionary add_pair ( key_type const & key,
value_type const & val ) const {
dictionary result ( *this );
result.data[key] = val;
return( result );
}

value_type const & operator[] ( key_type const & key ) const {
typename map_type::const _iterator iter = data.find( key );
if ( iter != data.end() ) {
return( iter->second );
} else {
return( answer_default );
}
}

}; // dictionary<>
#include <iostream>
#include <string>

int main ( void ) {
dictionary< int, std::string > dict =
dictionary<int, std::string> ( "!" )
.add_pair( 0, "hello" )
.add_pair( 1, " " )
.add_pair( 2, "world" );

for ( int i = 0; i < 5; ++i ) {
std::cout << dict[i];
}
std::cout << '\n';
}
Best

Kai-Uwe Bux

[Steven T. Hatton]

Kai-Uwe Bux wrote:

Steven T. Hatton wrote:

There are probably a zillion ways to do this, but I'm wondering of
there's a
C++ convention. I want to have a fixed mapping between keys and values.
It's basically the same thing as a std::map<>, except what I'm talking
about would not create a new element on a miss. This is a traditional
approach I've seen with C and other languages.
string

[big switch snipped]

If I were to use a switch method, I'd return from the case rather than
falling off the end. Even that seems a bit too clunky for me.
std::map<> is good for what it's designed for, but it doesn't work for
fixed sets with a default for cases where there's no key to match the
sample.

I know this is trivial, but it's the kind of thing I find myself fretting
over more than seems necessary. Everytime I encounter the situation I
toy
around with a solution, but I've never found the "right fit". Any
suggestions for a nice, concise, flexible way of setting up this kind of
associative mapping.

I could use a set of std::pair<key,v alue>, and provide a comparator, but
that seems unnecessarily complicated for the situation. Using a
std::map<> and doing a find likewise seems excessive.

What about:

#include <map>

template < typename KeyType,
typename ValueType >
class dictionary {
public:

typedef KeyType key_type;
typedef ValueType value_type;

private:

typedef std::map< key_type, value_type > map_type;

map_type data;
value_type answer_default;

public:

dictionary ( value_type default_value = value_type() )
: data ()
, answer_default ( default_value )
{}

dictionary add_pair ( key_type const & key,
value_type const & val ) const {
dictionary result ( *this );
result.data[key] = val;
return( result );
}

value_type const & operator[] ( key_type const & key ) const {
typename map_type::const _iterator iter = data.find( key );
if ( iter != data.end() ) {
return( iter->second );
} else {
return( answer_default );
}
}

}; // dictionary<>
#include <iostream>
#include <string>

int main ( void ) {
dictionary< int, std::string > dict =
dictionary<int, std::string> ( "!" )
.add_pair( 0, "hello" )
.add_pair( 1, " " )
.add_pair( 2, "world" );

for ( int i = 0; i < 5; ++i ) {
std::cout << dict[i];
}
std::cout << '\n';
}
Best

Kai-Uwe Bux

Indeed. There are many ways to approach this situation. It just seems a
shame to write so many lines of code to do something so trivial. My guess
is someone considered providing

const T& operator[](const key_type& x) const;

which would behave in much the way I want my other_map to behave. It
probably was rejected because of the subtleties involved in using in
correctly.

I'm currently toying with the idea of an

//or should it be char, or long, or unsigned, or????
template <const int, typename Mapped_T>
class int_keyed_pair {
typedef const int key_type;
typedef Mapped_T mapped_type;
operator const key_type& () const;
};

and trying to figure out if I can get it to behave correctly in
circumstances such as the case constant expression in a switch() statement.
I also want the key to automagically morph into a std::string when
appropriate. The mapped_type should (also) be (convertable to) a
std::string.

It's the kind of thing that has often seemed marginally useful. Of course
the first place I want to use it is as an element in a key_map<Key_T,
Mapped_T>.

BTW, as counterintuitiv e as it may seem, the actual name given to the type
of the other half of a key-value pair in a std::map<> is as shown in the
following:

namespace std {
template <class Key, class T, class Compare = less<Key>,
class Allocator = allocator<pair< const Key, T> > >
class multimap {
public:
typedef Key key_type;
typedef T mapped_type;
typedef pair<const Key,T> value_type;
//...
};
}
--
If our hypothesis is about anything and not about some one or more
particular things, then our deductions constitute mathematics. Thus
mathematics may be defined as the subject in which we never know what we
are talking about, nor whether what we are saying is true.-Bertrand Russell

[Kai-Uwe Bux]

Steven T. Hatton wrote:

I'm currently toying with the idea of an

//or should it be char, or long, or unsigned, or????
template <const int, typename Mapped_T>
class int_keyed_pair {
typedef const int key_type;
typedef Mapped_T mapped_type;
operator const key_type& () const;
};

and trying to figure out if I can get it to behave correctly in
circumstances such as the case constant expression in a switch()
statement. I also want the key to automagically morph into a std::string
when
appropriate. The mapped_type should (also) be (convertable to) a
std::string.

You are thinking of some kind of two-faced type that will convert silently
to either an int or a string so that a variable of that type could be used
like so:

Smart_Error_Cod e exit_code = some_function() ;
std::cerr << exit_code << '\n';
switch exit_code {
case NO_RET : {...}
....
}

Here NO_RET would also be of type Smart_Error_Cod e. I played around with it
for a little while, but I was not able to get the implicit conversion work
out properly. Damn code would not compile.

It's the kind of thing that has often seemed marginally useful. Of course
the first place I want to use it is as an element in a key_map<Key_T,
Mapped_T>.
Does not the two-faced type already represent the map? Obviously I am
missing something.

BTW, as counterintuitiv e as it may seem, the actual name given to the
type of the other half of a key-value pair in a std::map<> is as shown in
the following:

namespace std {
template <class Key, class T, class Compare = less<Key>,
class Allocator = allocator<pair< const Key, T> > >
class multimap {
public:
typedef Key key_type;
typedef T mapped_type;
typedef pair<const Key,T> value_type;
//...
};
}

You are right.
BTW, I revisited the first posting. Here is a version of the dictionary that
uses expression templates to unroll the checks at compile time. It could
compile to something rather close to your original code:

// I am practicing expression templates right now, so here you go:

struct not_found {};

template < typename Key,
typename Map >
class DictionaryEntry {
public:

typedef Key key_type;
typedef Map mapped_type;

private:

key_type const entry_key;
mapped_type const entry_map;

public:

DictionaryEntry ( key_type const & key,
mapped_type const & val )
: entry_key ( key )
, entry_map ( val )
{}

mapped_type lookup ( key_type const & key ) const {
if ( entry_key == key ) {
return( entry_map );
}
throw ( not_found() );
}

};

template < typename SubExprA, typename SubExprB >
class DictionaryExpr {
public:

typedef typename SubExprB::key_t ype key_type;
typedef typename SubExprB::mappe d_type mapped_type;

private:

// WARNING: [references?]
/*
I really would like to know, why I cannot
use const references here.
*/
SubExprA const a;
SubExprB const b;

public:

DictionaryExpr ( SubExprA const & a_,
SubExprB const & b_ )
: a ( a_ )
, b ( b_ )
{}

mapped_type lookup ( key_type const & key ) const {
try {
return( b.lookup( key ) );
}
catch ( not_found ) {}
return( a.lookup( key ) );
}

DictionaryExpr< DictionaryExpr, SubExprB >
add_pair ( key_type const & key, mapped_type const & val ) const {
return( DictionaryExpr< DictionaryExpr, SubExprB >
( *this, DictionaryEntry < key_type, mapped_type >( key, val ) ) );
}

};

template < typename Map >
class DictionaryDefau lt {
public:

typedef Map mapped_type;

private:

mapped_type entry_map;

public:

DictionaryDefau lt ( mapped_type val = mapped_type() )
: entry_map ( val )
{}

template < typename Key >
mapped_type lookup ( Key const & key ) const {
return( entry_map );
}

template < typename Key >
DictionaryExpr< DictionaryDefau lt, DictionaryEntry < Key, mapped_type > >
add_pair ( Key const & key, mapped_type const & val ) const {
return( DictionaryExpr< DictionaryDefau lt, DictionaryEntry < Key,
mapped_type > >
( *this, DictionaryEntry < Key, mapped_type >( key, val ) ) );
}

};

#include <iostream>
#include <string>

std::string find_word( unsigned long i ) {
return
DictionaryDefau lt<std::string> ( "!" )
.add_pair( 0, "hello" )
.add_pair( 1, " " )
.add_pair( 2, "world" )
.lookup( i );
}

int main ( void ) {
for ( unsigned int i = 0; i < 4; ++i ) {
std::cout << find_word( i );
}
std::cout << '\n';
}

// This is one of the most complicated hello.cc that I have written so far.

Best

Kai-Uwe Bux

[Frank Chang]

Kai-Uwe Bux, I think your dictionary class is very nice. I tinkered
around with it:

template < typename KeyType,
typename ValueType >
class dictionary {
public:
typedef KeyType key_type;
typedef ValueType value_type;

private:
typedef std::map< key_type, value_type > map_type;

mutable map_type data; // made this mutable
value_type answer_default;

public:
dictionary ( value_type default_value = value_type() )
: data ()
, answer_default ( default_value )
{}

// return by reference instead of by value
dictionary& add_pair ( key_type const & key,
value_type const & val ) const {
data[key] = val;
return(const_ca st<dictionary&> (*this));
}
value_type const & operator[] ( key_type const & key ) const {
typename map_type::const _iterator iter = data.find( key );
if ( iter != data.end() ) {
return( iter->second );
} else {
return( answer_default );
}
}
}; // dictionary<>

I tested it using your test cases and it still works. Could you please
explain the merits of returning by value in the member function
add_pair() versus returning by reference in add_pair()? Thank you.

[Kai-Uwe Bux]

Frank Chang wrote:

Kai-Uwe Bux, I think your dictionary class is very nice. I tinkered
around with it:

template < typename KeyType,
typename ValueType >
class dictionary {
public:
typedef KeyType key_type;
typedef ValueType value_type;

private:
typedef std::map< key_type, value_type > map_type;

mutable map_type data; // made this mutable
value_type answer_default;

public:
dictionary ( value_type default_value = value_type() )
: data ()
, answer_default ( default_value )
{}

// return by reference instead of by value
dictionary& add_pair ( key_type const & key,
value_type const & val ) const {
data[key] = val;
return(const_ca st<dictionary&> (*this));
}
value_type const & operator[] ( key_type const & key ) const {
typename map_type::const _iterator iter = data.find( key );
if ( iter != data.end() ) {
return( iter->second );
} else {
return( answer_default );
}
}
}; // dictionary<>

I tested it using your test cases and it still works. Could you please
explain the merits of returning by value in the member function
add_pair() versus returning by reference in add_pair()? Thank you.

I do not see any merits in returning by value. I just wasn't thinking.
Thanks a lot for spotting.

As for your code, why not go all the way and just not pretend that
add_pair() is a const method:

template < typename KeyType,
typename MappedType >
class dictionary {
public:

typedef KeyType key_type;
typedef MappedType mapped_type;

private:

typedef std::map< key_type, mapped_type > map_type;

map_type data;
mapped_type answer_default;

public:

dictionary ( mapped_type default_value = mapped_type() )
: data ()
, answer_default ( default_value )
{}

dictionary & add_pair ( key_type const & key,
mapped_type const & val ) {
data[key] = val;
return( *this );
}
mapped_type const & operator[] ( key_type const & key ) const {
typename map_type::const _iterator iter = data.find( key );
if ( iter != data.end() ) {
return( iter->second );
} else {
return( answer_default );
}
}
}; // dictionary<>
Should be equivalent to your code, but without const-cast / mutable.
Best

Kai-Uwe Bux

[Frank Chang]

Kai-Uwe Bux, Your approach is the most elegant. Thank you for reviewing
the code I posted.

[Steven T. Hatton]

Kai-Uwe Bux wrote:

Steven T. Hatton wrote:
[...]
You are thinking of some kind of two-faced type that will convert silently
to either an int or a string so that a variable of that type could be used
like so:

Smart_Error_Cod e exit_code = some_function() ;
std::cerr << exit_code << '\n';
switch exit_code {
case NO_RET : {...}
...
}

Here NO_RET would also be of type Smart_Error_Cod e. I played around with
it for a little while, but I was not able to get the implicit conversion
work out properly. Damn code would not compile.

Actually, I was combining a few such musings into a single design idea.
Probably a bad idea at this stage. The most important behavior would be
something such as:

MagicPair<int, std::string> mp(42, "SuSE Linux 4.2");

switch(key) {
case mp: return "The first version of SuSE Linux.";//as if mp===42;
}

std::cout<<mp<< std::endl;
// prints `SuSE Linux 4.2'

It's the kind of thing that has often seemed marginally useful. Of
course the first place I want to use it is as an element in a
key_map<Key_T, Mapped_T>.

Does not the two-faced type already represent the map? Obviously I am
missing something.

Probably because my thinking, and hence my words are not clear. I want
something that I can easily print out in a for-each loop as key/value
pairs. The auto-conversion to std::string for the key was "additional
support". That would be for situations such as are dealt with by this bit
of code:

http://www.research.att.com/~bs/bs_f...#int-to-string

It would probably be sufficient to have something along the lines of

MagicPair<>::ke y_as_string();

BTW, as counterintuitiv e as it may seem, the actual name given to the
type of the other half of a key-value pair in a std::map<> is as shown in
the following:

namespace std {
template <class Key, class T, class Compare = less<Key>,
class Allocator = allocator<pair< const Key, T> > >
class multimap {
public:
typedef Key key_type;
typedef T mapped_type;
typedef pair<const Key,T> value_type;
//...
};
}

You are right.
BTW, I revisited the first posting. Here is a version of the dictionary
that uses expression templates to unroll the checks at compile time. It
could compile to something rather close to your original code:

[snip for further review]

Now I've done it! I opened my mouth, and now people are expecting me to
_think_! I'll take a closer look at your code before commenting on it.

I will observe that in another post you provided this:

value_type const & operator[] ( key_type const & key ) const {
typename map_type::const _iterator iter = data.find( key );
if ( iter != data.end() ) {
return( iter->second );
} else {
return( answer_default );
}

Which suggests you are aware of the gotcha related to std::map::opera tor[
(key) const;
This is my current hack to address the original issue:

template<typena me K, typename M>
class KeyMap_T {
public:
typedef std::map<K,M> map_type;

KeyMap_T(const map_type& map_, const M& default_)
:_map(map_.begi n(), map_.end())
,_default(defau lt_)
{}

// Big dilemma: If I explicitly create a variable of iterator type, I avoid
// calling _map.find(k) twice. But I cannot accomplish that in one line of
// moderately sane code. I'm not sure which version an optimizer will
// prefer.
const std::string& operator[](const K& k) const {
return _map.find(k) != _map.end()? _map.find(k)->second: _default;
}

private:
map_type _map;
M _default;
};

//---------------------------------------

typedef KeyMap_T<Elf32_ Word,std::strin g> Elf32_WordMap;
Elf32_WordMap:: map_type mapSectionHeade r();
const Elf32_WordMap sectionHeaderKe yMap(mapSection Header(),"UNKNO WN ");

// I had a KeyMap_T<>::add (const key_type& k, const mapped_type& m), but I
// wasn't using it, so I removed it. What I have may appear hackish, but it
// is the most comfortable version I came up with.

Elf32_WordMap:: map_type mapSectionHeade r() {
Elf32_WordMap:: map_type m;

m[SHT_NULL] = "NULL ";
m[SHT_PROGBITS] = "PROGBITS";
m[SHT_SYMTAB] = "SYMTAB ";
m[SHT_STRTAB] = "STRTAB ";
m[SHT_RELA] = "RELA ";
m[SHT_HASH] = "HASH ";
m[SHT_DYNAMIC] = "DYNAMIC ";
m[SHT_NOTE] = "NOTE ";
m[SHT_NOBITS] = "NOBITS ";
m[SHT_REL] = "REL ";
m[SHT_SHLIB] = "SHLIB ";
m[SHT_DYNSYM] = "DYNSYM ";
return m;
}
I don't like the return by value, but the alternative is to create `m' in
the calling scope, which is a bother.
--
If our hypothesis is about anything and not about some one or more
particular things, then our deductions constitute mathematics. Thus
mathematics may be defined as the subject in which we never know what we
are talking about, nor whether what we are saying is true.-Bertrand Russell