[shapir]

During an interview the interviewer claimed that STL vectors are actually implemented a black & red trees.
I don't think that this is the case, since STL vector elements are guaranteed to reside consecutively.
I find black & red trees appropriate for STL sets and maps.
While I do understand that the STL spec. does not specify any specific implementation, I would assume that:
1) vectors are implemented as arrays
2) lists implementation is still by means of lists (nodes and pointers)
3) maps, sets etc. are implemented as black & red trees

Yes I do understand that the implementation is not part of the standard (only the big O notation is).
Looking at the internet I could not find a definite answer.

The bottom line is that I did well in the interview, but would like to confirm the above 3 statements for the next interview

Thank you

Gil

This post has been edited by skyhawk133: 16 March 2011 - 02:40 PM

[KYA]

I don't think vectors are trees in any instance. i could be wrong though.

[janotte]

Here's my logic:
http://en.wikipedia....rary#Containers
vector = a dynamic array, like C array (i.e., capable of random access) with the ability to automatically resize itself when inserting or erasing an object. Inserting and removing an element to/from back of the vector at the end takes amortized constant time. Inserting and erasing at the beginning or in the middle is linear in time.

http://en.wikipedia..../Red-black_tree
However, the immediate result of an insertion or removal may violate the properties of a red-black tree. Restoring the red-black properties requires a small number (O(log n) or amortized O(1)) of color changes (which are very quick in practice) and no more than three tree rotations (two for insertion). Although insert and delete operations are complicated, their times remain O(log n).

The differences in bigO notation descriptions of how the two containers perform indicate to me that they are not the same structure.

Does that seem a compelling argument or am I simply showing my limits?

[EDIT]typo[/EDIT]

This post has been edited by janotte: 19 December 2008 - 05:51 PM

[shapir]

janotte, on 19 Dec, 2008 - 04:30 PM, said:

Here's my logic:
http://en.wikipedia....rary#Containers
vector = a dynamic array, like C array (i.e., capable of random access) with the ability to automatically resize itself when inserting or erasing an object. Inserting and removing an element to/from back of the vector at the end takes amortized constant time. Inserting and erasing at the beginning or in the middle is linear in time.

http://en.wikipedia..../Red-black_tree
However, the immediate result of an insertion or removal may violate the properties of a red-black tree. Restoring the red-black properties requires a small number (O(log n) or amortized O(1)) of color changes (which are very quick in practice) and no more than three tree rotations (two for insertion). Although insert and delete operations are complicated, their times remain O(log n).

The differences is bigO notation descriptions of how the two containers perform indicate to me that they are not the same structure.

Does that seem a compelling argument or am I simply showing my limits?

Yep. This is the way I understand the vector portion too. Thank you.

Gil

[skaoth]

It looks like you have some ground to stand on. You should go back and tell them that they are wrong.

One of the ways to know if a tree is being used vs. something else, is to know what type of guarantees the structure provides for common things like insert(), delete() find() etc. Anyways I did some digging in the stl code and found this. (Note using MSDN VC 9 headers)


Vector
-----------

		// TEMPLATE CLASS vector
template<class _Ty,
	class _Ax>
	class vector
		: public _Vector_val<_Ty, _Ax>
	{	// varying size array of values
public:
	typedef vector<_Ty, _Ax> _Myt;
	typedef _Vector_val<_Ty, _Ax> _Mybase;
	typedef typename _Mybase::_Alty _Alloc;
	typedef _Alloc allocator_type;
...


	pointer _Myfirst;	// pointer to beginning of array
	pointer _Mylast;	// pointer to current end of sequence
	pointer _Myend;	// pointer to end of array
	};

------------------

So yes it does look lie the vector is implemented as and array

Map
-------------

	// TEMPLATE CLASS map
template<class _Kty,
	class _Ty,
	class _Pr = less<_Kty>,
	class _Alloc = allocator<pair<const _Kty, _Ty> > >
	class map
		: public _Tree<_Tmap_traits<_Kty, _Ty, _Pr, _Alloc, false> >
	{	// ordered red-black tree of {key, mapped} values, unique keys
public:
	typedef map<_Kty, _Ty, _Pr, _Alloc> _Myt;
	typedef _Tree<_Tmap_traits<_Kty, _Ty, _Pr, _Alloc, false> > _Mybase;
	typedef _Kty key_type;
	typedef _Ty mapped_type;
	typedef _Ty referent_type;	// retained
	typedef _Pr key_compare;

...

-------------

The Map on the other hand looks like it uses a red-black tree

[shapir]

Thanks for your header digging Sqaoth!

I agree that the guarantees approach is a good one.

And last... Awaiting to sign a contract next Monday, I'll hold off with the "you are wrong" message

Gil

[perfectly.insane]

std::vector is usually implemented as a contiguous block of memory, very similar to a C style array. Resizing usually involves reallocating and copying the contents from one array to another, however, a vector usually reserves unused elements so that reallocation doesn't happen with every addition to the end of the array. The reserve() function call alone should be enough proof that vectors usually aren't implemented in terms of RB trees, as an RB tree implementation would not need such a function.

Usually, each reallocation is double the size of the previous allocation. So if you have a 16 element vector (and it's capacity is 16) and add a new element, it's internal size will likely grow to 32, even though only 17 elements would be used.

std::basic_string/std::string works in a very similar fashion.

In the STLport implementation of std::vector, std::vector<T>::iterator is a typedef to T*, so the iterators actually are pointers, as opposed to mimicking them.

std::map is often implemented in terms of a RB tree. Perhaps this is related to the confusion here...

This post has been edited by perfectly.insane: 22 December 2008 - 04:49 PM

[shapir]

Great! Exactly as I thought.

I believe that both STL Map and STL List are the RB tree guys, while vector is indeed contiguous and array like. Well, there might have been some confusion due to the dynamics of both parties during an interview... you know

The bottom line is the important one:
I've just signed a contract with these guys, so I'll be able to straighten this up directly with them

Thanks you all

Gil

[perfectly.insane]

I think your initial statements are basically on target:

shapir, on 19 Dec, 2008 - 07:02 PM, said:

1) vectors are implemented as arrays
2) lists implementation is still by means of lists (nodes and pointers)
3) maps, sets etc. are implemented as black & red trees

list is a doubly-linked list. I don't know much about set as I rarely use it, but I'd imagine that it's implemented as a binary search tree of some sort, just like map. I'd think that most are based on RB trees, but there is no inherent requirement to use them. An AVL tree could also be used. A plain binary search tree could also, though such would not be optimal (as well as lists and arrays...). The most precise prediction that I'd make is that they're probably all implemented as balanced trees (RB, AVL, etc.).

This post has been edited by perfectly.insane: 22 December 2008 - 06:14 PM