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.

  • Index
  • » C++
  • » STL: how does set or map "insert" work?

#1 2006-08-17 10:50 AM

thinking
Member
Registered: 2005-09-15
Posts: 103

Re: STL: how does set or map "insert" work?

[email protected]

currently i'm a bit experimenting with the STL and i'm wondering how a map or a set insert's it's values
the question i have is:
Q1: how does a unique associative container know, if it should insert the element or not because it maybe already within the container?

i wrote the following example:

#include <map>
#include <set>
using namespace std;

class test{
   private:
      int value;
   public:

      test(int val){
          this->value = val;
      }

      ~test(){
      }

      int getValue() const{
          return this->value;
      }

      bool operator<(const test &s1) const
      {
       printf("Comparing %d with %d\n",this->getValue(),s1.getValue());
       return this->getValue() < s1.getValue();
      }
};

int main(int argc,char **argv){
/*    map <test,int> testmap;
    printf("\ncnt: %d\n\n",testmap.size());
    testmap[test(1)] = 0;
    printf("\ncnt: %d\n\n",testmap.size());
    testmap[test(3)] = 0;
    printf("\ncnt: %d\n\n",testmap.size());
    testmap[test(5)] = 0;
    printf("\ncnt: %d\n\n",testmap.size());
    testmap[test(3)] = 0;
    */
    set <test> testset;
    printf("\ncnt: %d\n\n",testset.size());
    testset.insert(test(1));
    printf("\ncnt: %d\n\n",testset.size());
    testset.insert(test(3));
    printf("\ncnt: %d\n\n",testset.size());
    testset.insert(test(5));
    printf("\ncnt: %d\n\n",testset.size());
    testset.insert(test(4));
    printf("\ncnt: %d\n\n",testset.size());
}

the output i get is:

cnt: 0


cnt: 1

Comparing 3 with 1
Comparing 1 with 3
Comparing 3 with 1

cnt: 2

Comparing 5 with 1
Comparing 5 with 3
Comparing 3 with 5
Comparing 5 with 3

cnt: 3

Comparing 4 with 3
Comparing 4 with 5
Comparing 3 with 4
Comparing 4 with 5

cnt: 4

if i change
    testset.insert(test(4));
to
    testset.insert(test(3)); // this value is already whithin the container

i get

cnt: 0


cnt: 1

Comparing 3 with 1
Comparing 1 with 3
Comparing 3 with 1

cnt: 2

Comparing 5 with 1
Comparing 5 with 3
Comparing 3 with 5
Comparing 5 with 3

cnt: 3

Comparing 3 with 3
Comparing 3 with 5
Comparing 3 with 3

cnt: 3

Q2: why are some values compared a second time?
for example: Comparing 3 with 3
Q3: at the last insert, why is the value 3 or 4 not compared with the value 1?

[email protected]

Offline

#2 2006-08-17 12:34 PM

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

Re: STL: how does set or map &quot;insert&quot; work?

Offline

#3 2006-08-17 02:59 PM

thinking
Member
Registered: 2005-09-15
Posts: 103

Re: STL: how does set or map &quot;insert&quot; work?

Offline

#4 2006-08-17 03:49 PM

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

Re: STL: how does set or map &quot;insert&quot; work?

I saw the starting /*, but missed the closing one and the set declaration. And forgot it was a < operator instead of a normal compare function. Oh well, all mysteries solved.

Offline

#5 2006-08-18 10:20 PM

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

Re: STL: how does set or map &quot;insert&quot; work?

Working ( backwards )...

Many of the structures in the STL actually use balanaced trees of some sort - with red / black trees seeming to be a preference - for the underlying structures...

One way to tell if WHAT the underside is in general terms is to look at the second parameter of definition ( which - if not supplied should default to using the internal < or == of the key class )... and if the comparator is using a lt comparison then its almost always a tree... e.g. with sets and maps...  on the other hand, if you see an eq comparator then it will be what you would consider a true 'hash' set up e.g. with hash_map ...

As for seeing all the comparisons... I would hazard to guess that the reason is you are dealing with an underlying balanced tree structure...  which means, once you decide what node the new object will be placed in... you then also need to do some checks to determine if everything underneath that node requires rebalancing... so it really is a two to three stage process of find location / if needs rebalance ( then rebalance )...

Finally... and I'm fairly certain you are NOT seeing this in your code but...  if you are using an STL impl optimized for very large data structures then that impl will probably do things such as limit recursion etc. depths... which means on traversal back 'up' the tree secondary checks are probably required to make certain you are where you want to be...

Michael


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

Salvador Dali (1904-1989)

Offline

#6 2008-08-18 02:45 AM

hkalilinks
Guest

Re: STL: how does set or map &quot;insert&quot; work?

I finally found something to the question,thanks

  • Index
  • » C++
  • » STL: how does set or map &quot;insert&quot; work?

Board footer

Powered by FluxBB