UNIX Socket FAQ

A forum for questions and answers about network programming on Linux and all other Unix-like systems

You are not logged in.

#1 2006-05-31 02:16 PM

Lloyd
Member
Registered: 2006-02-13
Posts: 53

Re: STL for Tree

How can I make use of the tree available with C++? I don't know where it resides, please help me.

Can you suggest me any other data structure than linked list (like tree) to access the data elements fastly. My problem is I have multiple key fields. In a tree we arrange the elements based on a field's value. But in my case it is four fields. (I think, here I can't use a tree) so which is the efficient data structure available for me?

Offline

#2 2006-06-01 04:45 AM

Uzume
Administrator
Registered: 2002-08-30
Posts: 186

Re: STL for Tree

I am not entirely sure I understand but I might suggest a hash table.

Offline

#3 2006-07-05 07:24 PM

mlampkin
Administrator
From: Sol 3
Registered: 2002-06-12
Posts: 911
Website

Re: STL for Tree

That many STL impls actually are implementing the set(s) and map(s) as trees... 

Its only ( on some systems / compilers ) e.g. Microsoft when you declare a hash_ set or map that it actually uses what one typically thinks of as a hash table type style...


Michael


"The only difference between me and a madman is that I'm not mad."

Salvador Dali (1904-1989)

Offline

#4 2009-05-22 08:34 AM

yurec
Member
From: Singapore
Registered: 2006-11-16
Posts: 134

Re: STL for Tree

"In a tree we arrange the elements based on a field's value" - that is std::set.
"But in my case it is four fields" - I think you should take a look at boost::multi-index.

Regards,
Yurij

Offline

#5 2009-05-22 04:46 PM

jfriesne
Administrator
From: California
Registered: 2005-07-06
Posts: 348
Website

Re: STL for Tree

Offline

#6 2009-05-22 09:52 PM

i3839
Oddministrator
From: Amsterdam
Registered: 2003-06-07
Posts: 2,239

Re: STL for Tree

Guys, you are resurrecting a three years old thread.

(Probably because of the stupid spam bot that bumped it up.)

Offline

#7 2009-05-22 11:58 PM

jfriesne
Administrator
From: California
Registered: 2005-07-06
Posts: 348
Website

Re: STL for Tree

Offline

#8 2009-06-03 05:29 AM

mlampkin
Administrator
From: Sol 3
Registered: 2002-06-12
Posts: 911
Website

Re: STL for Tree

Um...

What eludes me about the resurrection is that a set / etc. from the STL allows a comparator to be specified... which could then be written to do the appropriate comparisons against 1 or more elements contained in the type / object to be stored...

The thing is that I am not anti-Boost but... I don't understand the rationale of adding an external library to duplicate functionality already included with the standard libraries... other than maybe save the programmer from typing two or three extra lines of code... ?!


Michael


"The only difference between me and a madman is that I'm not mad."

Salvador Dali (1904-1989)

Offline

#9 2009-06-03 08:49 AM

yurec
Member
From: Singapore
Registered: 2006-11-16
Posts: 134

Re: STL for Tree

#include <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <string>

 struct Customer {
   Customer(const std::string & i_ssn, const std::string & i_name)
   :  m_ssn(i_ssn), m_name(i_name)
   {
   
   }
   
   std::string m_ssn;
   std::string m_name;
   };
   
 struct SSN { };
 struct Name { };
 
 typedef boost::multi_index_container<
   Customer,
   boost::multi_index::indexed_by<
   boost::multi_index::ordered_unique<
   boost::multi_index::tag<SSN>,
   boost::multi_index::member<Customer, std::string, &Customer::m_ssn>
   >,
   boost::multi_index::ordered_non_unique<
   boost::multi_index::tag<Name>,
   boost::multi_index::member<Customer, std::string, &Customer::m_name>
   >
   >
   >
   MyCustomerDB;

int main() 
{
 typedef MyCustomerDB::index<SSN>::type SSNIndex;
 typedef MyCustomerDB::index<Name>::type NameIndex;
 typedef SSNIndex::iterator SSNIterator;
 typedef NameIndex::iterator NameIterator;
 
 MyCustomerDB db;
 SSNIndex& ssnIndex = db.get<SSN>();
 NameIndex& nameIndex = db.get<Name>();
 
 Customer c1("333-44-5555", "John Smith");
 Customer c2("666-77-8888", "Robert Brown");
 
 db.insert(c1);
 db.insert(c2);
 
 SSNIterator ssnIter = ssnIndex.find("333-44-5555");
 c1.m_ssn = "999-00-1111";
 ssnIndex.replace(ssnIter, c1);

return 0;
}

Offline

#10 2009-06-05 03:21 PM

mlampkin
Administrator
From: Sol 3
Registered: 2002-06-12
Posts: 911
Website

