CODEWITHSUNDEEP
c++data-structuresstl
user1136342
user1136342

Reputation: 4941

Appropriate data structure for returning all subsets of a set

I understand the algorithm for doing this but I don't know what data structure (array, linked list, vector, other?) would be best for returning the final set of sets since every example I see just asks to print the sets.

  1. Can someone explain the thought process for deciding between the 3 data structures I mentioned?
  2. Also, are vectors even used anymore? I heard they were obsolete but still see many recent examples.

To be clear, I mean ALL subsets, so they have different sizes.

Upvotes: 0

Views: 532

Answers (2)

phoxis
phoxis

Reputation: 61910

Once i used bit fields to determine the subsets. Where if the i th bit is 1 then the i the element in the set is selected in the subset and 0 otherwise. In this case you need to store the ordering of the elements. The same can be done with bool vectors i think.

Upvotes: 1

Alok Save
Alok Save

Reputation: 206518

The decision of which data structure to use depends on:

  • Type of data to be stored
  • Operations that you intend to perform on the data

A normal array, would give you contiguous block of memory and random access to the elements, however you need to know the exact number of elements before hand so that you can allocate an array of appropriate size.

With std::vector you get random access to the data, and contiguous just like arrays but vector is a dynamic array,it grows as you add new elements, and a amortized constant complexity, however insertion/deletion of elements is faster only at the ends since all elements need to be moved.

With std::list you don't get the random access but insertion and deletion of elements is faster because it involves just moving around of the pointer links.

Also, are vectors even used anymore?
That is not true at all.
They are very much in use and one of the most widely used data structures provided by the Standard Library.

Upvotes: 2

Related Questions