Data structure similar to a 2-argument map

Is there a data structure (readily available in STL or boost), that accepts two arguments and maps it to a certain value?

Examples would be for returning certain information in a coordinate grid or getting the weight of an edge in a graph:

coordinate_quadrant(-1,-1) = 3

weight_of(u,v) = 10

The quadrant example could be done in a simple function with four if statements. I'm mainly looking for an example that would suit the weight example. I'm trying to avoid having to create an edge class and pass that into the weight_of(Edge edge) function.

-------------Problems Reply------------

You could use std::map< std::pair<Type1,Type2>, Type3 >.

I would consider the following choices:

Option 1

std::map with std::pair< Type1, Type2 > as the key and Type3 as the value

std::map< std::pair< Type1, Type2 >, Type3 > data;

Option 2

2-dimensional std::vector

In case that the Type1 and Type2 are integers, as you might find when modeling a graph or Cartesian space: std::vector< std::vector< Type3 > > data;

Option 3

user-defined class containing Type1 and Type2, which can be mapped to Type3

In case you might ever want to decorate your two types with more values, you could define a class that contains both of your types, and use a std::map to map it to the third type:

public:
MyClass( Type1 x, Type2 y ) : x_( x ), y_( y )

Type1 x() const {
return x_;
}

Type2 y() const {
return y_;
}

private:
Type1 x_;
Type2 y_;
};

std::map< MyClass, Type3 > data;

The benefit of Option 1 is that it's really fast and easy to code, and should make sense to anyone who knows C++. Option 2 is likely a small bit faster, and has the added benefit that it can easily be modified to have more dimensions. The downside of Option 2 is that your values need to be integer indices into the 2-dimensional vector.

In my opinion Option 3 is the best choice to me because it's readable, places no requirements on the type of Type1 and Type2, and can be extended to contain more data in a very reasonable way. The downside to Option 3 is that you need to define a StrictWeakOrdering for comparing MyClass objects to each other, but that's fairly straightforward:

bool operator<(const MyClass & rhs) const {
return ( rhs.x() <= x() && rhs.y() <= y() );
}

Make that a member function of your class, and you should be ready to go.

Like many things in programming, there's not an obvious right answer until you consider the specifics of what you're doing and how much time you're willing to invest. Don't forget to check for key existence and out-of-bounds errors. :)

Use an object that is a pair of integers on the back end. In other words, implement map, but for this pair object. You can't override operator [] to accept multiple arguments, but you can override operator () on a custom map class, so you can get some syntactical sugar e.g. my_map[row](col) = whatever

Category:c# Views:0 Time:2009-07-13
Tags: c# data structure

