[C Elementary] Pemahaman awal tentang daftar class

[C Elementary] Pemahaman awal tentang kelas daftar

2024-07-12

1. Perpustakaan standardaftarbaik

Lapisan bawah daftar adalah struktur daftar tertaut melingkar dua arah dengan bit penjaga.
Dibandingkan dengan struktur daftar tertaut tunggal forward_list, iterator daftar adalah iterator dua arah
Dibandingkan dengan wadah terstruktur berurutan seperti vektor, daftar lebih efisien dalam menyisipkan dan menghapus di posisi mana pun, tetapi tidak mendukung akses acak di posisi mana pun.
Daftar adalah kelas templat. Saat menggunakannya, kita perlu memberikan tipe elemennya.

Saat menggunakan kelas daftar, Anda perlu menyertakan file header<list>

2. Antarmuka umum kelas daftar

1. Konstruktor yang umum digunakan

1. Konstruktor default, membuat daftar tertaut kosong

list();

Misalnya:


void test()
{
	list<int> lt;
}

2. Buatlah objek daftar dan inisialisasi dengan n vals

list(size_type n, const value_type& val =  value_type());

Misalnya:


void test()
{
	list<int> lt(3, 1);
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

hasil operasi:

3.Salin konstruktor kelas daftar

list(const list& x);

Misalnya:


void test()
{
	list<int> lt(3, 1);
	list<int> lt1(lt);
	for (auto i : lt1)
	{
		cout << i << " ";
	}
}

hasil operasi:

4. Gunakan konstruktor inisialisasi iterator


Template<class InputIterator>
 
list(InputIterator first, InputIterator last);

Misalnya:


void test()
{
	list<int> lt(3, 1);
	list<int> lt1(lt.begin(), lt.end());
	for (auto i : lt1)
	{
		cout << i << " ";
	}
}

hasil operasi:

2. Antarmuka kapasitas yang umum digunakan

Masih sama, mari saya bahas bersama-sama di sini.

1.ukuran,kosong,ukuran_maks,ubah_ukuran

ukuran:kembalidaftar tertautJumlah elemen dalam wadah.
size_type size() const;
kosong:kembalidaftarApakah wadahnya kosong (yaituukuranadalah 0).
(Catatan: Fungsi ini tidak mengubah wadah dengan cara apa pun. Untuk menghapusdaftar tertautIsi wadahnya, lihatdaftar::bersih。）
bool empty() const;
ukuran_maksimum(tidak umum digunakan): kembalidaftar tertautJumlah maksimum elemen yang dapat ditampung oleh wadah.
(Karena keterbatasan implementasi sistem atau perpustakaan, ini adalah potensi maksimum yang dapat dicapai oleh sebuah wadahukuran , namun tidak ada jaminan bahwa kontainer akan mencapai ukuran tersebut: kontainer mungkin masih tidak dapat mengalokasikan penyimpanan kapan pun sebelum mencapai ukuran tersebut. )
size_type max_size() const;
mengubah ukuran:Ubah ukuran wadah untuk menampungnyaNelemen.
jikaNlebih kecil dari wadah saat iniukuran, konten akan dikurangi ke sebelumnyaNelemen, menghilangkan elemen yang melebihi (dan menghancurkannya).
jikaNLebih besar dari kontainer saat iniukuran, lalu konten diperluas dengan memasukkan jumlah elemen yang diperlukan di akhir untuk mencapainyaN ukuran dari.Jika ditentukannilai, maka elemen baru akan diinisialisasinilaisalinan, jika tidak, salinan tersebut akan diinisialisasi nilai.
(Perhatikan bahwa fungsi ini mengubah isi sebenarnya dari wadah dengan menyisipkan atau menghapus elemen dari wadah.)
void resize (size_type n, value_type val = value_type());

Misalnya:


void test()
{
	list<int> lt(3, 1);
	/*list<int> lt1(lt);*/
	list<int> lt1(lt.begin(), lt.end());
	list<int> lt2;
	cout << lt1.size() <<endl;
	cout << lt1.empty() <<endl;
	cout << lt2.empty() <<endl;
	lt1.resize(10);
	cout << lt1.size() << endl;
	for (auto i : lt1)
	{
		cout << i << " ";
	}
}

hasil operasi:

3. Akses umum dan traversal

1.Iterator


iterator begin();
 
const_iterator begin() const;
 
iterator end();
 
const_iterator end() const;

Iterator: digunakan untuk mendapatkan posisi node pertama dan node terakhir pada linked listPosisi berikutnya (yaitu posisi penjaga)

Misalnya:


void test()
{
	list<int> lt(5, 2);
	list<int> ::iterator it = lt.begin();
	while (it != lt.end())
	{
		cout << *it << " ";
		++it;
	}
}

hasil operasi:

2. Membalikkan iterator

iterator_terbalik rbegin();

const_reverse_iterator rbegin() const;

iterator_terbalik rend();

const_reverse_iterator rend() const;

Membalikkan iterator, rbegin mendapatkan posisi node terakhir di container, rend mendapatkan posisi bit sentinel di container


void test()
{
	list<int> lt = { 1,23,4,4,5,2 };
	list<int> ::reverse_iterator rit = lt.rbegin();
	while (rit != lt.rend())
	{
		cout << *rit << " ";
		++rit;
	}
}

hasil operasi:

Catatan: Rit iterator terbalik juga harus menggunakan ++ alih-alih --

3.depan dan belakang

depan:

referensi depan();

const_referensi depan() const;

Mengembalikan referensi ke data yang disimpan di node pertama dalam daftar tertaut

kembali:

referensi kembali();

const_referensi kembali() const;

Mengembalikan referensi ke data yang disimpan di node terakhir dalam daftar tertaut

Misalnya:


void test()
{
	list<int> lt = {213123,123,34524,213};
	cout << lt.front() << endl;
	cout << lt.back() << endl;
 
}

hasil operasi:

4.Tambahkan, hapus, periksa dan ubah daftar

1) dorong_depan dan pop_depan

push_front disebut penyisipan kepala, memasukkan elemen dari kepala daftar tertaut

void push_front(const nilai_tipe& val);

pop_front disebut penghapusan kepala, yang menghapus elemen dari kepala daftar tertaut.

batal pop_depan();

void pop_front();

Misalnya:


void test()
{
	list<int> lt = {213123,123,34524,213};
	cout << lt.front() << endl;
	lt.push_front(21345);
	cout << lt.front() << endl;
	lt.pop_front();
	cout << lt.front() << endl;
}

hasil operasi:

2) push_back dan pop_back

