Java sorted Collection impl ที่อนุญาตให้มีค่าเท่ากันหลายค่า

ฉันพยายามใช้ TreeSet:

Comparator<Product> pc = (p1, p2) -> ((Double) p1.getPrice()).compareTo(p2.getPrice());
Set<Product> products = new TreeSet<>(pc);
products.add(new Product(10));
products.add(new Product(10));

แต่ปัญหาคือไม่สามารถมีค่าเท่ากันได้มากกว่าหนึ่งค่าในแง่ของตัวเปรียบเทียบ ดังนั้นจะมีเพียงหนึ่งในผลิตภัณฑ์เท่านั้นที่จะอยู่ในชุด products

ฉันต้องการใช้งาน Collection บางอย่าง ซึ่งจะเรียงลำดับค่าที่แทรกใหม่ อนุญาตให้มีค่าเท่ากัน (ในแง่ของตัวเปรียบเทียบ) และมีความซับซ้อนในการแทรก log(n) (อาจเป็นนัยตามต้นไม้)


java collections
person Kysil Ivan    schedule 08.02.2017    source แหล่งที่มา
comment
ผลิตภัณฑ์ของคุณมีสิ่งที่เป็นเอกลักษณ์ เช่น productId หรือไม่   -  person assylias    schedule 08.02.2017
comment
อาจซ้ำซ้อนกับ การใช้งานรายการที่รักษาลำดับ   -  person shmosel    schedule 08.02.2017
comment
assyliad: ไม่ ฉันไม่ต้องการ ID ดูเหมือนว่า Guava TreeMultiset จะดีสำหรับฉัน แต่ฉันสงสัยว่าฉันจะสามารถทำได้โดยใช้ Java Collection API หรือไม่   -  person Kysil Ivan    schedule 08.02.2017
comment
เมื่อคุณพูดว่าแบบต้นไม้ คุณหมายถึง เรียงลำดับ จริงๆ หรือ? การใช้งานคอลเลกชันภายในไม่ควรสำคัญสำหรับคุณ   -  person Andy Turner    schedule 08.02.2017
comment
คุณอาจพบสิ่งที่น่าสนใจใน เหตุใดจึงไม่มี SortedList ใน Java   -  person Andy Turner    schedule 08.02.2017
comment
สำหรับการเปรียบเทียบความซับซ้อนของเวลา โปรดดูที่ infotechgems.blogspot.de/ 2011/11/.   -  person René Scheibe    schedule 08.02.2017

คำตอบ (3)


arrow_upward
4
arrow_downward

class ใน JDK ที่ตรงกับข้อกำหนดของคุณคือ PriorityQueue . จากเอกสาร:

คิวลำดับความสำคัญที่ไม่จำกัดตามฮีปลำดับความสำคัญ องค์ประกอบของคิวลำดับความสำคัญจะถูกเรียงลำดับตามการเรียงลำดับตามธรรมชาติ หรือโดย Comparator ที่ให้ไว้ ณ เวลาก่อสร้างคิว ขึ้นอยู่กับตัวสร้างที่ใช้

และ

หมายเหตุการใช้งาน: การใช้งานนี้ให้เวลา O(log(n)) สำหรับวิธีการจัดคิวและการจัดคิว (offer, poll, remove() และ add); เวลาเชิงเส้นสำหรับวิธี remove(Object) และ contains(Object) และเวลาคงที่สำหรับวิธีการดึงข้อมูล (peek, element และ size)

คุณยังสามารถใช้ TreeSet ต่อไปได้ แต่ให้ Comparator ที่ให้คำตอบที่ไม่ซ้ำใคร ตัวอย่างเช่น หาก Product ของคุณมี name ที่ไม่ซ้ำกัน:

Comparator<Product> pc = Comparator.comparing(Product::getPrice)
                         .thenComparing(Comparator.comparing(Product::getName));

สังเกตการใช้ Comparator.comparing แทนแลมบ์ดาของคุณ - มันเรียบร้อยกว่าและแข็งแกร่งกว่า

person Boris the Spider    schedule 08.02.2017
comment
ขอบคุณ ฉันเพิ่งลองใช้ JDK PriorityOueue และมันก็ใช้ได้สำหรับฉัน - person Kysil Ivan; 08.02.2017

arrow_upward
2
arrow_downward

ในกรณีที่คุณจำเป็นต้องสั่งซื้อองค์ประกอบในเวลาแทรกคุณสามารถใช้ TreeMultiset

person René Scheibe    schedule 08.02.2017

arrow_upward
0
arrow_downward

ดังนั้น
PriorityQueue จึงใช้งานได้ ฉัน.

TreeMultiset ทำ ไม่. เมื่อฉันเพิ่มวัตถุที่แตกต่างกันสองรายการ:
products.add(new Product(10)); products.add(new Product(10));
มันจะมีสองลิงก์สำหรับอินสแตนซ์แรกและไม่มีเลยสำหรับวินาที ()

person Kysil Ivan    schedule 08.02.2017