c++.de :: sortiertes array of ints

Unregistrierter

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?

Unregistrierter 12:34:23 06.05.2012 Titel:

C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	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 Moderator 12:35:22 06.05.2012 Titel:

C++:
#include<set>

edit: Zu langsam.

Unregistrierter 12:36:41 06.05.2012 Titel:

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 Mitglied 12:36:47 06.05.2012 Titel:

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

Unregistrierter

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

C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23	#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")); }

Unregistrierter

seldon schrieb:

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

C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23	#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.