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

Question

Это мой код

map<string,int> persons;

persons["B"] = 123;
persons["A"] = 321;


for(map<string,int>::iterator i = persons.begin();
    i!=persons.end();
    ++i)
{
    cout<< (*i).first << ":"<<(*i).second<<endl;
}

Ожидаемый результат:

  B:123
  A:321

Но на выходе получается:

  A:321
  B:123

Я хочу сохранить порядок, в котором ключи и значения были вставлены в map<string,int>.

Возможно ли это? Или я должен использовать какую-то другую структуру данных STL? Какой?

Answer 1

Нет стандартного контейнера, который делает то, что вы хотите. Очевидным контейнером для использования, если вы хотите поддерживать порядок вставки, является вектор. Если вам также нужен поиск по строке, используйте вектор И карту. В общем случае карта будет иметь индекс строки к вектору, но поскольку ваши данные уже являются целыми числами, вы можете просто захотеть дублировать их, в зависимости от варианта использования.

Answer 2

Как сказал Матье в другом ответе, библиотека 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

Answer 3

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

"Внутренне элементы на карте сортируются от нижнего к верхнему значению ключа в соответствии с определенным строгим критерием слабого упорядочения, установленным при построении."

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

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

Answer 4

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

Answer 5

карт и наборов предназначены для наложения строгого слабого порядка на данные. Строгое слабое упорядочение утверждает, что ни одна запись не является эквивалентной (отличной от равной).

Вам необходимо предоставить функтор, который карта / набор может использовать для выполнения a<b. С помощью этого функтора карта / набор сортирует свои элементы (в STL из GCC используется красно-черное дерево). Он определяет погоду, если два элемента эквивалентны, если !a<b && !b<a - тест эквивалентности.

Функтор выглядит следующим образом:

template <class T>
struct less : binary_function<T,T,bool> {
  bool operator() (const T& a, const T& b) const {
    return a < b;
  }
};

Если вы можете предоставить функцию, которая сообщает STL, как упорядочивать вещи, тогда карта и набор могут делать то, что вы хотите. Например

template<typename T>
struct ItemHolder
{
    int insertCount;
    T item;
};

Затем вы можете легко написать функтор для заказа с помощью insertCount. Если ваша реализация использует красно-черные деревья ваши базовые данные будут оставаться сбалансированными - однако вы получите большую перебалансировку, поскольку ваши данные будут генерироваться на основе инкрементного упорядочения (по сравнению со случайным) - в этом случае list с push_back будет лучше. Однако вы не можете получить доступ к данным по ключу так же быстро, как с картой / набором.

Если вы хотите сортировать по строке - предоставьте функтору для поиска по строке, используя insertCount, вы можете работать в обратном направлении. Если вы хотите искать по обоим, у вас может быть две карты.

map<insertcount, string> x; // auxhilary key
map<string, item> y; //primary key

Я часто использую эту стратегию - однако я никогда не помещал ее в код, который часто выполняется. Я рассматриваю boost :: bimap .

Answer 6

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

1. СТЛ

По умолчанию используйте vector. Здесь это будет означать:

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.

Answer 7

Время от времени у меня возникала одна и та же проблема, и вот мое решение: https://github.com/nlohmann/fifo_map. Это решение C ++ 11 только для заголовков и может использоваться в качестве замены для std::map.

Для вашего примера его можно использовать следующим образом:

#include "fifo_map.hpp"
#include <string>
#include <iostream>

using nlohmann::fifo_map;

int main()
{
    fifo_map<std::string,int> persons;

    persons["B"] = 123;
    persons["A"] = 321;

    for(fifo_map<std::string,int>::iterator i = persons.begin();
        i!=persons.end();
        ++i)
    {
        std::cout<< (*i).first << ":"<<(*i).second << std::endl;
    }
}

В этом случае вывод

B:123
A:321

Answer 8

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

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;
   }
}

Наслаждайтесь

Answer 9

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

Answer 10

Вместо карты вы можете использовать функцию пары с вектором! например:

vector<::pair<unsigned,string>> myvec;
myvec.push_back(::pair<unsigned,string>(1,"a"));
myvec.push_back(::pair<unsigned,string>(5,"b"));
myvec.push_back(::pair<unsigned,string>(3,"aa"));`

Выход:

myvec[0]=(1,"a"); myvec[1]=(5,"b"); myvec[2]=(3,"aa");

или другой пример:

vector<::pair<string,unsigned>> myvec2;
myvec2.push_back(::pair<string,unsigned>("aa",1));
myvec2.push_back(::pair<string,unsigned>("a",3));
myvec2.push_back(::pair<string,unsigned>("ab",2));

Выход: myvec2[0]=("aa",1); myvec2[1]=("a",3); myvec2[2]=("ab",2);

Надеюсь, что это может помочь кому-то еще в будущем, кто искал несортированные карты, как я!