push_back disebut penyisipan ekor, menyisipkan elemen dari akhir daftar tertaut

void push_back(const nilai_tipe& val);

pop_back disebut penghapusan ekor, yang menghapus elemen dari akhir daftar tertaut.

batal pop_back();

Misalnya:


void test()
{
	list<int> lt = {213123,123,34524,213};
	cout << lt.back() << endl;
	lt.push_back(21345);
	cout << lt.back() << endl;
	lt.pop_back();
	cout << lt.back() << endl;
}

hasil operasi:

3) temukan


template <class InputIterator, class T>
 
InputIterator find(InputIterator first, InputIterator last, const T& val);

Temukan val di kisaran dua iterator dan kembalikan iterator ke tempatnya

Misalnya:


void test()
{
	list<int> lt;
	for (int i = 0; i < 3; i++)
	{
		lt.push_back(i);
	}
	list<int>::iterator pos = find(lt.begin(), lt.end(), 1);
	*pos = 114514;
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

hasil operasi:

Catatan: Fungsi ini bukan fungsi anggota daftar, tetapi fungsi di perpustakaan standar. Beberapa kontainer berbagi fungsi find.

Seperti yang Anda lihat, kita dapat langsung melakukan dereferensi iterator daftar dan mengubah kontennya, tetapi bukankah iterator harus menunjuk ke node? Mengapa dereferensi dapat mengubah data?

Faktanya, iterator daftar tidak disimulasikan dan diimplementasikan menggunakan penunjuk ekologi asli, dan perlu diringkas di bagian bawah, yang akan tercermin dalam kode sumber implementasi simulasi daftar.

4)masukkan

iterator sisipan(posisi iterator, const tipe_nilai& val);

void insert(posisi iterator, ukuran_tipe n, const tipe_nilai& val);

————————————————————————————————————————

templat<class InputIterator>

void insert(posisi iterator, InputIterator pertama, InputIterator terakhir);

Sisipkan satu atau lebih elemen di depan posisi

Misalnya:


void test()
{
	list<int> lt;
	for (int i = 0; i < 3; i++)
	{
		lt.push_back(i);
	}
	list<int>::iterator pos = find(lt.begin(), lt.end(), 1);
	lt.insert(pos, 8848);
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

hasil operasi:

Siswa yang cermat mungkin telah menemukan bahwa operasi penyisipan daftar adalahTidak akan menyebabkan iterator menjadi tidak valid, karena node yang ditunjuk oleh pos tetap tidak berubah dan posisi relatifnya tidak berubah.

Namun, operasi penghapusan daftar pasti akan menyebabkan iterator menjadi tidak valid, dan hanya iterator yang menunjuk ke node yang dihapus yang akan menjadi tidak valid, dan iterator lainnya tidak akan terpengaruh.

5) menghapus


iterator erase(iterator position);
 
