The 'best' data structure to use does not necessarily depend on the size of the data, but on what you need to do with it.
For example, if you need fast, random access to members, a vector might work. This has drawbacks, though, as a vector (I believe) stores its data in sequential order in memory, thus requiring millions of bytes of memory in a row to work.
If you don't need very fast access, or you need to be able to re-order and delete quickly, a linked list would work. Linked Lists don't need sequential memory - its data is stored randomly throughout memory - but it does require that you traverse through the whole list to find a certain element (or half the list at best, using a doubly-linked list).
If you need to keep these things in balance, I would suggest a binary search tree. The BST offers relatively quick access, relatively quick deletion, maintains sorted order, and does not require sequential order.
These are just 3 common data sets - you may also like to look at stacks, queues, AVL trees, sets, maps, etc.