sortiertes array of ints

Ich habe ein int array[1000]; und will nach und nach ints einfügen, so dass das array sortiert bleibt. Dabei können auch Werte zweimal auftreten. Also im Prinzip wie eine multimap, oder?

Hat da jemand Code für?

int main()
{
	multiset<int> ms;

	ms.insert(32);
	ms.insert(564);
	ms.insert(232);
	ms.insert(1);
	ms.insert(0);

	for(multiset<int>::const_iterator it=ms.begin(); it!=ms.end(); ++it)
	{
		cout << *it << '\n';
	}
}

SeppJ

#include<set>

edit: Zu langsam.

KOmmt drauf an, was du brauchst: Assoziative oder Sequentielle Container. Eig. Brauchst du aber ein std::multiset , du kannst aber auch eine std::list nehmen und sortieren...

Edit: Auch zu langsam ... hyperaktive Forenuser..

cooky451

http://en.cppreference.com/w/cpp/algorithm
Guck dir da mal die "Binary search operations (on sorted ranges)" Funktionen an. Bedenke aber, dass du auf einem Array die Elemente eventuell verschieben musst. Insofern dürfte die Suche etwas schneller sein, das Einfügen von Elementen aber nicht. Und das Verhältnis verschiebt sich zu Gunsten von multiset je mehr Elemente du hast.

Edit: Argh, der Letzte. oO

Warum so umständlich? Ich hätte dafür jetzt einfach std::inplace_merge missbraucht:

#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>

int main() {
  int array[1000];
  size_t n;

  std::srand(std::time(0));

  for(n = 0; n < 100; ++n) {
    // Element hinten anfügen; der vordere Teil ist sortiert, und das neue Element
    // kann als sortiertes Teilarray aufgefasst werden, womit die Voraussetzungen
    // für std::inplace_merge gegeben sind.

    array[n] = rand() % 10000;
    std::inplace_merge(array, array + n, array + n + 1);
  }

  std::copy(array, array + n, std::ostream_iterator<int>(std::cout, "\n"));
}

seldon schrieb:

Warum so umständlich? Ich hätte dafür jetzt einfach std::inplace_merge missbraucht:

#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>

int main() {
  int array[1000];
  size_t n;

  std::srand(std::time(0));

  for(n = 0; n < 100; ++n) {
    // Element hinten anfügen; der vordere Teil ist sortiert, und das neue Element
    // kann als sortiertes Teilarray aufgefasst werden, womit die Voraussetzungen
    // für std::inplace_merge gegeben sind.

    array[n] = rand() % 10000;
    std::inplace_merge(array, array + n, array + n + 1);
  }

  std::copy(array, array + n, std::ostream_iterator<int>(std::cout, "\n"));
}

Danke, das hab ich gesucht.