Карта C ++ STL Я не хочу ее сортировать!

Да, контейнер карты не для вас.
Как вы и просили, вместо этого вам понадобится следующий код:

   struct myClass {
      std::string stringValue;
      int         intValue;
      myClass( const std::string& sVal, const int& iVal ):
               stringValue( sVal ),
               intValue( iVal) {}
   };

   std::vector<myClass> persons;

   persons.push_back( myClass( "B", 123 ));
   persons.push_back( myClass( "A", 321 ));


   for(std::vector<myClass>::iterator i = persons.begin();
      i!=persons.end();
      ++i)
   {
      std::cout << (*i).stringValue << ":" << (*i).intValue << std::endl;
   }

Здесь вывод не отсортирован должным образом.

Что ж, не существует контейнера STL, который бы действительно делал то, что вы хотите, но есть возможности.

1. STL

По умолчанию используется вектор . Здесь это будет означать:

struct Entry { std::string name; int it; };

typedef std::vector<Entry> container_type;

Если вы хотите искать по строке, в вашем распоряжении всегда есть алгоритм find .

class ByName: std::unary_function<Entry,bool>
{
public:
  ByName(const std::string& name): m_name(name) {}
  bool operator()(const Entry& entry) const { return entry.name == m_name; }
private:
  std::string m_name;
};

// Use like this:
container_type myContainer;
container_type::iterator it =
  std::find(myContainer.begin(), myContainer.end(), ByName("A"));

2. Boost.MultiIndex

Это кажется излишним, но вы всегда можете проверить это здесь .

Он позволяет вам создать ОДИН контейнер для хранения, доступный через различные индексы различных стилей, и все они поддерживаются для вас (почти) волшебным образом.

Вместо использования одного контейнера ( std :: map ) для ссылки на контейнер хранения ( std :: vector ) со всеми проблемами синхронизации, которые он вызывает ... вы лучше использовать Boost.

Карта определенно не подходит для вас:

«Внутренне элементы на карте отсортированы от меньшего к большему значению ключа в соответствии с конкретным строгим слабым критерий упорядочения, установленный при построении »

Цитата из здесь .