Re: STL for Tree

Um... yurec...

I have to ask whats up with the "Dear Mr Lampkin" routine... are you writing a response to my post or a love letter ?! 

:lol::P

Anyway... let me clarify... the user seemed to be saying they wanted a collection keyed on multiple fields within a single object... in which case I think a regular stl style set / similar would work fine ( and part(s) of the stored value can be specified as the key segment )... e.g. I don't think the following is complex at all:

// Some definition of class Foo here to be stored...
struct ltFoo
{
  bool operator()(const Foo f1, const Foo f2) const
  {
    // Compare f1.key field 1 to f2.key field 1 and
    // if equal compare f1.key field 2 to f2.key field 2
    // and if equal compare etc.

    return true | false;
  }
};
int main()
{
    set<Foo, ltFoo> Bar;

    // ... add some Foo

    // Just set the appropriate fields of the finderFoo where is a temp
    // obj or persisted per thread ( or similar ) if desired to be thread-safe
 
    Bar.find( finderFoo ); // returns an iterator to the matching obj

}

On the other hand...

If the user who posted the question several centuries ago wanted to not just key on multiple fields within an object... but also to key on specified and differing fields during find operations a la database style indexing operations... then maybe something like the suggested boost container would be appropriate...

But again... if you re-read the post - thats not what he / she said they wanted to do... and unfortunately... at this late date its a bit hard to get clarification... lol


Michael


"The only difference between me and a madman is that I'm not mad."

Salvador Dali (1904-1989)

Offline

#11 2009-06-05 09:27 PM

yurec
Member
From: Singapore
Registered: 2006-11-16
Posts: 134

Re: STL for Tree

Hi,

The task was to access elements of a container fast using multiple keys.
But you are right, only the user who posted the question can make it clear.

Regards,
Yurij

Offline

#12 2009-06-11 09:27 PM

Nope
Administrator
From: Germany
Registered: 2004-01-24
Posts: 385
Website

Re: STL for Tree

- yawns -

Boost, no Boost. That'll be no longer really relevant once the next specification is out. Because, basically the whole Boost Libs will be then part of the STL.

Allthough, at least I won't be effected by that. I use neither STL nor Boost. Both usually are much too slow for my taste.

Offline

#13 2009-06-11 10:01 PM

jfriesne
Administrator
From: California
Registered: 2005-07-06
Posts: 348
Website

Re: STL for Tree

Offline

#14 2009-06-12 07:46 AM

yurec
Member
From: Singapore
Registered: 2006-11-16
Posts: 134

Re: STL for Tree

Anyhow you shoud need some kind of structures, algorithms, smart ptrs (threre are much more staff like this in stl and boost). You say that it's not efficient enough. But i'm sure you make your own analogous reusable code for this kind of things. And If it's not just bla-bla about your mega efficient code, i think boost committee (and milions of other developers) will appreciate your great code!
Don't be so greedy to share it!
Waiting for a new library by mr.Nope ;-)

Best regards,
Yurij

Offline

#15 2009-06-12 09:04 PM

Nope
Administrator
From: Germany
Registered: 2004-01-24
Posts: 385
Website

Re: STL for Tree

rofl.

Too slow at run time and usually not that much faster to develop to accept the lost speed later. Besides, they also waste memory. And, especially if you think about the energy problem in the data centers, faster code means less needed energy, creating less heat and running costs.

No, sorry. No libs from me. You see, what makes self written code faster than general purpose libs, is the fact that the general purpose procedures/classes/functions carry a lot around you you just don't need in most cases. Even worse, often you still have to write additional code to get from them what you really need.

Take the tree example. A simple tree might be enough for a small amount of highly dynamic data. But once you enter the realm of huge data sets, you need a more complex tree design. For example one that balances itself, or not a binary tree but one that uses lists for nodes that share the same sorting key. There are so many kinds of trees, each with it's distinct strong and weak points.
Or another favourite of mine: databases. Surely is a db like MySQL or Oracle a mighty tool. But it's usually overkill, resource hungry and it is outside the application, making it mandatory to waste resources for the communication. I am working with search engines these days, and guess what, they all share one thing... they've all got their own DB engines highly specialised for search speed, because those general purpose ones are just way too slow.

I've written a lot code in the past 28 years and I've read a lot books too. So in most cases I can just throw things together for the needs I have. Often I can borrow parts of code from old projects, sometimes I have even something there just right for the new problem. I can't use that in the job though, there I have to write "code" in Perl, Python, C# and the like. But then, there it's useless to optimize too much anyway.

Offline

#16 2009-06-13 01:35 PM

yurec
Member
From: Singapore
Registered: 2006-11-16
Posts: 134

Re: STL for Tree

Sorrry, i was a bit sarcastic.
For sure there is much sense in your words.
I would say that the libs we are discussing (stl and boost are perfect in 95% ). And you are those 5%.
But for other 95% they are must know and must use.

