C / C++ / MFC

efficient sorting [was: STL iterator::operator+()]

7-Mar-02 9:49

The error is descriptive enough: You cannot shift a list iterators by adding some integer. Instead, you should do something like

temp_it=m_it_begin;
(for size_t n=0;n<subsize)temp_it++

But this is an indication of a flaw in your design. Please keep on reading.
Why list iterators cannot be added an integer? lists as implemented by STL¹ are not suitable for random access (that is, going to somewhere inside the list from a position index). As list nodes are typically connected to the previous and subsequent nodes by means of internal pointers, the only way to get to the n-th element is by transversing the entire list from the beginning. This is an expensive (in computational terms) operation and should be avoided whenever possible. Because of this, designers of STL decided to ban operator + on these iterators to remind the programmer about this issue. If you want random access, use vector instead. As so often in life, there's a tradeoff involved here: vectors are random access, but insertions in the middle of a vector are way more expensive than for lists.

¹ STL dos not mandate any particular implementation, but takes into account typical implementation tecnhiques as long as they affect the overall design of the components described.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

moredip7-Mar-02 9:54

moredip

7-Mar-02 9:54

Thanks for such a descriptive answer Smile | :)

Hmm, now i have to decide how I'm gonna improve the efficiency of my problem.

I've got a function which is generating double's. I eventually need to have these ordered. I initially just shoved them in an array, then qsort()ed it.

Then I tried sorting them as I inserted them into a list.

The two methods were pretty much equivelent in terms of speed.

Maybe I'll try hash-tables and buckets...

Can anyone a better way?

Re: efficient sorting [was: STL iterator::operator+()]

Joaquín M López Muñoz7-Mar-02 10:02

Re: efficient sorting [was: STL iterator::operator+()]

7-Mar-02 10:02

The structure of your data (pairs of key-value) might be an excellent candidate for std::map.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

moredip7-Mar-02 10:15

moredip

7-Mar-02 10:15

Looks like you're right.

I guess I'll use that rather than trying to reinvent the wheel. My wheel would probably be wobbly and fall off anyway Wink | ;)

Thanks,

Pete

Re: efficient sorting [was: STL iterator::operator+()]

Tomasz Sowinski7-Mar-02 23:52

Tomasz Sowinski

7-Mar-02 23:52

If, for some reason, you'll decide to stick with std::list, remember that there's std::list::sort method (which is different than generic std::sort from algorithm header).

Tomasz Sowinski -- http://www.shooltz.com

VC++ object layout

Joaquín M López Muñoz7-Mar-02 9:20

7-Mar-02 9:20

Does anyone have info on C++ object layout as implemented by VC++? Thanx.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

Serge Krynine7-Mar-02 11:32

Serge Krynine

7-Mar-02 11:32

Some info on this in Stanley Lipman's book "Inside C++ Object Model". For example, VC++ compiler inserts vptr at the first slot of an object, so *this dereferences it.

Joaquín M López Muñoz7-Mar-02 11:35

7-Mar-02 11:35

Thanx! Actually, I was looking for some info in the net I could consult for free. Anyway, maybe I can drop by some bookshop and take a look at that book.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

Serge Krynine7-Mar-02 11:57

Serge Krynine

7-Mar-02 11:57

I know what you mean, but I doubt that Microsoft would publish such information. Have a look trough the book (it is an excellent one), he compares different object model implementation done by Sun and Microsoft.

Tim Smith7-Mar-02 12:53

Tim Smith

7-Mar-02 12:53

Hmm, here is a quick run down...

Like a structure, data inside a class is placed inside the class in the order it is defined using the current alignment. (99% sure...)

The virtual table is in the order that virtual functions are defined. (I think...)

The virtual table is a simple pointer to a table at the beginning of the class.

If a class is derived from another class, then any virtual functions defined in the derived class are added at the end of the vtable (I think, that is most logical). Overridden methods just replace the proper entry in the vtable.

All objects of the same class share the same vtable. However, a base class of a derived class might not share the same vtable as an instance of the base class when it is created directly (i.e. not derived).

HERE IS WHERE IT GET HAIRY...

When class is derived from 2 or more classes that contain virtual tables, then there actually exists multiple virtual tables in the object. Let us take an example where class C is derived from A and B in that order. At the head of object C is the vtable for all the virtual methods in A, B and C. At the start of B you have the vtable for B (which might contain overridden methods in C.)

Now the fun begins with the required thunking of the this pointer.

First, let us consider the case where the program has a pointer to object C and wants to invoke a method in B that isn't overridden by C. The calling routine would access the vtable at the start of C (which is the combo A, B and C vtable) and invoke that routine using C as the address. However, since the routine has NOT been overridden, the method in B would be receiving a pointer to C while expecting a pointer to B. So instead of having a pointer to the method in B in the combo vtable, you actually have a pointer to a thunk routine that adjusts the this pointer from C to B and then invokes the real routine.

