Python and STL efficiency

[Marc 'BlackJack' Rintsch]

In <1156143136.020647.294290 at i42g2000cwa.googlegroups.com>, Licheng Fang
wrote:

> Hi, I'm learning STL and I wrote some simple code to compare the
> efficiency of python and STL.
> 
> //C++
> #include <iostream>
> #include <string>
> #include <vector>
> #include <set>
> #include <algorithm>
> using namespace std;
> 
> int main(){
> 	vector<string> a;
> 	for (long int i=0; i<10000 ; ++i){
> 		a.push_back("What do you know?");
> 		a.push_back("so long...");
> 		a.push_back("chicken crosses road");
> 		a.push_back("fool");
> 	}
> 	set<string> b(a.begin(), a.end());
> 	unique_copy(b.begin(), b.end(), ostream_iterator<string>(cout, "\n"));
> }

Why are you using `unique_copy` here?

> #python
> def f():
> 	a = []
> 	for i in range(10000):
> 		a.append('What do you know')
> 		a.append('so long...')
> 		a.append('chicken crosses road')
> 		a.append('fool')
> 	b = set(a)
> 	for s in b:
> 		print s
> 
> I was using VC++.net and IDLE, respectively. I had expected C++ to be
> way faster. However, while the python code gave the result almost
> instantly, the C++ code took several seconds to run! Can somebody
> explain this to me? Or is there something wrong with my code?

There's a difference in data structures at least.  The Python `set` type
is implemented with a hash algorithm, so the equivalent STL type would be
`hash_set`.  `set` in Python does not store its contents sorted.

Ciao,
	Marc 'BlackJack' Rintsch