2

This is my work but not home work. I am trying to come up decide how best to represent a data I have using a native data structure(By native i mean I cannot use STL in C++, its a C++ code. Its our design decision not to use STL and have no way to change it or violate it)

Data is as follows:

There is a variable say int to denote ipaddr say e.g. 192.168.10.77(lets say this is stored in a int which is uniquely obtained from the 192.168.10.77 ) which lets call deviceId.

Now for each such deviceId there are other fields multiple services associated to it say service 1, service2, etc... Number of services associated with each device is variable from one deviceId to another.

So a sample of data could look like:

192.168.10.77 

    service1

    service2

    service3

    service4

192.168.10.98

    service1

    service2

192.168.10.97

    service1

Right now I store it in a inefficient data structure as below.

I have a struct as:

typedef struct
{
   deviceId d;
   serviceId s;
}mystr;

And then I use an array of a struct which holds 

mystr mylist[64];

so entries of this array look like

mylist[0].d = 192.168.10.77

mylist[0].s = service1


mylist[1].d = 192.168.10.77

mylist[1].s = service2

mylist[2].d = 192.168.10.77

mylist[2].s = service3

mylist[3].d = 192.168.10.77

mylist[3].s = service4

mylist[4].d = 192.168.10.98

mylist[4].s = service1

mylist[5].d = 192.168.10.98

mylist[5].s = service2

... ... and so on ....

Essentially the deviceId value is duplicated as many times as there are services associated to it.

I need some thing more efficient because later I have to group all the services associated with a device.

So to do that I might have to search for deviceId and club the services for it together. I don't know how I am going to search by deviceId as it can have any value.

What is a better way to represent this data using some optimal data structure ?

[ I can see it as linked list but could not come up with the struct Node{ } for it ]

goldenmean
  • 18,376
  • 54
  • 154
  • 211
  • [The STL is dead.](http://stackoverflow.com/q/5205491/166749) It's subsumed by the standard library now. So your data structures are far from native -- they're custom. – Fred Foo Feb 25 '13 at 16:18
  • 3
    a map of ip to a list of names might work best for you. `std::map >` – andre Feb 25 '13 at 16:20
  • @larsman - I know. So lets say I cannot use containers from the std lib for C++ as this runs on two different targets - ARM, x86 and is compiled using 3 compilers(2 different ones for linux-Arm and 1 for windows-x86). We had found some slight differences in code and behaviour on these variants. – goldenmean Feb 25 '13 at 16:21
  • 3
    typedef struct {...} mystr; c++ code for real. – Slava Feb 25 '13 at 16:21
  • @Slava Who said one can't use typdefine for structs in C++ – goldenmean Feb 25 '13 at 16:23
  • 1
    @goldenmean: so? MSVC, GNU and Intel all support the standard library and the containers don't need any runtime support (you can even give them custom allocators). I don't see a reason to reinvent the wheel. If you must, then first using standard data structures and then replacing them one by one might work. – Fred Foo Feb 25 '13 at 16:23
  • @goldenmean: `struct mystr{ ... };`. No `typedef` necessary. – Zeta Feb 25 '13 at 16:24
  • 1
    @goldenmean you can compile C code by C++ compiler in most cases. That does not make that C++ code. – Slava Feb 25 '13 at 16:26
  • @Slava - I know but u you havent seen the actualcode I have whether its C or C++ and also its besides the point – goldenmean Feb 25 '13 at 16:29
  • I already see C-code, typedef struct - pure C code. There is nothing wrong with writing C code, just do not confuse people. – Slava Feb 25 '13 at 16:31
  • @Slava - If you have downvoted, please care to explain, would you? Pls. don't be dogmatic. you can always go to another question by leaving this alone. – goldenmean Feb 25 '13 at 16:37
  • Tag it properly, C not C++ – Slava Feb 25 '13 at 16:38
  • There is a reason why `typedef struct` is used in C. If you don't use it you have to have `struct` in front of your struct names everywhere. Reducing syntax is one on the reasons for using `typedef` in C. So, unless you need to maintain backward compatibility with C, your just adding extra syntax. It doesn't hurt but it's not popular. – andre Feb 25 '13 at 16:38
  • 1
    I know the reason, but no, you are not just adding extra syntax. Try to forward declare that struct. Believe me that hurts. – Slava Feb 25 '13 at 16:41

4 Answers4

2

typedef struct
{ deviceId d;
serviceId s[100]; more than 1 service for 1 device is required

 `}mystr;  

mystr mylist[64];`

or you can have a linked list like

` struct device {
device id; *service; }

 typedef struct serviceid{
 {
   *service;
 }service;

` point to null by last service id

Pannan Mp
  • 77
  • 10
  • 1
    your solution is every bit as inefficient as OP's, have not idea why would anyone upvote it –  Feb 25 '13 at 16:50
  • @aleguna - it looks like [sock puppts](http://meta.stackexchange.com/questions/60515/how-did-stack-overflow-come-to-know-about-dummy-upvotes) were involved in that – LittleBobbyTables - Au Revoir Feb 25 '13 at 19:58
0

Consider using gethostbyname and gethostbyaddr. First try one, if it fails, try the other. Then you only have to store one string.

john.pavan
  • 910
  • 4
  • 6
0

How about this library to store it as a basic hash table?

http://troydhanson.github.com/uthash/

Disclaimer: I'm only vaguely familiar with C

Matt Browne
  • 12,169
  • 4
  • 59
  • 75
0

You can have link list of devices with link list of services

typedef Service{
 serviceId s;//store service id
 Service *nextService;//link to the different services supported by the device, end by null
}*deviceServiceList;

typedef struct Device{
 deviceId d;//store the device id
 Service *s;//store the list of service available for this device
}myDevices;

the devices can be stored in a array of devices or u can create a link list of devices

rohitmb
  • 151
  • 1
  • 3
  • 13