Tìm phần tử trên Linked list của STL

[Rok_Hoang (Minh Hoàng)]

List của STL có thể duyệt tuyến tính để tìm một phần tử không? Cài đặt như thế nào?

[tntxtnt]

xài std::find ấy. std::list, std::vector, std::deque gì cũng cùng 1 code:

auto it = std::find(p.begin(), p.end(), x);

với x là giá trị cần tìm trong container p. Giá trị trả về là iterator it có thể xem như là con trỏ. Để kiểm tra xem có tìm thấy x trong p thì đơn giản là kiểm tra xem it != p.end():

if (it != p.end())
{ /*xử lý với *it */ }

[Rok_Hoang (Minh Hoàng)]

Vậy có cách nào tìm phần tử min, max (theo giá trị của một element của struct) trên list không anh?

[tntxtnt]

có, xài std::min_element hay std::max_element ấy: http://en.cppreference.com/w/cpp/algorithm/max_element

ví dụ có cái struct Student { int id; std::string name; double avgScore; } chứa trong 1 std::list<Student> p, bây giờ tìm student trong p có điểm trung bình cao nhất thì:

auto maxAvgScoreIt = std::max_element(p.begin(), p.end(), [](const Student& a, const Student& b){
    return a.avgScore < b.avgScore;
});

kết quả maxAvgScoreIt thu được là iterator tới student có đtb cao nhất. Iterator có thể tạm hiểu là con trỏ cũng được (có vài hạn chế, ví dụ iter của list thì hạn chế là không random access được, tức là ko xài [] như con trỏ được)

nếu ko xài C++11 thì có thể viết hàm riêng so sánh 2 cái struct. Hoặc nếu viết class ko lấy được phần tử trong object của class đó thì viết 1 static compare function:

class Student
{
public:
    static bool compByAvgScore(const Student& a, const Student& b)
    { return a.avgScore < b.avgScore; }
private:
    int id;
    std::string name;
    double avgScore;
}

//...
std::list<Student>::iterator maxAvgScoreIt = std::max_element(p.begin(), p.end(), Student::compByAvgScore);

nếu muốn tìm element lớn nhất ở vị trí (index) nào thì xài std::distance, nhưng mà index trong list là vô dụng vì có random access được như mảng hay vector đâu.

int index = std::distance(p.begin(), maxAvgScoreIt);