Iterator mapy w strukturze problem

Question

Witam

Chciałem zrobić sobie funkcję sortującą wielowymiarową mapę i chciałem użyć do tego iteratora ale pojawił się pewien problem.

map<string, map<string, string>> mapa;

for(int i = 0; i < 1500; i++) {
    mapa[to_string(i)]["id"] = to_string(i);
}

struct struktura;

map<string, map<string, string>>::iterator it = mapa.end();
it--;

cout << it->second["id"] << endl; // To działa. Wyświetla id 1499

struktura strukt;
strukt.list = mapa;
strukt.sort();

struct struktura {
    map<string, map<string, string>> list;

    void sort() {
        map<string, map<string, string>> it = list.end();
        it--;
        cout << it->second["id"] << endl; // Tutaj wyświetla 999. Czemu?
}

Poza strukturą wszystko ładnie działa a w strukturze maksymalny iterator ma indeks 999 chociaż mapa ma 1500 elementów. Tak samo mogę w strukturze te elementy wyświetlić w ten sposób:

cout << list["1400"]["id"];

I wszystko ładnie działa. Wie ktoś może co jest tego przyczyną? Może trzeba to zalakować dynamicznie z większą ilością pamięci? 

Z góry dziękuję za pomoc. ;)

Answer 1

U mnie oba kody (po poprawkach*) dają 999 - co jest poprawnym wyjściem, bo 999 jest leksykograficznie największe.

* Pokaż prawdziwy kod, którego używałeś do testów - bo to, co masz teraz, nie ma prawa się skompilować i wygląda jakbyś to pisał z pamięci.

Przy okazji, nie ma sensu mówić o "sortowaniu" std::map, bo ona z definicji ma określoną kolejność elementów której nie da się zmienić.

Comments

Bo pisałem to z pamięci żeby jakkolwiek to zobrazować.

Nie będę wrzucał całego kodu ponieważ jest tam dużo zbędnych rzeczy.

#include /* ... */
#include "structs.hpp"

using namespace std;

int main() {
	for (int i = 0; i < 1040; i++) {
		mapa[to_string(i)]["clid"] = to_string(i);
	}

	clientList list;
	list.list = mapa;

	list.sort1();

	for (int i = 0; i < 1000; i++) {
		cout << list.list[to_string(i)]["clid"] << endl;
	}

}

structs.cpp: (hpp nie daje bo to chyba oczywiste co tam się znajduje :D)

#include /* .. */
using namespace std;

/*
void clientList::partition(map <string, map<string, string>>::iterator it_p, map <string, map<string, string>>::iterator it_k)
{
	map <string, map<string, string>>::iterator it_os = it_p;
	map <string, map<string, string>>::iterator it_os1 = it_k;

	cout << it_os1->second["clid"] << endl;
	
	while (it_os != it_os1) {
		it_os++;
		if (it_os == it_os1) {
			break;
		}
		else {
			it_os1--;
		}
	}
	
	map <string, map<string, string>>::iterator it_pp = it_p;
	map <string, map<string, string>>::iterator it_kk = it_k;

	map <string, map<string, string>>::iterator buffer;

	map<string, string> buf = it_os->second;
	
	bool os_block = false;
	bool os_block2 = false;

	int wartosc = stoi(it_os->second["clid"]);

	do {
		if (!os_block) {
			while (stoi(it_p->second["clid"]) < wartosc) {
				it_p++;
				if (it_p == it_os) {
					it_p--;
					os_block = true;
					break;
				}
			}
		}

		if(!os_block2) {
			cout << it_k->second["clid"] << endl;
			while (stoi(it_k->second["clid"]) > wartosc) {
				it_k--;
				if (it_k->second == buf) {
					os_block2 = true;
					break;
				}
			}
		}
		int test;
		cin >> test;
		buffer = it_p;
		list.insert(it_p, it_k);
		list.insert(it_k, buffer);
		
	} while (!os_block && (it_k != it_os));
	
	partition(it_pp, it_p);
	partition(it_k, it_kk);
}
*/

void clientList::sort1() {
	map <string, map<string, string>>::iterator &it_kk = list.end();
	
	map <string, map<string, string>>::iterator it_p = list.begin();
	cout << "Max size: " << list.max_size() << endl;
	it_kk--;
	cout << it_kk->second["clid"] << endl;; // Tutaj wyświetla 999 :(
	cout << list["1030"]["clid"] << endl; // Ładnie wyświetla 1030
	int lol;
	cin >> lol;
	//partition(it_p, it_kk);
}

Nie przyglądajcie się tej skomentowanej funkcji bo jest to taka pierwsza wersja i bez komentarzy teraz raczej nie zadziała. :D Tak samo brzydko napisana ale widzę to i wiem gdzie trzeba poprawić. Między innymi te if'y. :)

---

W każdym razie, jak mówiłem - stringi, jak nazwa sugeruje, są sortowane leksykograficznie. "999" > "1030". Jeśli chcesz żeby były według liczb, zrób map<int, xyz> albo w ogóle nie map<> tylko zwykły vector.

---

No w sumie to by wszystko wyjaśniało. Vector nie wchodzi w grę ponieważ docelowo tam nie ma być liczb tylko normalne wyrazy więc nie powinno być problemu. Zresztą będę robił też taką strukturę tylko dla map<int, map<string, string>>. O sortowaniu leksykograficznym nie wiedziałem. :/ Ogólnie to mam jeszcze pytanie. Jeżeli tak iterator zwraca wartości to mapa domyślnie sortuje wartości? np.

map<int, string> mapa;

map[1] = "w1";
map[3] = "w3";
map[2] = "w2:'

// Po takiej deklaracji iteracja będzie przebiegać w takiej kolejności?

// it - iterator

cout << it->second; // w1
it++;
cout << it->second; // w2
it++;
cout << it->second; // w3

// Czy zwróci je w takiej kolejności jak zostały dodane?

W sumie teraz tak sobie pomyślałem że mogłem sobie to sam sprawdzić zamiast się pytać. :D No ale co by było gdyby indeksami był obiekt?

map<Obiekt, string> mapa;

 

---

Mapa zawsze ma posortowane obiekty, bo jest zaimplementowana jako drzewo binarne. Wystarczy spojrzeć na pierwsze zdanie dokumentacji (cppreference):

std::map is a sorted associative container

No ale co by było gdyby indeksami był obiekt? map<Obiekt, string> mapa;

Obiekt będący kluczem std::map musi implementować operator<. Dla liczb jest to normalne porównywanie liczb, dla std::string to porównywanie leksykograficzne (jak w dzienniku, "adam" na początku i "ziutek" na końcu) etc.

---

Dzięki za dobrą odpowiedź. :) Trzeba zacząć czytać co pisze w dokumentacji o danym obiekcie a nie tylko wybiórczo opisy działania funkcji.