К сожалению, в STL нет неупорядоченного ассоциативного контейнера, поэтому вы можете либо использовать неассоциативный, например вектор , либо написать свой собственный: - (

Я бы проголосовал за typedef std :: vector > UnsortedMap;

Назначение выглядит немного иначе, но ваш цикл остается таким же, как сейчас.

Использовать вектор . Это дает вам полный контроль над заказом.

Карта - это упорядоченная коллекция (второй параметр в шаблоне - это функтор порядка), как установлено. Если вы хотите вставлять элементы в этих последовательностях как pushd, вы должны использовать deque, list или vector.

Я также считаю, что карта - не лучший вариант. Ключи на карте образуют набор; единственный ключ может встречаться только один раз. Во время вставки в карту карта должна искать ключ, чтобы убедиться, что он не существует, или обновить значение этого ключа. Для этого важно (с точки зрения производительности), чтобы ключи и, следовательно, записи имели определенный порядок. Таким образом, карта с упорядочением вставки будет крайне неэффективной при вставке и извлечении записей.

Другая проблема может возникнуть, если вы используете один и тот же ключ дважды; следует ли сохранить первую или последнюю запись и следует ли обновлять порядок вставки или нет?

Поэтому я предлагаю вам воспользоваться предложением Нилса, вектором для упорядочивания времени вставки и картой для поиска по ключам.

Как сказал Матье в другом ответе, библиотека Boost.MultiIndex кажется правильным выбором для того, что вы хотите. Однако эту библиотеку может быть немного сложно использовать вначале, особенно если у вас нет большого опыта работы с C ++. Вот как вы могли бы использовать библиотеку для решения точной проблемы в коде вашего вопроса:

struct person {
    std::string name;
    int id;
    person(std::string const & name, int id) 
    : name(name), id(id) { 
    }
};

int main() {

    using namespace::boost::multi_index;
    using namespace std;

    // define a multi_index_container with a list-like index and an ordered index
    typedef multi_index_container<
      person,        // The type of the elements stored
      indexed_by<    // The indices that our container will support
        sequenced<>,                           // list-like index
        ordered_unique<member<person, string, 
                              &person::name> > // map-like index (sorted by name)
      >
    > person_container;

    // Create our container and add some people
    person_container persons;
    persons.push_back(person("B", 123));
    persons.push_back(person("C", 224));
    persons.push_back(person("A", 321));

    // Typedefs for the sequence index and the ordered index
    enum { Seq, Ord };
    typedef person_container::nth_index<Seq>::type persons_seq_index;
    typedef person_container::nth_index<Ord>::type persons_ord_index;

    // Let's test the sequence index
    persons_seq_index & seq_index = persons.get<Seq>();
    for(persons_seq_index::iterator it = seq_index.begin(), 
                                    e = seq_index.end(); it != e; ++it)
        cout << it->name << ":"<< it->id << endl;
    cout << "\n";

    // And now the ordered index
    persons_ord_index & ord_index = persons.get<Ord>();
    for(persons_ord_index::iterator it = ord_index.begin(), 
                                    e = ord_index.end(); it != e; ++it)
        cout << it->name << ":"<< it->id << endl;
    cout << "\n";

    // Thanks to the ordered index we have fast lookup by name:
    std::cout << "The id of B is: " << ord_index.find("B")->id << "\n";
}

Что дает следующий результат:

B:123
C:224
A:321

A:321
B:123
C:224

The id of B is: 123

Помимо рекомендаций Нила о комбинированной векторной + карте, если вам нужно как сохранить порядок вставки, так и возможность поиска по ключу, вы также можете рассмотреть возможность использования многоиндексных библиотек boost, которые обеспечивают адресацию контейнеров несколькими способами.

Для того чтобы делать то, что они делают, и быть эффективными в этом, карты используют хэш-таблицы и сортировку. Поэтому вы будете использовать карту, если готовы отказаться от памяти порядка вставки, чтобы получить удобство и производительность поиска по ключу.

Если вам нужно хранить порядок вставки, одним из способов будет создание нового типа, который сопрягает значение, которое вы храните, с порядком, в котором вы его храните (вам придется написать код для отслеживания порядка). Затем для хранения можно использовать map of string к этому новому типу. Когда вы выполняете поиск по ключу, вы также можете получить порядок вставки и затем отсортировать значения на основе порядка вставки.

Еще один момент: если вы используете карту, имейте в виду, что проверка на существование persons["C"] (после того, как вы вставили только A и B) фактически вставит пару ключ-значение в вашу карту.

Для сохранения всех ограничений временной сложности нужны map + list:

struct Entry
{
   string key;
   int val;
};

typedef list<Entry> MyList;
typedef MyList::iterator Iter;
typedef map<string, Iter> MyMap;

MyList l;
MyMap m;

int find(string key)
{
   Iter it = m[key]; // O(log n)
   Entry e = *it;
   return e.val;
}

void put(string key, int val)
{
   Entry e;
   e.key = key;
   e.val = val;
   Iter it = l.insert(l.end(), e); // O(1)
   m[key] = it;                    // O(log n)
}

void erase(string key)
{
   Iter it = m[key];  // O(log n)
   l.erase(it);       // O(1)
   m.erase(key);      // O(log n)
}

void printAll()
{
   for (Iter it = l.begin(); it != l.end(); it++)
   {
       cout<< it->key << ":"<< it->val << endl;
   }
}

Enjoy

Используйте карту вместе с вектором итераторов при вставке в карту. (Гарантируется, что итераторы карты не станут недействительными)

В приведенном ниже коде я использую Set set myset; vector :: iterator> vec;

void printNonDuplicates () {{ {1}} vector :: iterator> :: iterator vecIter; for (vecIter = vec.begin (); vecIter! = Vec.end (); vecIter ++) { cout << ( * vecIter) -> c_str () <

void insertSet (string str) { pair :: iterator, bool> ret; ret = myset.insert (str); if (ret.second) vec.push_back (ret.first); }