iterator erase(iterator first, iterator last);

Hapus elemen pada posisi atau semua elemen dalam rentang [pertama, terakhir)

Misalnya:


void test()
{
	list<int> lt;
	for (int i = 0; i < 3; i++)
	{
		lt.push_back(i);
	}
	list<int>::iterator pos = find(lt.begin(), lt.end(), 1);
	lt.erase(lt.begin());
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

hasil operasi:


void test()
{
	list<int> lt;
	for (int i = 0; i < 3; i++)
	{
		lt.push_back(i);
	}
	list<int>::iterator pos = find(lt.begin(), lt.end(), 2);
	lt.erase(lt.begin(),pos);
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

hasil operasi:

6) tukar

void swap(vektor& x);

Tukar dua objek daftar

Misalnya:


void test()
{
	list<int> lt;
	list<int> lt2(6, 12);
	for (int i = 0; i < 10; i++)
	{
		lt.push_back(i);
	}
	lt.swap(lt2);
	for (auto i : lt2)
	{
		cout << i << " ";
	}
	cout << endl;
}

hasil operasi:

7）menetapkan

templat<class InputIterator>

void assign(InputIterator pertama, InputIterator terakhir);

void assign(jenis_ukuran n, const jenis_nilai& val);

Tentukan konten baru untuk daftar, ganti konten saat ini dan ubah jumlah node

Misalnya:


void test()
{
	list<int> lt;
	for (int i = 0; i < 10; i++)
	{
		lt.push_back(i);
	}
	lt.assign(4, 0);
	for (auto i : lt)
	{
		cout << i << " ";
	}
}

hasil operasi:

8）jelas

batal hapus();

Hapus semua node dalam daftar tertaut

Misalnya:


void test()
{
	list<int> lt;
	for (int i = 0; i < 10; i++)
	{
		lt.push_back(i);
	}
	lt.clear();
	cout << lt.size() << endl;
}

hasil operasi:

5. Daftar antarmuka modifikasi pesanan

(1）menyortir

batal sort();

templat<class Compare>

void sort(Bandingkan comp);

Karena kekhasan struktur daftar, fungsi pengurutan di perpustakaan standar tidak dapat digunakan, karena iterator tidak dapat melakukan operasi pengurangan.

Dan dalam dokumentasi C++, kita dapat melihat bahwa sortir di perpustakaan standar juga membatasi jenis iterator menjadi akses acak (RandomAccess)


default (1)	
template <class RandomAccessIterator>
  void sort (RandomAccessIterator first, RandomAccessIterator last);
custom (2)	
template <class RandomAccessIterator, class Compare>
  void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);

Iterator memiliki beberapa kategori fungsional:

Iterator satu arah, hanya dapat melakukan ++
Iterator dua arah, bisa ++ dan --
Iterator acak, bisa ++, --, + dan -

Namun, fungsi pengurutan daftar tidak diperlukan, karena efisiensi pengurutan daftar tertaut secara langsung jauh lebih lambat daripada menyalin ke vektor, mengurutkan, dan kemudian menyalin kembali ke daftar tertaut.

(2）balik

template <class BidirectionalIterator>
  void reverse (BidirectionalIterator first, BidirectionalIterator last);

Balikkan daftar tertaut

Misalnya:


void test()
{
	list<int> lt;
	for (int i = 0; i < 10; i++)
	{
		lt.push_back(i);
	}
	for (auto i : lt)
	{
		cout << i << " ";
	}
	cout << endl;
	lt.reverse();
	for (auto i : lt)
	{
		cout << i << " ";
	}
	cout << endl;
 
}

hasil operasi:

Jika ada kesalahan, mohon koreksi saya.

Berbagi teknologi

[C Elementary] Pemahaman awal tentang kelas daftar

1. Perpustakaan standardaftarbaik

2. Antarmuka umum kelas daftar

1. Konstruktor yang umum digunakan

1. Konstruktor default, membuat daftar tertaut kosong

2. Buatlah objek daftar dan inisialisasi dengan n vals

3.Salin konstruktor kelas daftar

4. Gunakan konstruktor inisialisasi iterator

2. Antarmuka kapasitas yang umum digunakan

1.ukuran,kosong,ukuran_maks,ubah_ukuran

3. Akses umum dan traversal

1.Iterator

2. Membalikkan iterator

3.depan dan belakang

4.Tambahkan, hapus, periksa dan ubah daftar

1) dorong_depan dan pop_depan

2) push_back dan pop_back

3) temukan

4)masukkan

5) menghapus

6) tukar

7）menetapkan

8）jelas

5. Daftar antarmuka modifikasi pesanan

(1）menyortir

(2）balik

Profil pribadi

informasi kontak saya