[c++] stl 맵의 사이즈가 아주 클때.

맵에 있는 내용을 출력하는데, 맵의 싸이즈가 아주 크다면 갑자기 출력속도가 저하되거나 그러나요?
도무지 이해할 수가 없어서.

typedef multimap<long, Index *> mmap_IndexMap;
mmap_IndexMap IndexMap;

i_IndexMap i_index = IndexMap.begin();
Index * new_index;

while(i_index != IndexMap.end()){

		new_index = i_index->second;

		fs_inversedIndex << " " << new_index->id << " " << new_index->doc_id << " " << new_index->term_freq << "\n";
		++i_index;
	}

Index는 클래스이고, fs_inversedIndex는 파일스트림입니다.
맵에 741560개 정도의 원소가 들어있을때 위와 같은 출력시간은 1초도 안걸리는데, 3166565개를 출력해야 하는데 시간이 장난이 아닙니다. 아직 끝을 보지 못했을 정도입니다. 몇시간이고 돌거 같더군요. 맵의 사이즈가 어느정도 까지는 출력이 정말 빠르던데, 다시 수정해서 그 이상을 넣어서 출력하려고 하면 속도가 갑자기 정말 심하게 느려집니다. 왜 그런건가요.
참고로 fsout.write 형태로도 해 봤으나 거의 속도차이가 없더군요.
컴파일, 런타임에러 모두 없습니다.