And i probably  don't have as much experience as you. So that is only my point of view.

Yurij

Offline

#17 2009-06-13 06:09 PM

RobSeace
Administrator
From: Boston, MA
Registered: 2002-06-12
Posts: 3,847
Website

Re: STL for Tree

You just have to think about what your code is going to be doing...  If I'm writing an
end-user GUI app, I don't care as much about super-efficiency, so using a general
purpose solution will be fine as far as speed goes, and easier to code...  But, if I'm
writing a back-end server app of some kind, then I'm likely to care a lot more
about efficiency, and would have no qualms about rolling my own custom solution in
place of a general purpose solution, if I knew it'd be more efficient for my own
specific uses...

Of course, I write pretty much everything in straight C, so I'd never use STL or boost
for anything, anyway... ;-)  Damn OOP wussies... ;-)

Offline

#18 2009-06-14 03:14 PM

Nope
Administrator
From: Germany
Registered: 2004-01-24
Posts: 385
Website

Re: STL for Tree

Yeah, that's it. Server apps are things where I write complete own and optimized code. But also normal apps that need a lot cpu will get at least the power hungry part highly optimized.

For all other things STL might be ok. But I often do compare programming with composing music. And STL is like using pre-recorded sound snippets. To get the flow right you have to bend your code/music to match the needs of those. You'll inevitably get something that doesn't sound right and it isn't really your music either.
So yurec, if you use STL and Boost to finish work to earn money or a good grad, it's really ok. But honestly, if you do write something for yourself that you don't need asap, then go the way to write the one or other thing by yourself. You'll learn a lot and it's the only way to get experience and a better understanding of data structures and how to organize/process/manipulate them in a meaningfull way.
If you are content with a limited understanding and think you won't need or appreciate any thing any deeper, then you could also start using things like the curl lib and forget so low level tasks like socket programming. After all, there's almost for all a lib out there in the web.

:P och Rob. OOP, as well as the whole rest of OOAD isn't as bad as you might think. It actually makes team work and maintenance so much easier if done right. Just give it a try :P

Offline

#19 2009-06-14 06:10 PM

RobSeace
Administrator
From: Boston, MA
Registered: 2002-06-12
Posts: 3,847
Website

Re: STL for Tree

Offline

#20 2009-06-16 02:40 AM

jfriesne
Administrator
From: California
Registered: 2005-07-06
Posts: 348
Website

Re: STL for Tree

Offline

#21 2009-06-16 01:42 PM

RobSeace
Administrator
From: Boston, MA
Registered: 2002-06-12
Posts: 3,847
Website

Re: STL for Tree

Offline

#22 2009-06-16 07:41 PM

jfriesne
Administrator
From: California
Registered: 2005-07-06
Posts: 348
Website

Re: STL for Tree

Offline

#23 2009-06-16 08:54 PM

RobSeace
Administrator
From: Boston, MA
Registered: 2002-06-12
Posts: 3,847
Website

Re: STL for Tree

Offline

#24 2009-06-16 09:57 PM

jfriesne
Administrator
From: California
Registered: 2005-07-06
Posts: 348
Website

Re: STL for Tree

// This code may, or may not, contain a bug!
   int s = socket(AF_INET, SOCK_DGRAM, 0);
   if (s >= 0)
   {
      DoSomething(s);
      close(s);
   }

Offline

#25 2009-06-16 11:18 PM

RobSeace
Administrator
From: Boston, MA
Registered: 2002-06-12
Posts: 3,847
Website

Re: STL for Tree

typedef struct sock_ref_struct {
    int sock, cnt;
} sock_ref;

sock_ref *sock_ref_open (int family, int type, int protocol)
{
    sock_ref *ref = malloc (sizeof (sock_ref));
    if (!ref) return (NULL);
    ref->sock = socket (family, type, protocol);
    if (ref->sock < 0) { free (ref); return (NULL); }
    ref->cnt = 1;
    return (ref);
}

sock_ref *sock_ref_copy (sock_ref *ref)
{
    if (!ref) { errno = EINVAL; return (NULL); }
    if (ref->cnt < 1) { errno = EINVAL; return (NULL); }
    ref->cnt++;
    return (ref);
}

int sock_ref_close (sock_ref *ref)
{
    if (!ref) { errno = EINVAL; return (-1); }
    if (ref->cnt < 1) { errno = EINVAL; return (-1); }
    ref->cnt--;
    if (ref->cnt == 0) { close (ref->sock); free (ref); }
    return (ref->cnt);
}

...

sock_ref *mysock = sock_ref_open (AF_INET, SOCK_DGRAM, 0);
if (mysock) DoSomething (mysock);
sock_ref_close (mysock);

Offline

Board footer

Powered by FluxBB