write the codes in c++ please!

Assignment 3 The bag data structure is a data structure for storing the data in an unordered list. For the bag data structure, the insert function takes 0(1) and the remove function takes 0(1). However the search function for a large bag a lot of different values is O(n) Design a second bag data structure with the same specification of the first bag data structure that has a search time of O(Ig n) but the insert and remove time of O(n). This special bag data structure might be very useful in the real life. Suppose there is a list of items for sale, The users may search for specific items again and again (For multiple times) However removal and insertion to the item list may happen very infrequency This assignment is an example of a data structure with the same capabilities of the other but different performance that is designed for a different environment