Related post

  • C# Collection Data Structure With 1:1 Key/Value Mapping 2008-11-05

    Are there any built-in C# data structures that are like a hash table but requires both the Keys and the Values to be unique among each other? I basically want a way to look up my Key object in a table via a unique Value and vice-versa. Next to mainta

  • What kind of data structure we should use to create map like Google map? 2010-12-21

    If you had to indicate travel directions visually on a map (like say Google maps), what data structure would you use to store it? How would you store the map itself? --------------Solutions------------- Without putting much thought into it; At the ba

  • Python data structure similar to dictionary where key is two values? 2012-01-23

    I am looking for a data structure in Python that is similar to a dictionary. The difference is that there is two keys. I want to be able to access the value in constant time. Like: dict.get(dog, smurf) {(dog, smurf): 40} Is this possible? If this doe

  • Data structure to use for platformer game map 2013-11-25

    I'm writing a 2D platformer game using Java for Android. Currently I have all game entities (except for the avatar, stored in an array of array of "Entity" Entity[][] Whenever I need to check something - such as what I'm going to draw on screen or fo

  • OSX API for accessing data structures similar to Quicktime atoms or MPEG boxes 2009-09-24

    Quicktime-, MPEG- or AIFF-files all seem to organize their data elements in chunks like this: 0x00 chunk 1 header (size as UInt32 + ID as 4-char-code) 0x08 chunk 1 data ... 0xA0 chunk 2 header 0xA8 chunk 2 data ... and so on. When reading a file like

  • Is there a data structure similar to std::set in TCL? 2012-01-07

    TCL has a data structure called dict which maintains a collection of key-value pairs. Is there another data structure which maintains a collection of keys (with no values)? If no, then maybe someone already wrote a simple adapter on dict with empty v

  • data structure to support google/bing maps 2010-01-22

    I was wondering what the data structure is in an application like google/bing maps. How is it that the results are returned so quickly when searching for directions? what kind of algorithms are being used to determine this information? thanks -------

  • Data structure to use in Sencha Touch similar to Vector in Blackberry 2011-10-19

    I am a beginner to sencha Touch, basically i am a blackberry developer. Currently we are migrating our application to support Sencha Touch 1.1. Now i have some business solutions like i want to store the selected values in the local database. I mean

  • Why do we use arrays instead of other data structures? 2008-12-25

    As I was programming, I haven't seen an instance where an array is better for storing information than another form thereof. I had indeed figured the added "features" in programming languages had improved upon this and by that replaced them. I see no

  • Generating data structures by parsing plain text files 2009-04-28

    I wrote a file parser for a game I'm writing to make it easy for myself to change various aspects of the game (things like the character/stage/collision data). For example, I might have a character class like this: class Character { public: int x, y;

  • Explaining persistent data structures in simple terms 2009-09-16

    I'm working on a library for Python that implements some persistent data structures (mainly as a learning exercise). However, I'm beginning to learn that explaining persistent data structures to people unfamiliar with them can be difficult. Can someo

  • Is there a data structure that holds sets of data in .NET? 2010-02-09

    I'm looking for a data structure similar to a dictionary that returns the set of all related items to a key. For example, I would use it like this: var data = new FancyDataStructure(); data.Add(new string[] {"Elizabeth", "Liz", "Betty"}); data.Add(ne

  • Data Structure Behind Amazon S3s Keys (Filtering Data Structure) 2010-03-12

    I'd like to implement a data structure similar to the lookup functionality of Amazon S3. For those of you who don't know what I'm taking about, Amazon S3 stores all files at the root, but allows you to look up groups of files by common prefixes in th

  • What data structure is most suitable for implementing a 2-D array in Java? 2009-03-26

    I want to implement a 2-D array kind of a thing. What data structure will be most suitable for this? An array or some other data-structure will do. If there is any other data structure which will satisfy my requirement, then please tell me. I don't w

  • What data structure to use / data persistence 2010-05-03

    I have an app where I need one table of information with the following fields: field 1 - int or char field 2 - string (max 10 char) field 3 - string (max 20 char) field 4 - float I need the program to filter on field 1 based upon a segmented control

  • Building a Generic Parser for Converting a Text File to a Data Structure in C# 2010-08-18

    I have a definition for a SPAN file (http://www.cme-ch.com/span/spanl300.htm) that i'd like to use in constructing a parser to parse the string data into an in memory collection class (or even using lazy evalution with the yield keyword.) All parsing

  • storing edges in a data structure 2011-04-16

    I have a class called Edge, which has attribute source id, target id and weight. I want to store this edge in a set data structure, so in the set there won't be duplicates of edges (i.e: edges with the same source and target id). The problem is this:

  • Data structure for expandable 3D array? 2012-02-25

    I'm looking for a data structure similar to T[,,] (a 3D array) except I don't know the dimensions beforehand (nor have a reasonable upper bound) that will expand outwards as time goes on. I'd like to use negative indexes as well. The only thing that

  • Two Way Mapping using single Data Structure 2009-05-13

    I ran across some code recently at work (recreated to be similar to what I am dealing with) similar to the code below Is there a way I can rework the code below to use one data structure (with performance in mind)? Here is some code to illustrate wha

Copyright (C) dskims.com, All Rights Reserved.

processed in 0.285 (s). 11 q(s)