Wektory, parę pytań. :: 4programmers.net

0

Muszę wykonać pewną rzecz na studiach i niestety musi to być w tym języku. Jako, że nie mam czasu na naukę tego języka to mam takie pytanka.

1.Poszukuję struktury z dostęp stałym i w miarę szybkim dodawaniem, czy poza vectorem coś znajdę w c++11?
2. Czy da radę sprawdzić w vectorze czy pole o podanym indeksie jest puste?
3. Czemu tab.size() jest równy 0 pomimo, że istnieją w nim już elementy?
4. Czemu jeśli dodam normalnie insertem np pola o index 1,2,9 to iterując po obiekcie wypisze mi tylko 1,2?

 int main(){
    std::vector< pairlist > tab;
    tab.reserve(200000);
    std::cout<< "j";
    //tab.push_back(pairlist());
    tab[0].add(1, 3);

   // tab.push_back(pairlist());
    tab[1].add(4, 5);
    print_vec(tab);

   // tab.insert(tab.begin()+1, pairlist());
    tab[1].add(2, 4);

   // tab.insert(tab.begin()+9, pairlist());

    tab[9].add(9, 8);
    tab[9].add(22, 5);
    print_vec(tab);
    std::cout << tab.size() << std::endl << tab[9].getNext().first << std::endl;
    std::cout << tab[9].getNext().first;
   
    return 0;
};

 void print_vec(const std::vector<pairlist>& vec)
{
    for (pairlist x: vec) {
        std::cout << ' ' << x.getNext().first;
    }
    std::cout << '\n';
}

1

W C++11 wprowadzili unordered_map.
Co rozumiesz przez "puste"?
tab[n] nie dodaje elementu do wektora i ogólnie jest złą rzeczą. Jak chcesz dodać elementy to tylko push_back, a skoro wcześniej zaalokowałeś tablicę to nie ma to narzutu większego niż przepisanie elementu + zwiększenie licznika.
Pokaż więcej kodu. Zwłaszcza implementację pairlist.

1

Czy da radę sprawdzić w vectorze czy pole o podanym indeksie jest puste?

Co to znaczy puste? w kontenerze vector nie ma „pustych” elementów. Wszystkie o indeksach od 0 do size()-1 istnieją.

Czemu tab.size() jest równy 0 pomimo, że istnieją w nim już elementy?

Nie istnieją. W twoim kodzie masz undefined behavior bo odwołujesz się do obiektów których nie ma.
Metoda reserve tylko alokuje pamięć, nie tworzy obiektów.

0

struct pairlist{
    pairnode *head;
    pairnode *next;
    void add(int x, int y);
    std::pair<int, int> getNext();
    bool isAll();
    pairlist();
};

pairnode to po prostu struktura z parą i wskaźnikiem na następny, a dodawanie to wstawianie na początek i wskaźnik na resztę, ta część kodu akurat działa poprawnie :), a getNext pobiera kolejne elementy z listy.

@Azarien
1.Puste rozumiem, że na polu nie utworzyłem jeszcze obiektu. Więc nie chodzi mi o to czy istnieje komórka tylko czy pod tą komórką istnieje obiekt.

@winerfresh
A jak jest ze złożonością w dostępie i usuwaniu w unordered_map , bo znalazłem tylko że dodawanie jest stałe lub liniowe.

Ogólnie dzięki za rozjaśnienie trochę sytuacji, zastanawiam się czy nie zrobić po prostu tablice z pairlist, bo wiem że maksymalnie będę potrzebował 10 000 komórek a elementów we wszystkich komórkach może być max 200000, pytanie tylko czy mi się zmieści to wszystko w 16mb ? Jak myślicie? I da się jakoś sprytnie utworzyć obiekty pairlist we wszystkich komórkach tablicy, czy to i tak bez znaczenia bo musi to zrobić w czasie liniowym i mogę w pętli to zrobić?

A co do push_back akurat w moim przypadku za wiele mnie nie ratuje bo akurat dość istotne było pod którym indexem sie coś znajduje, ogólnie algorytm ma układać coś co przypomina domino, i tak wiem, że mogę po prostu w walić na pałę wszystko i polecieć dfs, po wszystkim, ale mam trochę inny pomysł i chciałbym go zrealizować XD.

0

Co do złożoności w usuwaniu to idąc za cplusplus.com

Average case: Linear in the number of elements removed (which is constant for versions (1) and (2)).
Worst case: Linear in the container size.

I dostęp

Average case: constant.
Worst case: linear in container size.

May trigger a rehash if an element is inserted (not included in the complexity above).

Takie info są w Complexity http://www.cplusplus.com/reference/unordered_map/unordered_map/operator%5B%5D/

2

A jak jest ze złożonością w dostępie i usuwaniu w unordered_map , bo znalazłem tylko że dodawanie jest stałe lub liniowe.

Operacja	Avg	Worst
Konstruktor bezparametrowy	$\mathcal{0}(1)$	$\mathcal{0}(1)$
Konstruktory tworzące N takich samych elementów	$\mathcal{0}(n)$	$\mathcal{0}(n)$
Konstruktory tworzące mapę z podanego zbioru	$\mathcal{0}(n)$	$\mathcal{0}(n^2)$
`emplace`	$\mathcal{0}(1)$	$\mathcal{0}(n)$
`insert`	$\mathcal{0}(1)$	$\mathcal{0}(n)$
`erase`	$\mathcal{0}(k)$	$\mathcal{0}(n)$
`find`	$\mathcal{0}(1)$	$\mathcal{0}(n)$
`clear`	$\mathcal{0}(n)$	$\mathcal{0}(n)$