map as efficient as switch

[Christoph Rabel]

Hi!

I'm often using map sometimes to replace switch.

Something according to:

map.insert(make_pair(key, &somefunction);
map.insert(make_pair(key2, &somefunction2);
....

Now, while map is entirely sufficient for me, fast enough
and all, I am just wondering if this can be more efficiently
done.

Is there a container or some implementation that is better
suited for this approach than map?

thx,

Christoph

 

[Ron Natalie]

Hi!

I'm often using map sometimes to replace switch.

Map is O(log n) to look things up. Switch is typically
O(n) or O(1) depending on whether or not it decides
to use a jump table. Of course, the big issue with switch
is that it only works with integers/enums and it can't be
changed at runtime.,

 

[Jeff Schwab]

Hi!

I'm often using map sometimes to replace switch.

Something according to:

map.insert(make_pair(key, &somefunction);
map.insert(make_pair(key2, &somefunction2);
...

Now, while map is entirely sufficient for me, fast enough and all, I am
just wondering if this can be more efficiently done.

Is there a container or some implementation that is better suited for
this approach than map?

You could use a hash instead of a map, but there is none in the standard
library. Are your programs meant to run on only a particular system, or
do they need the portability that comes with compliance to the standard?

 

[Gianni Mariani]

Map is O(log n) to look things up. Switch is typically
O(n) or O(1) depending on whether or not it decides
to use a jump table. Of course, the big issue with switch
is that it only works with integers/enums and it can't be
changed at runtime.,

You may use a hash map instead (which in theory gives O(1) time). hash
map is not part of the standard STL but it is provided by most compilers
and it follows the same stl container interface design.

 

[Christoph Rabel]

You could use a hash instead of a map, but there is none in the standard
library. Are your programs meant to run on only a particular system, or
do they need the portability that comes with compliance to the standard?

No. The question simply appeared, without a concrete problem
to solve. I am just wondering...

I simply wanted to know if there is a container or something
that is more suited to the task than map.

Something along template Metaprogramming that constructs a
switch/lookup table for me.

Maybe with some restrictions (only ints or something like that).
And maybe this is just a weird thought.

I thought of something along a fixed size map. Where the
objects/function pointers are inserted is calculated at
compile time and lookup is maybe a bit better than log n.
[Insertion is not really an issue, but the lookup should be
as fast as possible]

cu

Christoph

 

[Gianni Mariani]

You could use a hash instead of a map, but there is none in the
standard library. Are your programs meant to run on only a particular
system, or do they need the portability that comes with compliance to
the standard?

No. The question simply appeared, without a concrete problem to solve. I
am just wondering...

I simply wanted to know if there is a container or something that is
more suited to the task than map.

Something along template Metaprogramming that constructs a switch/lookup
table for me.

Maybe with some restrictions (only ints or something like that).
And maybe this is just a weird thought.

I thought of something along a fixed size map. Where the
objects/function pointers are inserted is calculated at compile time and
lookup is maybe a bit better than log n.
[Insertion is not really an issue, but the lookup should be as fast as
possible]

Virtual methods solve this problem like you just described (ok - it may
be a bit of s stretch).

This is what I mean : instead of using enums, use a class. Derive new
classes with a behaviour specific to that enum. In this ReallyBad(TM)
example there is a header describing a "Material" is and materials
affect the behaviour of "Heating" and "Bending". A Shape describes the
shape of an object and a material can "look into" the shape and change
it depending on how what material it is.



//
// Header
//
struct Shape;
struct Angle;
struct Temperature;

struct Material
{
virtual ~Material(){}

virtual void Bend( Shape &, const Angle & ) const = 0;
virtual void Heat( Shape &, const Temperature & ) const = 0;

bool operator== ( const Material & lhs ) const
{
return this == & lhs;
}
};

extern const Material & Glass;
extern const Material & Steel;


// materials.cpp
//
// Material details
//

namespace
{

struct Glass_Material : Material
{
virtual void Bend( Shape &, const Angle & ) const;
virtual void Heat( Shape &, const Temperature & ) const;
};

Glass_Material g_Glass_Material;


struct Steel_Material : Material
{
virtual void Bend( Shape &, const Angle & ) const;
virtual void Heat( Shape &, const Temperature & ) const;
};

Steel_Material g_Steel_Material;

};

const Material & Glass = g_Glass_Material;
const Material & Steel = g_Steel_Material;

// application.cpp
//
// application code - knows nothing about implementations
//

void DoSomthing( Shape & i_shape, const Temperature & i_temp, const
Angle & i_angle )
{
Glass.Heat( i_shape, i_temp );
Glass.Bend( i_shape, i_angle );

const Material & mat_1 = Glass;
const Material & mat_2 = Steel;

if ( mat_1 == mat_2 )
{
// glass can't be the same as steel
}
}

 

[Jonathan Turkanis]

I simply wanted to know if there is a container or something
that is more suited to the task than map.

Something along template Metaprogramming that constructs a
switch/lookup table for me.

Maybe with some restrictions (only ints or something like that).
And maybe this is just a weird thought.

I thought of something along a fixed size map. Where the
objects/function pointers are inserted is calculated at
compile time and lookup is maybe a bit better than log n.
[Insertion is not really an issue, but the lookup should be
as fast as possible]

Metaprogramming can allow you to build the table at compile time, but
it won't solve your problem. Briefly, metaprogramming can handle
intergral values only if they're constant expressions (e.g., '3').
Even if you have a compile-time table, at runtime you will still have
to take an ordinary runtime value and map it to a constant expression.
This can be done easily, but it is no easier than your original
problem.

C++ does have a data structure representing a fixed size map with
intergral keys. It's called an 'array'. If you really know in advance
what the entries should be, and if the keys are not too spread out,
you can use an array of function pointers, with almost instantaneous
access to any element.

Jonathan

 

[Chris Theis]

You could use a hash instead of a map, but there is none in the standard
library. Are your programs meant to run on only a particular system, or
do they need the portability that comes with compliance to the standard?

No. The question simply appeared, without a concrete problem
to solve. I am just wondering...

I simply wanted to know if there is a container or something
that is more suited to the task than map.

Something along template Metaprogramming that constructs a
switch/lookup table for me.

Maybe with some restrictions (only ints or something like that).
And maybe this is just a weird thought.

I thought of something along a fixed size map. Where the
objects/function pointers are inserted is calculated at
compile time and lookup is maybe a bit better than log n.
[Insertion is not really an issue, but the lookup should be
as fast as possible]

One possibility would be to use just an array of function pointers as it is
often done for table driven state machines. Something like:

#define DF(N,I) void N( int& Index) { Index = I; cout << "function " #N "
called..." << endl; }
DF(a, 1); DF(b, 3); DF(c, 4); DF(d, 2);
void (*func_table[])( int& Index) = { a, b, c, d, e };

At least the compiler will be able to construct the LUT at compile time.
However, whether this solution is preferable to a map is arguable, as you're
for example bound to use integers as indices.

Cheers
Chris

 

[EventHelix.com]

Map is O(log n) to look things up. Switch is typically

O(n) or O(1) depending on whether or not it decides
to use a jump table. Of course, the big issue with switch
is that it only works with integers/enums and it can't be
changed at runtime.,

Some compilers use a binary search in a very large switch
statement so it might be O (log n) in using the switch statement.
However, a switch statement with that many entries is difficult
to maintain.

The following article covers the handling for different
CASE statement scenarios:

http://www.eventhelix.com/RealtimeMantra/Basics/CToAssemblyTranslation3.htm

Sandeep

 

[Thomas Matthews]

Hi!

I'm often using map sometimes to replace switch.

Something according to:

map.insert(make_pair(key, &somefunction);
map.insert(make_pair(key2, &somefunction2);
...

Now, while map is entirely sufficient for me, fast enough and all, I am
just wondering if this can be more efficiently done.

Is there a container or some implementation that is better suited for
this approach than map?

thx,

Christoph

I prefer using a constant table (array). Tables don't
have to be initialized during run-time and can be
const and initalized by the compiler.

If the table is big enough, a binary search or other
search may save time. However, most of the function
tables that I've created were small so that the time
difference between a linear search and a binary one
was negligable (sp!). If the table is small enough,
the binary search may take longer!

Also, with the table, one can use multiple keys and
build different search algorithms based on the keys.
BTW, the table is an array of structs/classes.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book