In the opposite case, you have an object C which a program is referencing via a pointer to B. The program wishes to invoke a method in B which has been overridden by C. When the method is invoked, the vtables at the start of the B object inside of C is accessed (since all you have is a pointer to B, you are required to access its vtable). The method address retrieved from the vtable is actually the pointer to the overridden method in C. But, like in the previous case if we passed this, which is pointing to B to the routine expecting a pointer to C, the program would fail. Thus once again the vtable points to a thunk that adjusts the this pointer and then invokes the proper routine.

Smile | :)

(I hope I got most of this right...)

Tim Smith

I know what you're thinking punk, you're thinking did he spell check this document? Well, to tell you the truth I kinda forgot myself in all this excitement. But being this here's CodeProject, the most powerful forums in the world and would blow your head clean off, you've got to ask yourself one question, Do I feel lucky? Well do ya punk?

Serge Krynine7-Mar-02 12:56

Serge Krynine

7-Mar-02 12:56

The virtual table is in the order that virtual functions are defined. (I think...)

where the slot 0 contains run-time type class id, slot 1 contains pointer to the first virtual function, slot 2 contains pointer to the second virtual function etc.

Tim Smith7-Mar-02 14:57

Tim Smith

7-Mar-02 14:57

If that option is enabled. I don't ever use it.

Tim Smith

I know what you're thinking punk, you're thinking did he spell check this document? Well, to tell you the truth I kinda forgot myself in all this excitement. But being this here's CodeProject, the most powerful forums in the world and would blow your head clean off, you've got to ask yourself one question, Do I feel lucky? Well do ya punk?

Nemanja Trifunovic7-Mar-02 13:01

Nemanja Trifunovic

7-Mar-02 13:01

Maybe you are looking for this article

I vote pro drink Beer | [beer]

pba_7-Mar-02 17:00

pba_

7-Mar-02 17:00

The binary layout of a C++ object is a structure which keeps the attributes ( in the order of definition ) and if the class inherits from some other classes the structure is prefixed with the parent vptr table and data ( in the order of definition). So, for a simple hierarchy like "class child : public parent " the layout will be:
parent::vptr_table
parent::data
child::data
and if we have a more complex hierarchy like :
class base;
class parent1 : public virtual base;
class parent2 : public virtual base;
class child : public parent1, public parent2
the layout will be:
base::vptr_table
base::data
parent1::vptr_table
parent1:data
parent2:vptr_table
parent2::data
child::data
Let’s say you have a class named CObject and you create an instance called x . Since the calling convention of a member function is the "this" convention , the compiler will just copy into the ECX register the "this" value for x object , will push the parameters on the stack and will call the method :
Lea ecx, x
Push ..
Call CObject::method
If you will define another instance of CObject called y the method call will be :
Lea ecx, y
Push ..
Call CObject::method
If you want to access the attributes just point to the class location and get the variable by offset, and to call method functions thru vptr table all you have to do is pointer arithmetic . If you have time you can check this sample :

#include <stdio.h>

class CBase1
{
public:
virtual void b1_test1() = 0;
virtual void b1_test2() = 0;
};

class CBase2
{
public:
virtual void b2_test1() = 0;
virtual void b2_test2()
{
};
virtual void b2_test3()
{
};
};

class CTest : public CBase1, public CBase2
{
public:
void b1_test1();
void b1_test2();
void b2_test1();
void b2_test3();
void b2_test2()
{
printf("b2_test2\n");
};
};

void CTest::b1_test1()
{
printf("b1_test1\n");
};

void CTest::b1_test2()
{
printf("b1_test2\n");
};

void CTest::b2_test1()
{
printf("b2_test1\n");
};

void CTest::b2_test3()
{
printf("b2_test3\n");
};

void test_vptr()
{
CTest x;

//call CBase1::b1_test1
_asm
{
lea ecx, x
mov eax, dword ptr[ ecx] //get CBase1 vptr
call dword ptr[ eax + 0] //first method from table
}

//call CBase2::b2_test3
_asm
{
lea ecx, x
mov eax, dword ptr[ ecx + 4] //get CBase2 vptr - second base class
call dword ptr[ eax + 8] //third method from table
}

//call CBase2::b2_test2
_asm
{
lea ecx, x
mov eax, dword ptr[ ecx + 4] //get CBase2 vptr
call dword ptr[ eax + 4] //second method from table
}
};

class CSimple
{
private:
int k;
int f;
public:
CSimple(int v)
{
k = v;
f = 3;
}
void test();
};

void CSimple::test()
{
printf("simple::test\n");
};

