C / C++ / MFC

7-Mar-02 9:33

Hi all,

Anyone want to give me some tips on the STL iterator?

I'm trying to implement a binary search on a list. here's a little snippet of code:

typedef struct _key_data{
	KEY k;
	DATA d;
} key_data;

typedef list<key_data>::iterator KLiterator;

KLiterator m_it_begin;

...
...
...

CKeyList::Search( KEY key )
{
        KLiterator temp_it;
	int sub_size;
...
...
...
	temp_it = m_it_begin + sub_size;         //   <-This here is the problem :C
...
...
...

the problem is with my iterator's + operator. When i try and compile I get this error msg:

error C2678: binary '+' : no operator defined which takes a left-hand operand of type 'class std::list<struct CKeyList<double,unsigned int>::_key_data,class std::allocator<struct CKeyList<double,unsigned int>::_k
ey_data> >::iterator' (or there is no acceptable conversion)

now I expect this will turn out to be a really dumb mistake, but I can't figure out why it's not working Frown | :(

Can anyone spot what's wrong?

TIA,

pete

Christian Graus7-Mar-02 9:41

Christian Graus

7-Mar-02 9:41

You're using list. A binary search on list is going to be VERY expensive, as list has only bi-directional iterators. They define operator ++, but not operator +, because you need to step through the elements one at a time, you can't do an arbitrary jump. You need random access iterators for that ( as in vector ).

For the most efficient search on list, use the member function provided.

Christian

The tragedy of cyberspace - that so much can travel so far, and yet mean so little.

"I'm thinking of getting married for companionship and so I have someone to cook and clean." - Martin Marvinski, 6/3/2002

moredip7-Mar-02 9:48

7-Mar-02 9:48

Doh!

Random access on a linked list? What was I thinking? Blush | :O

Thanks for pointing that one out.

Christian Graus wrote:
For the most efficient search on list, use the member function provided

do you mean list::sort()? I couldn't find a search function in my documentation.

Does anyone have a clue on how efficient the sort algorithm is. I'm guessing it'll be slower than a qsort() on an array, right?

Pete

Nemanja Trifunovic7-Mar-02 9:58

Nemanja Trifunovic

7-Mar-02 9:58

I made the same mistake not so long ago... Smile | :)

I vote pro drink Beer | [beer]

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

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

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

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?

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

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

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

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