void test_simple()
{
CSimple x(1);
CSimple y(2);
int t = 0;

//printf x.k
_asm
{
mov eax, dword ptr[ x]
mov t, eax
}
printf("x::k : %d\n", t);

//printf x.f
_asm
{
mov eax, dword ptr[ x + 4]
mov t, eax
}
printf("x::f : %d\n", t);

//printf y.k
_asm
{
mov eax, dword ptr[ y]
mov t, eax
}
printf("y::k : %d\n", t);

}
void main(void)
{
test_vptr();
test_simple();
}

Thank you all

Joaquín M López Muñoz7-Mar-02 19:51

7-Mar-02 19:51

Thanxs to everybody for this bunch of replies. I'm going to have a fun time digesting them Smile | :)

Regards

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

Re: Thank you all

Tim Smith8-Mar-02 2:02

Tim Smith

8-Mar-02 2:02

I hope it didn't make you ill Smile | :)

Tim Smith

I know what you're thinking punk, you're thinking did he spell check this document? Well, to tell you the truth I kinda forgot myself in all this excitement. But being this here's CodeProject, the most powerful forums in the world and would blow your head clean off, you've got to ask yourself one question, Do I feel lucky? Well do ya punk?

Array of objects?

clintsinger7-Mar-02 8:40

clintsinger

7-Mar-02 8:40

Is it possible to create an array of objects or an array of pointers to objects. I think the later is what I am really after.

I have tried doing such a beast and all I get is an error.

class Bar
{
  Bar(CString strName, CString strAddress)
}

class Foo
{
protected:
  Bar* m_poBars[16];

public:
  Foo();
  Create(INT nIndex);
}

////////// Implementation

Foo::Foo()
{
  for (INT i; i < 16; i++)
  {
    m_poBars[i] = NULL; // This is not liked at all
  }
}

// Then I would like to initialize an arbitrary location with the Bar class

Foo::Create(INT nIndex)
{
  m_poBars[nIndex] = new Bar("My Place", "123 Road");
}

The above code doesn't seem to be too happy Dead | X|

and I was wondering what I am doing wrong.

Cheers,
Clint Singer

Joaquín M López Muñoz7-Mar-02 8:51

7-Mar-02 8:51

I think everything is perfect except the following line:

for (INT i; i < 16; i++)

You forgot to initialize i:

for (INT i=0; i < 16; i++)

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

clintsinger7-Mar-02 10:25

clintsinger

7-Mar-02 10:25

I can't believe it. The INT i... Well it was the problem. I made the mistake in my posting and in my code. What is worse, the posting was totally made up to simplify the problem. I don't know how many times I looked at my real code and didn't notice that I wasn't initalizing i to Zero. Boy, I feel silly Laugh | :laugh:

Cheers,
Clint Singer

Joaquín M López Muñoz7-Mar-02 10:59

7-Mar-02 10:59

Didn't you get a warning? The compiled should have issued one on this.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo

HomeNuke7-Mar-02 8:55

HomeNuke

7-Mar-02 8:55

Like Joaquin said it looks good except for the initialazation part of 'i'. However, if that does not resolve your problem what is the specific error message you are getting? That would help diagnose the problem.

PLUS are you sure that is where the error is generated? Your example class BAR is defined such as:

class Bar
{ 
	Bar(int strName, int strAddress);
};

The problem with this is that Bar is now a private Constructor by default. You would have problems initializing this in your main function when it calls FOO create unless this is declared as a friend of the class, but that wasn't appearent in your example. Plus you may want to add to the end of your constructor { } so it would be an inline function or define it somewhere else or you may get a linker error.

Hope this helps out...I don't even know what I'm talking about right now...need more coffee Hmmm | :|

HomeNuke
----
"Nuke'd Your Home, Yet?"
Run your own PostNuke based web server from home
http://www.homenuke.com

clintsinger7-Mar-02 9:46

clintsinger

7-Mar-02 9:46

Some mistakes on my part. The Bar() constructor is infact public: and INT i is indeed INT i = 0; They are just wrong on my posting, sorry. I am still getting the error. To add more to the story I am making a simple ActiveX control and running it in visual basic. The errors I get are as such when I try to do m_poBars[i] = NULL;

First-chance exception in VB6.EXE (DVMS CLIENT LIB.DLL): 0xC0000005: Access Violation.
First-chance exception in VB6.EXE (KERNEL32.DLL): 0x80010105: (no name).

HomeNuke7-Mar-02 9:48

HomeNuke

7-Mar-02 9:48

So the error you are getting is from the client side? Oh OK I'm thinking from a straight C++ side application Smile | :)

Let me review this some more...sorry for not understanding the question in the first place.

HomeNuke
----
"Nuke'd Your Home, Yet?"
Run your own PostNuke based web server from home
http://www.homenuke.com

Joaquín M López Muñoz7-Mar-02 9:53